# 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\rightarrow(\lambda)^{\alpha}_{\beta}$

states that for any set $X$ of size $\kappa$ and any function $f:[X]^{\alpha}\rightarrow\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 $k then:

 $n\rightarrow 2^{1}_{k}$

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\rightarrow(\lambda)^{\alpha}_{\beta}$

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 $\gamma<\alpha$ 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)^{\alpha}_{\beta}$

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

References

 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