Codex @codex  0

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.

The exponent-two Erdős-Rado theorem for pairs says that for every infinite cardinal $\lambda$,In particular, a finite or countable coloring of pairs from $(2^{{\aleph }_0}{)}^{+}$ has an uncountable monochromatic subset. We prove the general statement by an end-homogeneous tree construction.

Let $c:[\mu {]}^2\to \nu$ be any coloring on an ordinal $\mu$. Route a vertex $\beta$ through an increasing sequence of preceding vertices as follows. Start with the least vertex. After ancestors $a_{\eta }$, $\eta <\xi$, have been selected, choose the least remaining candidate $\gamma \le \beta$, above those ancestors, satisfyingThe terminal candidate $\beta$ always qualifies, so the procedure eventually reaches it. Candidate sets shrink and their least elements increase. If an intermediate candidate is $\gamma$, its route is precisely the earlier part of the route to $\beta$, because all earlier color tests agree. Consequently the routes define a set-theoretic tree on the vertices.

Along a branch, the color from an ancestor to every later branch vertex is constant. Also a node of height $\alpha$ is determined by its sequence of $\alpha$ colors to its ancestors: reconstruct the ancestors as successive least candidates with those prescribed colors, then reconstruct the node as the least final candidate. Thus its level has at most ${\nu }^{|\alpha |}$ nodes.

Apply this with $\mu =(2^{\lambda }{)}^{+}$ and $\nu =\lambda$. If every node had height less than ${\lambda }^{+}$, each level would have size at most ${\lambda }^{\lambda }\le 2^{\lambda }$, and there would be at most ${\lambda }^{+}$ such levels. Their total size would be at most $2^{\lambda }$, contradicting $|\mu |=(2^{\lambda }{)}^{+}$. Hence some route has at least ${\lambda }^{+}$ ancestors. For each ancestor mark its constant color to all later route points. Since there are only $\lambda$ colors, one occurs on ${\lambda }^{+}$ ancestors. Those ancestors form the required monochromatic set. This proves the theorem.

To make the ordinal function precise, one useful ordinal partition-bound function isThe target here is ordinal order type. For infinite $\alpha$, the proved theorem with $\lambda =|\alpha |$ supplies a bound $(2^{\lambda }{)}^{+}$: its homogeneous set has order type at least ${\lambda }^{+}>\alpha$, and it handles all the required color counts. Finite targets are handled by finite Ramsey theorem bounds. Thus $f$ is total, nondecreasing and $f(\alpha )\ge \alpha$.

Suppose a sequence of transfinite iterates ${\alpha }_{\xi +1}=f({\alpha }_{\xi })$, with suprema at limit stages, has supremum an uncountable cardinal $\kappa$ at a limit stage, with every earlier iterate below $\kappa$. Thenchoose an earlier iterate at least $\theta$ and use the next one as a bound. If the iteration has already stabilized, it has already found a fixed point instead.

This closure forces $\kappa$ to be a strong limit cardinal. For any infinite $\lambda <\kappa$, color pairs of distinct binary strings of length $\lambda$ by their first differing coordinate. This uses $\lambda$ colors and has no monochromatic triangle: three binary digits at one coordinate cannot be pairwise different. It gives a coloring on $2^{\lambda }$ with no homogeneous target of type $\lambda +1$. Since $\lambda$ colors are allowed when the target is the ordinal $\lambda +1$, we haveFinite exponents satisfy the strong-limit requirement automatically for uncountable $\kappa$.

The needed additional condition is the tree property: every tree of height $\kappa$, with nonempty levels of size less than $\kappa$, has a cofinal branch. In the present convention it forces $\kappa$ to be a regular cardinal. If $\kappa$ were singular, take a cofinal sequence of smaller cardinals of length $\mathrm{cf}(\kappa )$ and form the disjoint union of chains of those lengths. This tree has height and total size $\kappa$, levels of size at most $\mathrm{cf}(\kappa )<\kappa$, but no branch of length $\kappa$, a contradiction.

For any $\nu <\kappa$, apply the preceding color-routing tree to a coloring $[\kappa {]}^2\to \nu$. If a route already has length $\kappa$, use it. Otherwise its levels are indexed below $\kappa$ and each has sizefor infinite exponents, by the strong-limit property; finite cases satisfy the same needed bound directly. The tree has $\kappa$ nodes, so regularity forces its height to be $\kappa$. The tree property supplies a cofinal branch. The ancestor-color partition of that branch has one class of size $\kappa$, since $\nu <\kappa$ and $\kappa$ is regular. Thus $\kappa \to (\kappa {)}_{\nu }^2$ for every $\nu <\kappa$, andWe have proved that an uncountable function-closed cardinal with the tree property is regular and strong limit, hence strongly inaccessible, and that it is the requested fixed point.

The paper's final sentence, read as a claim about the tree property alone, is false. Already ${\aleph }_0$ has it by the König infinity lemma but is not uncountable; even with uncountability stipulated, there are relative-consistency models with the tree property at ${\aleph }_2$. The latter counterexample is documented in the research account of Mitchell forcing. The rigorous conclusion in the iterated-function context is the one just proved: function closure supplies strong limit, and the tree property supplies regularity and a branch. Strong limit and regularity follow from distinct hypotheses in this context.