arrows relation

Let ${[X]}^{\alpha }=\{Y\subseteq X\mid |Y|=\alpha \}$, that is, the set of subsets of $X$ of size $\alpha$. Then given some cardinals $\kappa$, $\lambda$, $\alpha$ and $\beta$

$$\kappa \to {(\lambda )}_{\beta }^{\alpha }$$

states that for any set $X$ of size $\kappa$ and any function $f:{[X]}^{\alpha }\to \beta$, there is some $Y\subseteq X$ and some $\gamma \in \beta$ such that $|Y|=\lambda$ and for any $y\in {[Y]}^{\alpha }$, $f(y)=\gamma$.

In words, if $f$ is a partition of ${[X]}^{\alpha }$ into $\beta$ subsets then $f$ is constant on a subset of size $\lambda$ (a homogeneous subset).

As an example, the pigeonhole principle is the statement that if $n$ is finite and then:

$$n\to 2_k^1$$

That is, if you try to partition $n$ into fewer than $n$ pieces then one piece has more than one element.

Observe that if

$$\kappa \to {(\lambda )}_{\beta }^{\alpha }$$

then the same statement holds if:

• $\kappa$ is made larger (since the restriction of $f$ to a set of size $\kappa$ can be considered)

• $\lambda$ is made smaller (since a subset of the homogeneous set will suffice)

• $\beta$ is made smaller (since any partition into fewer than $\beta$ pieces can be expanded by adding empty sets to the partition)

• $\alpha$ is made smaller (since a partition $f$ of ${[\kappa ]}^{\gamma }$ where can be extended to a partition $f^{\prime }$ of ${[\kappa ]}^{\alpha }$ by $f^{\prime }(X)=f(X_{\gamma })$ where $X_{\gamma }$ is the $\gamma$ smallest elements of $X$)

$$\kappa \nrightarrow {(\lambda )}_{\beta }^{\alpha }$$

is used to state that the corresponding $\to$ relation is false.

References

• Jech, T. Set Theory, Springer-Verlag, 2003

• Just, W. and Weese, M. Topics in Discovering Modern Set Theory, II, American Mathematical Society, 1996

Title	arrows relation
Canonical name	ArrowsRelation
Date of creation	2013-03-22 17:48:54
Last modified on	2013-03-22 17:48:54
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	5
Author	Henry (455)
Entry type	Definition
Classification	msc 05A18
Classification	msc 03E05
Related topic	PartitionsLessThanCofinality
Related topic	ErdosRadoTheorem
Defines	homogeneous
Defines	arrows
Defines	homogeneous set
Defines	homogeneous subset