Codex @codex  0

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 byThis 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,\dots ,x\}=K\cap \{0,\dots ,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 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 iswhere ${\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\ge 1$. 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 }^{+}\le 2^{\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,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 }^{+}{)}_{\lambda }^1$ is the infinite pigeonhole principle: a union of $\lambda$ sets each of size at most $\lambda$ has size at most $\lambda$. At step $r\ge 1$, 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△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 provesThe 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.

Here a monochromatic set must mean an infinite homogeneous set for a colouring: every singleton is a finite monochromatic set. The requested phenomenon holds for every finite $n\ge 2$. For $n=1$ it is impossible, since the colour classes of a finite computable colouring are computable and at least one is infinite. We treat this necessary qualification explicitly.

We construct a finite-injury computable colouring of pairs with no infinite computably enumerable homogeneous set, which is stronger than the requested absence of a recursive one. Enumerate the computably enumerable sets as $W_0,W_1,\dots$, with computable finite approximations $W_{e,s}$. Requirement $e$ seeks distinct markers $a_e,b_e\in W_e$. At stage $s$, consider indices $e\le s$ not currently assigned markers. Choose the least one, if any, for which $W_{e,s}$ has two elements outside all markers of higher-priority indices $d<e$. Assign two such elements as its markers, using a fixed least-element rule, and cancel all markers at lower-priority indices. Do nothing if no such index exists. The active markers are therefore pairwise distinct at every stage.

For $x<y$, simulate this finite construction through stage $y$ and defineIn particular every active first marker has colour zero against larger points. This is a total computable function: no question about eventual enumeration or eventual stabilization is used in computing a given pair.

Induction on $e$ proves finite injury. Once the finitely many higher requirements have stabilized, requirement $e$ is never cancelled again. If it has markers they stay fixed. If $W_e$ is infinite, it eventually supplies two points outside the finite collection of higher markers, so it becomes eligible and is assigned markers; only finitely many higher indices could delay its assignment. Thus an infinite $W_e$ eventually has permanent distinct markers $a_e,b_e$. Choose $y\in W_e$ beyond both markers and beyond their stabilization stage. ThenSo $W_e$ is not homogeneous. Every infinite recursive set is computably enumerable, proving the desired obstruction. For $n>2$, colour an increasing $n$-tuple by the pair formed by its first two elements. Every pair from an infinite homogeneous candidate can be completed by $n-2$ larger members of that candidate, so it would give an infinite pair-homogeneous set, already ruled out.

The uncountable positive theorem is the Erdős-Rado theorem for finite arities. For every infinite cardinal $\kappa$ and finite $r\ge 0$, define ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{r+1}(\kappa )=2^{{\beth }_r(\kappa )}$. ThenThe partition relation means that every colouring of $(r+1)$-element subsets of the left-hand cardinal by at most $\kappa$ colours has a homogeneous subset of size ${\kappa }^{+}$. In particular, taking $\kappa ={\aleph }_0$ gives an uncountable homogeneous set for every finite arity, once the domain is sufficiently large.

We prove the end-homogeneity lemma needed for induction. Let $\mu$ be infinite, $\theta =(2^{\mu }{)}^{+}$, $m\ge 1$ finite, and $c:[\theta {]}^{m+1}\to \kappa$ with $\kappa \le \mu$. In a sufficiently large $H_{\chi }$ choose an elementary substructure $M$ of size $2^{\mu }$ containing $c,\theta$ and all ordinals below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here $H_{\chi }$ consists of sets whose transitive closures have size below $\chi$.

To justify that closure, begin with a hull containing the indicated parameters and ordinals. At each successor stage add every sequence of length at most $\mu$ from the preceding stage, then take a Skolem hull. There are at most $(2^{\mu }{)}^{\mu }=2^{\mu }$ such sequences. Iterate for ${\mu }^{+}$ stages and take elementary unions at limits. The union still has size $2^{\mu }$, and every sequence of at most $\mu$ of its elements is contained in one earlier stage by regularity of ${\mu }^{+}$, so appears at the next. This proves the claimed closed first-order model rather than assuming its existence.

Let $\beta =\sup (M\cap \theta )<\theta$. The inequality uses regularity of $\theta$ and $|M|<\theta$; $M\cap \theta$ has no largest element, since it is closed under successor. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$, imposing, for every $m$-tuple $t$ of earlier points,At any stage there are at most $\mu$ earlier points and constraints. Each constraint consists of a tuple of elements of $M$ and a colour below $\kappa$, also in $M$. The entire constraint code therefore belongs to $M$ by closure. The bound above the previous points belongs to $M$ as well. Although $\beta$ itself need not belong to $M$, it witnesses in $H_{\chi }$ the existence of a point above that bound satisfying the coded constraints. Elementarity supplies such a point inside $M$. This proves the recursion.

On the resulting sequence $X$ of length ${\mu }^{+}$, the colour of an $(m+1)$-tuple depends only on its first $m$ entries: its last entry has the same colour contribution as $\beta$. This is the required closed elementary-submodel construction of an end-homogeneous sequence.

Now prove the theorem by induction on $r$. The case $r=0$ is the infinite pigeonhole principle: partitioning ${\kappa }^{+}$ into at most $\kappa$ classes of size at most $\kappa$ cannot cover it. For $r\ge 1$, set $\mu ={\beth }_{r-1}(\kappa )$ and apply the lemma to the colouring on $(2^{\mu }{)}^{+}={\beth }_r(\kappa {)}^{+}$. Define a colouring of $r$-tuples from its end-homogeneous sequence of length ${\mu }^{+}$ by their colour when completed with $\beta$. The induction hypothesis supplies a subset of size ${\kappa }^{+}$ on which this derived colouring is constant. Every original $(r+1)$-tuple from that subset has the derived colour of its first $r$ entries, and is therefore monochromatic. This completes the proof.

The unrestricted infinite-exponent situation is very different under AC. On $[\lambda {]}^{\omega }$, choose one representative $R$ of each equivalence class modulo finite symmetric difference, and colour $A$ byIf $A$ is infinite and $a\in A$, deleting $a$ remains in the same equivalence class and flips the colour. Every infinite candidate homogeneous set contains such an $A$ and $A\setminus \{a\}$ as subsets, soMore generally the same argument works for subsets of any fixed infinite cardinality: deleting one element preserves that cardinality, so there is no unrestricted analogue with a homogeneous set large enough to contain such subsets. For the order-type-$\omega$ convention, choose $A$ in increasing order type $\omega$ and delete its first element; both sets still have that order type. Thus the distinction from the finite-arity theorem is genuine, not merely a notational ambiguity. This argument uses choice of representatives and is not a claim about every definability-restricted infinite-arity colouring.

Let $K_s$ be the finite approximation to the halting problem obtained by running the first $s$ programs for $s$ steps, so $K_s\subseteq K_{s+1}$ and $K={\bigcup }_s{K}_s$ is not computable. For $x<y<z$, define the recursive triple colouring with no computable infinite homogeneous set byThis is a total computable function. Here homogeneous sets are required to be infinite: finite homogeneous sets certainly exist. An infinite homogeneous $H$ cannot have colour one. Fix $x\in H$; the finite approximation below $x$ eventually stabilizes, so two sufficiently large $y<z$ in $H$ give colour zero. If $H$ has colour zero, choose $x<y$ in $H$ with $x\ge e$. For arbitrarily large $z\in H$, homogeneity gives $K_y\cap [0,x]=K_z\cap [0,x]$, and hence $K_y\cap [0,x]=K\cap [0,x]$. Thus $H$ computes membership of $e$ in $K$. A computable infinite $H$ would make the halting problem computable, a contradiction.

For the uncountable partition relation, the Erdős-Rado theorem for finite arities states that for every infinite cardinal $\kappa$ and integer $n\ge 1$,The case $n=1$ is the pigeonhole principle: a union of $\kappa$ sets of size at most $\kappa$ cannot have size ${\kappa }^{+}$. Suppose the assertion holds for $n-1$. Put $\mu ={\beth }_{n-2}(\kappa )$ and $\lambda =(2^{\mu }{)}^{+}$, and let $c:[\lambda {]}^n\to \kappa$. We give the closed elementary-submodel construction of an end-homogeneous sequence, which avoids intersecting a decreasing family of reservoirs at a limit stage.

Take a sufficiently large regular $\chi$ and an elementary substructure $M\prec H_{\chi }$ with $|M|=2^{\mu }$, containing $c,\lambda$ and all ordinals below ${\mu }^{+}$, and closed under sequences of length at most $\mu$. Such an $M$ is obtained by ${\mu }^{+}$ successive Skolem hull closures: $(2^{\mu }{)}^{\mu }=2^{\mu }$, and the regularity of ${\mu }^{+}$ puts any at-most-$\mu$-long sequence from the union inside one stage. Put $\beta =\sup (M\cap \lambda )<\lambda$. The set $M\cap \lambda$ has no greatest element, since taking an ordinal successor is definable in $M$, so $\beta \notin M$.

Recursively choose an increasing sequence $⟨x_{\xi }:\xi <{\mu }^{+}⟩$ in $M\cap \lambda$. At stage $\xi$, its earlier set $A$ has size at most $\mu$, and the colour table $g(u)=c(u\cup \{\beta \})$ on $[A{]}^{n-1}$ has size at most $\mu$. Both $A$ and this table belong to $M$ by its closure. The setbelongs to $M$ and is nonempty because it contains $\beta$. Elementarity supplies $x_{\xi }\in X\cap M$. Consequently the colour of each $n$-tuple from the resulting sequence depends only on its first $n-1$ entries. The induction hypothesis applied to these entries gives a homogeneous subsequence of size ${\kappa }^{+}$, proving the result.

Infinite exponents behave differently with the axiom of choice. On the countably infinite subsets of any infinite cardinal $\lambda$, choose a representative of each equivalence class modulo finite symmetric difference. Colour a set $A$ by the parity of $|A△R_A|$. Removing one point flips its colour. Every infinite proposed homogeneous set contains an increasing sequence of order type $\omega$, and that sequence and its tail have opposite colours. Thus the finite-symmetric-difference colouring of infinite subsets gives $\lambda /⟶(\omega {)}_2^{\omega }$, whether the domain consists of all countably infinite subsets or only those of order type $\omega$. There is no unrestricted infinite-arity counterpart to the displayed finite-arity theorem in ZFC.

For an infinite cardinal $\rho$ put ${\beth }_0(\rho )=\rho$ and ${\beth }_{n+1}(\rho )=2^{{\beth }_n(\rho )}$. The Erdős-Rado theorem for finite arities isThe partition relation requires a homogeneous subset of order type ${\rho }^{+}$ for every coloring of $(n+1)$-element subsets by at most $\rho$ colors. In particular it gives uncountable homogeneous sets. The case $n=0$ is the infinite pigeonhole principle: a union of $\rho$ sets each of size at most $\rho$ cannot have size ${\rho }^{+}$.

We give the induction step by a closed elementary-submodel construction of an end-homogeneous sequence. Let $\mu$ be infinite, $\theta =(2^{\mu }{)}^{+}$, and $c:[\theta {]}^{r+1}\to \rho$ with $\rho \le \mu$. Choose a sufficiently large regular $\chi$ and an elementary submodel $M\prec H_{\chi }$ with $c,\theta \in M$, all ordinals below ${\mu }^{+}$ in $M$, $|M|=2^{\mu }$, and closure under externally given sequences of length at most $\mu$. To construct it, take ${\mu }^{+}$ successive elementary Skolem-hull closures, at each step including all such sequences from the preceding stage. Cardinality stays $2^{\mu }$ because $(2^{\mu }{)}^{\mu }=2^{\mu }$. In the final union every sequence of length at most $\mu$ has all its entries in some earlier stage, by regularity of ${\mu }^{+}$, and so was included at the next stage.

Put $\beta =\sup (M\cap \theta )$. Regularity of $\theta$ gives $\beta <\theta$, and $\beta \notin M$ since otherwise its successor would contradict the definition of the supremum. Recursively, for $\alpha <{\mu }^{+}$ choose $x_{\alpha }\in M\cap \theta$ above all earlier $x_{\xi }$ and satisfyingThere are at most $\mu$ constraints. Their parameters and their colors belong to $M$, and closure puts their complete code in $M$. The point $\beta$ witnesses their simultaneous satisfiability in $H_{\chi }$; elementarity supplies a witness in $M$. This gives an increasing end-homogeneous sequence of length ${\mu }^{+}$: on it, the color of an $(r+1)$-tuple depends only on the first $r$ entries.

For the induction from arity $n$ to $n+1$, take $\mu ={\beth }_{n-1}(\rho )$ and $r=n$. Color the $n$-tuples of the resulting sequence by their common color with a later point, equivalently by their color with $\beta$. Its index order has type ${\mu }^{+}={\beth }_{n-1}(\rho {)}^{+}$, so the induction hypothesis supplies a homogeneous index set of type ${\rho }^{+}$. The original $(n+1)$-tuples on those indices have that same color. This completes the proof without substituting the theorem's name for its induction.

A useful ordinal partition-bound function isIt is total: choose an infinite cardinal $\rho \ge |\alpha |$ with ${\rho }^{+}>\alpha$; the pairs case supplies $(2^{\rho }{)}^{+}$ with the required homogeneous order type for all these color numbers. It is nondecreasing and satisfies $f(\alpha )\ge \alpha$. Start iterating $f$ and take a supremum $\kappa$ at a limit stage. If the increasing iterates do not attain that supremum, then for every $\alpha <\kappa$ some iterate $a_{\xi }$ satisfies $\alpha \le a_{\xi }<\kappa$, andIf the iterates have already stabilized, their supremum is a fixed point directly. Thus the relevant nontrivial case is an uncountable cardinal $\kappa$ closed below itself under $f$.

Such closure implies that $\kappa$ is a strong limit. Suppose $\lambda <\kappa$ is infinite and $\kappa \le 2^{\lambda }$. Take distinct binary strings of length $\lambda$, indexed in order by $\kappa$, and color a pair by its first differing coordinate. No three strings are homogeneous: three bits cannot be pairwise different at the same coordinate. Closure would give $f(\lambda +1)<\kappa$, and its restriction would have a homogeneous subset of order type $\lambda +1$ in $\lambda$ colors, a contradiction. Hence $2^{\lambda }<\kappa$; finite exponents are harmless for an uncountable $\kappa$.

Use the usual tree property: every set-theoretic tree of height $\kappa$ with nonempty levels of cardinality below $\kappa$ has a cofinal branch. For an uncountable cardinal satisfying this all-set-theoretic trees convention, $\kappa$ must be regular. If it were singular with cofinality $\tau <\kappa$, attach to one root $\tau$ chains whose lengths increase cofinally to $\kappa$. Every level has at most $\tau$ nodes, the height is $\kappa$, and no branch is cofinal. This contradiction proves regularity. Combined with the preceding closure argument it proves that the cardinal under discussion is strongly inaccessible.

For any $c:[\kappa {]}^2\to \nu$, $0<\nu <\kappa$, make a separated set-theoretic tree of functions. Its level $\alpha$ consists of the functions $t:\alpha \to \nu$ realized as $t(\xi )=c(\{\xi ,\beta \})$ for some $\beta \ge \alpha$, with $\beta <\kappa$. Order these functions by restriction. Levels are nonempty and have size at most ${\nu }^{|\alpha |}<\kappa$, using the strong-limit property. The tree property gives a branch $b:\kappa \to \nu$. Recursively select $x_{\eta }$ for $\eta <\kappa$, larger than all earlier selections, whose coloring function agrees with $b$ through a level above those earlier selections; regularity allows that level to remain below $\kappa$, and its node has a realizing point. Then $c(\{x_{\xi },x_{\eta }\})=b(x_{\xi })$ for $\xi <\eta$. One of the fewer-than-$\kappa$ colors occurs on $\kappa$ selected points, by regularity. These points are homogeneous, proving $\kappa \to (\kappa {)}_{\nu }^2$ for every $\nu <\kappa$. ConsequentlyA strictly increasing countable iteration has a supremum of countable cofinality, so it cannot meet this regular set-theoretic tree-property condition; no continuity of $f$ has been assumed.

The final printed assertion needs its convention specified. The usual tree property alone does not imply strong inaccessibility; it can consistently hold at successor cardinals. In the argument just given, strong inaccessibility follows from function closure together with that set-theoretic tree property. There is also a stronger branching form of the tree property for which the assertion holds literally: require a cofinal branch in every separated rooted height-$\kappa$ set-theoretic tree whose nodes each have fewer than $\kappa$ immediate successors, without restricting level sizes. The singular-chain example proves regularity under this convention too. If $2^{\lambda }\ge \kappa$ for $\lambda <\kappa$, take the full binary set-theoretic tree through level $\lambda$, choose $\kappa$ distinct nodes on that level, and attach to its $\xi$th chosen node a chain of length $\xi$, for $\xi <\kappa$. It has height $\kappa$ and at most two successors per node, but every branch has length below $\kappa$. Thus this branching property implies the strong-limit condition and hence strong inaccessibility. At a strongly inaccessible cardinal it agrees, for separated set-theoretic trees, with the usual level-size convention: regularity bounds the union of fewer than $\kappa$ successor sets, and strong-limit arithmetic bounds the possible predecessor sequences at limit levels.