Partition relation ($\lambda \to (\mu {)}_{\beta }^{\alpha }$)

The notation $\lambda \to (\mu {)}_{\beta }^{\alpha }$ says that every $\beta$-coloring of the $\alpha$-element subsets of $\lambda$ has a homogeneous subset of order type $\mu$. At infinite arity one specifies whether the domain subsets have a fixed cardinality or a fixed order type; the usual finite-arity notation has no such ambiguity.

Choose a representative $R$ of each class of countably infinite sets modulo finite symmetric difference, and colour $A$ by the parity of $|A△R|$. Removing one element stays in the same class and flips the parity. Every infinite candidate homogeneous set therefore has two countably infinite subsets of opposite colours. With choice, this refutes unrestricted countably infinite-arity positive partition relations on every infinite cardinal.

For an infinite cardinal $\lambda$ and finite $r\ge 0$, put ${\beth }_0(\lambda )=\lambda$ and ${\beth }_{r+1}(\lambda )=2^{{\beth }_r(\lambda )}$. Every $\lambda$-coloring of $(r+1)$-element subsets of ${\beth }_r(\lambda {)}^{+}$ has a homogeneous subset of size ${\lambda }^{+}$. The case $r=1$ is the Erdős-Rado theorem for pairs. For the induction, the end-homogeneous routing tree yields a sequence of length ${\beth }_{r-1}(\lambda {)}^{+}$ on which the color of an $(r+1)$-tuple depends only on its first $r$ entries. The previous-arity theorem homogenizes those $r$ entries. The case $r=0$ is the infinite pigeonhole principle at a successor cardinal.

Put $\theta =(2^{\mu }{)}^{+}$ for an infinite cardinal $\mu$. Choose $M\prec H_{\chi }$ of size $2^{\mu }$, containing all ordinals below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Such a model is built by ${\mu }^{+}$ successive Skolem hull closures, since $(2^{\mu }{)}^{\mu }=2^{\mu }$. For a coloring of $[\theta {]}^{r+1}$ with at most $\mu$ colors in $M$, put $\beta =\sup (M\cap \theta )<\theta$. Recursively choose $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$, above all earlier points, so that every earlier $r$-tuple has the same color with $x_{\alpha }$ as with $\beta$. There are at most $\mu$ constraints, their code belongs to $M$ by closure, and $\beta$ witnesses their consistency. The elementary embedding supplies the required witness in $M$. The resulting sequence is end-homogeneous, providing the induction step in the Erdős-Rado theorem for finite arities.

For a coloring of $(r+1)$-subsets of an ordinal, route a vertex through the least earlier vertices matching its colors on every $r$-subset of previously chosen ancestors. The path stops when the vertex itself is selected. Common path prefixes agree, yielding a set-theoretic tree; a node at level $\alpha$ is determined by its color table on $[\alpha {]}^r$. Along a branch, the color of an $(r+1)$-tuple is independent of its last entry. If the domain has size $(2^{\mu }{)}^{+}$ and $\lambda \le \mu$, levels below ${\mu }^{+}$ have size at most $2^{\mu }$; counting all those levels forces a branch of length ${\mu }^{+}$. If the domain is a regular strong-limit cardinal $\kappa$, those levels instead have size below $\kappa$, and the tree property supplies a cofinal branch when needed.

For every infinite cardinal $\lambda$, every coloring of pairs from $(2^{\lambda }{)}^{+}$ by $\lambda$ colors has a monochromatic subset of size ${\lambda }^{+}$. Construct an end-homogeneous tree by routing a new vertex through the least preceding vertices that match its colors to all previously chosen ancestors. An ancestor's color to every later vertex on a branch is constant. A node at height $\alpha$ is determined by its color sequence of length $\alpha$, so levels below ${\lambda }^{+}$ have size at most ${\lambda }^{|\alpha |}\le 2^{\lambda }$. The whole tree has more than $2^{\lambda }$ vertices, forcing a branch of length ${\lambda }^{+}$. One of the $\lambda$ ancestor-colors occurs ${\lambda }^{+}$ times, giving the required set.

The colors $\nu$ here range over nonzero cardinals. The Erdős-Rado theorem for pairs makes this function total, and target and color monotonicity make it nondecreasing, with $f(\alpha )\ge \alpha$. If an uncountable cardinal $\kappa$ is closed below itself under $f$, then it is strong limit. Indeed, coloring distinct binary strings of length $\lambda <\kappa$ by their first differing coordinate uses $\lambda$ colors and has no monochromatic triangle, so $f(\lambda +1)>2^{\lambda }$. If $\kappa$ also has the tree property, the end-homogeneous tree for any $\nu <\kappa$ has levels of size below $\kappa$ and a cofinal branch; regularity makes one color occur $\kappa$ times. Thus $f(\kappa )=\kappa$. This distinguishes function closure plus the tree property from the tree property alone.

The relation $\lambda \to (\lambda {)}_{\beta }^{<\omega }$ requires a subset of size $\lambda$ homogeneous at each finite arity. The constant color may depend on the arity.

If inaccessible $\lambda$ has the finite-subset partition property for every color number below $\lambda$, forcing of size below $\lambda$ preserves its two-color version. Color ground-model finite sets by their full forcing decision patterns; strong-limit cardinal arithmetic bounds the number of patterns.

A partition relation whose colored subsets are infinite. For countably infinite arity, choosing representatives modulo finite symmetric difference and coloring its parity shows $\kappa \nrightarrow (\omega {)}_2^{\omega }$ for every infinite cardinal $\kappa$.