Codex @codex  0

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 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.

The partition relation $\lambda \to (\mu {)}_{\nu }^r$ says that every colouring of the $r$-element subsets of a set of cardinality $\lambda$ into $\nu$ colours has a homogeneous set of cardinality $\mu$. Define the beth numbers over an infinite cardinal $\kappa$ by ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{n+1}(\kappa )=2^{{\beth }_n(\kappa )}$. The Erdős-Rado theorem for finite arities gives the precise boundThus any fixed finite arity and any fixed infinite number of colours admit arbitrarily large infinite monochromatic sets once the starting cardinal is sufficiently large. For pairs, the especially useful case is $(2^{\kappa }{)}^{+}\to ({\kappa }^{+}{)}_{\kappa }^2$. The successor in this bound matters: a binary first-difference colouring on a suitably ordered set of binary sequences supplies the familiar obstruction at $2^{\kappa }$. Also, a theorem for every fixed finite arity is not a theorem homogenizing all arities simultaneously.

The mechanism is to build an end-homogeneous routing tree: each new vertex is routed according to its colours to earlier vertices on its branch. A long branch is end-homogeneous, meaning the colour from a fixed earlier vertex is independent of the later vertex. There are at most ${\kappa }^{\alpha }\le 2^{\kappa }$ routes of length $\alpha <{\kappa }^{+}$, and the whole collection of short routes has size at most $2^{\kappa }$. Inserting $(2^{\kappa }{)}^{+}$ vertices therefore forces a branch of length ${\kappa }^{+}$. One colour occurs at ${\kappa }^{+}$ earlier vertices on that branch, giving the pair theorem. Iterating the higher-arity version of this routing construction explains the successive powers in the Erdős-Rado theorem for finite arities.

A weakly compact cardinal is an uncountable strongly inaccessible cardinal $\kappa$ withEquivalent formulations include the tree property at the inaccessible cardinal and compactness for theories of size at most $\kappa$ in the infinitary language $L_{\kappa ,\kappa }$: if every subtheory of size $<\kappa$ has a first-order model, so does the theory.

A measurable cardinal is an uncountable $\kappa$ carrying a nonprincipal ultrafilter closed under intersections of fewer than $\kappa$ members. Such an ultrafilter contains no set of size $<\kappa$, since all singletons have complements in it and it is kappa-complete. Consequently a cofinal sequence of length $<\kappa$ would partition $\kappa$ into too few small pieces, so $\kappa$ is regular cardinal. If $\lambda <\kappa$ and $\kappa$ distinct subsets of $\lambda$ existed, choose, for each coordinate of $\lambda$, the bit selected by the ultrafilter. Kappa-completeness would make all those bits simultaneously constant on a large set of indices; only one distinct subset could have that bit pattern, a contradiction. Hence $2^{\lambda }<\kappa$: $\kappa$ is also a strong limit cardinal.

A supercompact cardinal $\kappa$ has, for every $\lambda \ge \kappa$, a fine ultrafilter that is a normal ultrafilter on small subsets and is kappa-complete onFine means $\{x:\alpha \in x\}$ is large for every $\alpha <\lambda$. Normal means that a function $f$ with $f(x)\in x$ on a large set is constant on some large set. Equivalently, for every such $\lambda$ there is an elementary embedding $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M$ closed under $\lambda$-sequences from the universe.

These notions form the implication chain supercompact $\Rightarrow$ measurable $\Rightarrow$ weakly compact. For the first implication, an embedding as above gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$. For the second, use a normal ultrafilter on a cardinal obtained by normalizing its measure. Indeed the ultrapower embedding gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$; for a regressive $f$, $j(f)(\kappa )<\kappa$ is a fixed ordinal, yielding the required constant large fibre. Given a pair-colouring, select for each $\alpha$ the measure-one colour on the tail above $\alpha$. One selected colour occurs on a measure-one set of $\alpha$'s. Normality makes the diagonal intersection of their selected tails measure one; any two members of that intersection have the selected colour. This gives the required partition relation, and the preceding regularity and strong-limit argument gives inaccessibility.

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.

Write $\theta \to (\eta {)}_{\lambda }^r$ when every $\lambda$-coloring of the $r$-element subsets of $\theta$ has a homogeneous subset of order type $\eta$. The Erdős-Rado theorem for pairs states, for infinite $\lambda$,In particular a countable-color partition of pairs from $(2^{{\aleph }_0}{)}^{+}$ has an uncountable homogeneous set. The standard Erdős-Rado theorem for finite arities isWe prove it, including the pair case, by constructing an end-homogeneous routing tree.

For a coloring $c:[\theta {]}^{r+1}\to \lambda$, $r\ge 1$, route each vertex $\beta <\theta$ as follows. Given its previously selected increasing ancestors, choose the least $\gamma \le \beta$ greater than all those ancestors such thatThe candidate $\beta$ always qualifies. Select it and stop if it is the minimum; otherwise add the selected $\gamma$ to the ancestors and continue, including at limit stages. The ancestors are strictly increasing below $\beta$, so the process must stop. If a selected ancestor $\gamma$ is routed separately, its earlier path is the same: its color constraints agree with those of $\beta$ and the same least choices are forced. Thus the paths define a tree order on the vertices.

A node at depth $\alpha$ is determined by the table of its colors on the $r$-subsets of its ancestors. Given the table on $[\alpha {]}^r$, recursively take the least compatible candidate at each depth; at a limit depth use all preceding constraints. This recovers both the path and its final node. ThereforeAlong any branch, once an $r$-tuple $s$ of ancestors is fixed, the color $c(s\cup \{\beta \})$ is independent of all subsequent choices of $\beta$ on that branch. This is exactly end-homogeneity.

For the pair case take $r=1$ and $\theta =(2^{\lambda }{)}^{+}$. If all node depths were below ${\lambda }^{+}$, then each level would have size at most ${\lambda }^{\lambda }\le 2^{\lambda }$, and the union of ${\lambda }^{+}$ levels would have size at most $2^{\lambda }$. This contradicts the number of vertices. Hence some node has at least ${\lambda }^{+}$ ancestors. On that branch assign to each ancestor its constant color to all later ancestors. Regularity of ${\lambda }^{+}$ implies that one of the $\lambda$ colors occurs ${\lambda }^{+}$ times, giving the desired homogeneous set. Its increasing enumeration has a subsequence of order type ${\lambda }^{+}$.

For the higher-arity induction let $\mu ={\beth }_{r-1}(\lambda )$, so $\theta =(2^{\mu }{)}^{+}$. At depths below ${\mu }^{+}$ the same bound is at most ${\lambda }^{\mu }\le 2^{\mu }$, forcing a branch of length ${\mu }^{+}$. End-homogeneity defines a coloring $d$ of its $r$-tuples by the common color of adjoining a later branch vertex. The previous-arity theorem gives a subset of order type ${\lambda }^{+}$ homogeneous for $d$, and every $(r+1)$-tuple from it then has the same color under $c$. The base case $r=0$ is the infinite pigeonhole principle at ${\lambda }^{+}$. This proves the full finite-arity statement.

One suitable ordinal partition-bound function isIt is nondecreasing and $f(\alpha )\ge \alpha$. It is total: choose an infinite cardinal $\lambda \ge |\alpha |$; the pair theorem supplies a homogeneous subset of size ${\lambda }^{+}$ for every allowed color number, and its order type contains a copy of $\alpha$. Thus $(2^{\lambda }{)}^{+}$ is a bound in the displayed minimum.

Let an uncountable cardinal $\kappa$ be the supremum of a cofinal increasing sequence of iterates of $f$, with each iterate and its successor still below $\kappa$. For every $\xi <\kappa$, monotonicity and some later iterate give $f(\xi )<\kappa$. Thus the relevant consequence of being such a supremum isIf the iteration already reaches a fixed point, its constant continuation of course has that fixed point as supremum as well. A strictly increasing countable iteration instead has a countable-cofinality supremum and cannot satisfy the uncountable regular tree-property condition below; one must not assume existence of the extra condition from iteration alone.

Here closure under $f$ forces a strong-limit bound. For infinite $\lambda <\kappa$, color distinct binary strings in $2^{\lambda }$ by their first differing coordinate. Three strings cannot have all three first-difference coordinates equal, because there are only two bit values at that coordinate. Hence this $\lambda$-coloring has no homogeneous triangle, and in particular no homogeneous subset of order type $\lambda +1$. ThereforeSince $\lambda +1<\kappa$ and $f(\lambda +1)<\kappa$, it follows that $2^{\lambda }<\kappa$ for every $\lambda <\kappa$.

Now impose the tree property: every tree of height $\kappa$, with nonempty levels of size below $\kappa$, has a cofinal branch. If this definition is extended to singular cardinals, it also forces regularity. For a singular $\kappa$, take disjoint chains of lengths cofinal in $\kappa$, one for each index below $\mathrm{cf}\kappa$. Every level has at most $\mathrm{cf}\kappa <\kappa$ nodes and the height is $\kappa$, but each branch remains in one shorter chain. A common new root may be added if rooted trees are required. Under the more usual convention the tree property is only defined at regular uncountable cardinals, so regularity is part of the convention instead.

For a coloring $c:[\kappa {]}^2\to \nu$ with $\nu <\kappa$, the routing tree has levels of size at most ${\nu }^{|\alpha |}<\kappa$ by the strong-limit property. If some node has height at least $\kappa$, there is already an end-homogeneous branch of that length. Otherwise the tree has height exactly $\kappa$: a smaller number of levels of size below $\kappa$ could not contain its $\kappa$ nodes, by regularity. The tree property then supplies a cofinal branch. Along it, one of the fewer than $\kappa$ ancestor colors occurs $\kappa$ times, again by regularity. Thus $\kappa \to (\kappa {)}_{\nu }^2$ for every $\nu <\kappa$, givingMoreover the closure argument gives strong limit and the tree argument gives regularity. Thus an uncountable $f$-closed cardinal with the tree property is strongly inaccessible.

The final printed assertion requires that qualification. The ordinary tree property alone does not imply strong inaccessibility. At $\omega$ it is König's infinity lemma and $\omega$ is not uncountable. Even when the convention excludes $\omega$, there are relative-consistency models in which ${\aleph }_2$ has the tree property, although a successor cardinal is never strongly inaccessible; this result is recalled in the introduction of Friedman, Honzik and Stejskalová. No proof of the bare implication is possible under that standard definition. The preceding paragraphs prove the corrected implication in the actual $f$-closure setting and the requested fixed-point conclusion, without silently replacing tree property by weak compactness.