Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 25 / 5

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a nonprincipal $\kappa$-complete ultrafilter $U$: intersections of fewer than $\kappa$ members of $U$ remain in $U$. Such an ultrafilter contains no set of size less than $\kappa$. Indeed each singleton is absent, and intersecting fewer than $\kappa$ singleton complements shows that every small set's complement is in $U$. In particular every tail of $\kappa$ is in $U$.

Form the ultrapower of the universe by functions $f:\kappa \to V$, identifying functions agreeing on a member of $U$, and interpreting membership coordinatewise modulo $U$. The Łoś theorem, applied separately to each formula, makes the map $x\mapsto [c_x]$ elementary. Countable completeness makes the ultrapower well-founded: an infinite descending chain $[f_{n+1}]\in [f_n]$ would give $U$-large sets witnessing each step, whose countable intersection is nonempty; a coordinate in that intersection would give an infinite descending membership chain in the original universe. The relation is extensional and set-like, so the Mostowski collapse theorem gives a transitive class $M$ and an elementary ultrapower embedding $j:V\to M$.

For each $\alpha <\kappa$, every function $\kappa \to \alpha$ is constant modulo $U$. If no fibre were in $U$, intersecting the fewer than $\kappa$ fibre complements would give the empty set in $U$. Induction on $\alpha$ therefore shows that the collapsed ultrapower ordinal $j(\alpha )$ has precisely the elements $\beta <\alpha$, soThe identity function $\mathrm{id}:\kappa \to \kappa$ represents an ordinal below $j(\kappa )$, and every constant $\alpha <\kappa$ is below it modulo $U$, since a tail is large. ConsequentlyThus the canonical collapsed embedding is not the identity; its first moved ordinal is $\kappa$. For a general measure the identity-function class need not collapse to exactly $\kappa$; that stronger equality holds for a normal measure. The argument above needs only its lower bound.

Conversely, suppose $j:V\to M$ is elementary, $M$ is transitive, its critical point is $\kappa$, and its derived measure is a set, as for the usual definable or amenable class embeddings. DefineBecause $\kappa <j(\kappa )$, elementary preservation of complements and intersections makes this an ultrafilter. It is nonprincipal since $j(\{\alpha \})=\{\alpha \}$ for $\alpha <\kappa$. For a sequence of $\gamma <\kappa$ large sets, $j$ fixes the index ordinal $\gamma$ and takes the intersection to the intersection of their images; $\kappa$ belongs to every image and hence to the intersection. Thus $U$ is $\kappa$-complete. The set-existence qualification excludes treating an arbitrary external class map as a set parameter without justification.

For context, measurability already implies regularity and the strong-limit property. A cofinal sequence of length below $\kappa$ partitions $\kappa$ into that many bounded, hence small, pieces; completeness and their absent fibres contradict covering all of $\kappa$. If there were $\kappa$ distinct subsets of some $\lambda <\kappa$, for each coordinate choose the $U$-large side deciding its membership bit. The intersection of these $\lambda$ large sets would still be large, but all its indices would label the same subset, so it would have at most one member. This contradiction gives $2^{\lambda }<\kappa$. Thus the first moved ordinal is an uncountable strongly inaccessible cardinal, in addition to being measurable.

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.