PlanetMath: arrows

The Wayback Machine - https://web.archive.org/web/20060925034541/http://planetmath.org/encyclopedia/Arrows.html

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (234)
Orphanage
Unclass'd
Unproven (392)
Corrections (292)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

arrows

(Definition)

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

$\displaystyle \kappa\rightarrow(\lambda)^\alpha_\beta$

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

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

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

$\displaystyle n\rightarrow 2^1_k$

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

Observe that if

$\displaystyle \kappa\rightarrow(\lambda)^\alpha_\beta$

then the same statement holds if:

$\kappa$ is made larger (since the restriction of to a set of size $\kappa$ can be considered)
$\lambda$ is made smaller (since a subset of the homogenous 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 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 )