= Solution
For the effective counterexample, let $K$ be the <diagonal halting set> and let $K_s$ be the finite approximation obtained by running the first $s$ programs for $s$ steps. For $x<y<z$, define the <recursive triple colouring with no computable infinite homogeneous set> by
$$
c(\{x,y,z\})=\begin{cases}0,&K_y\cap\{0,\ldots,x\}=K_z\cap\{0,\ldots,x\},\\1,&\text{otherwise}.\end{cases}
$$
This is a total recursive two-coloring: only bounded computations are involved. An infinite <homogeneous set> $H$ cannot have color one. Fix $x\in H$ and take $y,z\in H$ sufficiently large that every halting computation with index at most $x$ that ever halts has already halted by stage $y$; then the color is zero. If $H$ has color zero, it computes $K$: given $e$, find $x<y$ in $H$ with $x\ge e$ and inspect $K_y(e)$. Agreement with every later stage $z\in H$, and the unboundedness of $H$, give $K_y\cap\{0,\ldots,x\}=K\cap\{0,\ldots,x\}$. Hence this is the correct answer. The <set> $K$ is not recursive: a purported halting decider would produce a program that halts exactly when the decider says it does not halt on its own index. Thus \b[there is no recursive infinite <homogeneous set>]. Here infinite is essential: every finite <subset> is recursive, and <sets> with fewer than three elements are vacuously homogeneous.
A precise finite-arity <Erdős-Rado theorem for finite arities> is
$$
\boxed{\beth_r(\lambda)^+\longrightarrow(\lambda^+)^{r+1}_\lambda\quad(r<\omega,\ \lambda\text{ an infinite cardinal}),}
$$
where $\beth_0(\lambda)=\lambda$ and $\beth_{r+1}(\lambda)=2^{\beth_r(\lambda)}$. We prove the <closed elementary-submodel construction of an end-homogeneous sequence> and then induct. We work with <AC>, as in the usual <cardinal> partition calculus.
Put $\theta=(2^\mu)^+$, where $\mu$ is infinite, and let $c:[\theta]^{m+1}\to\lambda$ with $\lambda\le\mu$ and $m\ge1$. Choose a <regular cardinal> $\chi$ large enough that this coloring and its domain belong to $H_\chi$, the <sets> of hereditary size below $\chi$. There is $M\prec H_\chi$ of size $2^\mu$ containing $c,\theta,\mu$, every <ordinal> below $\mu^+$, and closed under externally given <sequences> of length at most $\mu$. Here is the closure construction: start with a <Skolem hull> of the named parameters and the <ordinals> below $\mu^+$; iterate hulls after adjoining all at-most-$\mu$-sequences of the preceding hull for $\mu^+$ stages. Every stage and the <union> have size $2^\mu$, since $(2^\mu)^\mu=2^\mu$ and $\mu^+\le2^\mu$. The <elementary chain theorem> gives elementarity. Any <sequence> of at most $\mu$ members of the final <union> lies in a bounded stage, because $\mu^+$ is regular, and is added at the next stage. This proves the required closure.
Let $\beta=\sup(M\cap\theta)$. Regularity of $\theta$ gives $\beta<\theta$, and $\beta\notin M$: otherwise $\beta+1$ would also belong to $M\cap\theta$. Recursively choose increasing $x_\alpha\in M\cap\theta$ for $\alpha<\mu^+$ so that, for every $m$-subset $u$ of the earlier points,
$$
c(u\cup\{x_\alpha\})=c(u\cup\{\beta\}).
$$
To justify the recursion, the earlier <sequence> has length at most $\mu$, hence belongs to $M$. There are at most $\mu$ constraints. All their points and color values are in $M$, so their coded table belongs to $M$ by closure, even though $\beta$ itself is external to $M$. The supremum of the earlier points, plus one, also belongs to $M\cap\theta$ and is below $\beta$. Thus $\beta$ witnesses in $H_\chi$ that a point above that bound satisfying the table exists. Elementarity supplies such a point in $M$. This completes the recursion.
The <sequence> is end-homogeneous: on any increasing $(m+1)$-tuple from it, the color depends only on its first $m$ entries. Define the induced $m$-tuple coloring by $g(u)=c(u\cup\{\beta\})$. For the <induction>, the arity-one assertion $\lambda^+\to(\lambda^+)^1_\lambda$ is the infinite pigeonhole principle: a <union> of $\lambda$ <sets> each of size at most $\lambda$ has size at most $\lambda$. At step $r\ge1$, take $\mu=\beth_{r-1}(\lambda)$, so $\theta=\beth_r(\lambda)^+$. The constructed <sequence> has size $\mu^+=\beth_{r-1}(\lambda)^+$. The <induction> hypothesis makes $g$ constant on a <subset> of size $\lambda^+$; end-homogeneity makes $c$ constant on its $(r+1)$-subsets. This proves the theorem. In particular $\lambda=\aleph_0$ gives an uncountable <homogeneous set> for every finite-arity coloring with countably many colors, on a sufficiently large <cardinal>.
There is no unrestricted infinite-exponent analogue under <AC>. For any infinite <cardinal> $\kappa$, choose one representative $R$ from each equivalence class of $[\kappa]^\omega$ modulo <finite symmetric difference>. Color $X$ by the parity of $|X\mathbin\triangle R|$. Removing one element of $X$ leaves it in the same class and reverses the parity. Every infinite proposed <homogeneous set> contains both a countably infinite $X$ and $X\setminus\{x\}$, so cannot be homogeneous. Thus the <finite-symmetric-difference colouring of infinite subsets> proves
$$
\boxed{\kappa\not\longrightarrow(\omega)^\omega_2\quad\text{for every infinite }\kappa\text{, under AC}.}
$$
The contrast is between arbitrary colorings at countably infinite arity and the finite arities of the theorem; restrictions on the definability of an infinite-arity coloring can change the problem.
Back to article page
