Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 19 / 3

For a nonzero limit ordinal $\delta$, a subset $C\subseteq \delta$ is a club set if it is unbounded in $\delta$ and contains every one of its limit points below $\delta$. A subset $S\subseteq \delta$ is stationary ifThis defines stationarity in a limit ordinal. The regular uncountable case is the usual stationary set setting; results such as Fodor lemma require that additional hypothesis, rather than an arbitrary limit ordinal.

A set-theoretic tree is a partial order for which the strict predecessors of every node are well-ordered by the tree order. The height of a node is that predecessor order type, and $T_{\alpha }$ is the set of nodes of height $\alpha$. Under the ordinary height-and-width definition, a kappa-tree satisfies

For an arbitrary cardinal in this definition one must distinguish it from additional conventions such as being well-pruned, normal or splitting. Splitting means that every node has two incompatible extensions; it is not implied by the height-and-width clauses. This distinction is material in Question 5(ii)(a).

The club principle predicts a cofinal countable ladder contained in every uncountable subset of ${\omega }_1$. More precisely, $♣$ asserts that there is a sequence $⟨A_{\delta }:\delta \in \lim ({\omega }_1)⟩$ such that each $A_{\delta }$ is cofinal in $\delta$ with order type $\omega$, and every uncountable $X\subseteq {\omega }_1$ contains at least one entire $A_{\delta }$. It predicts a countable ladder contained in $X$, rather than predicting $X\cap \delta$ exactly. The latter is the stronger kind of guessing in the diamond principle.

For every $\beta <{\omega }_1$, choose an injection $e_{\beta }:\beta \to \omega$. Define the Ulam matrix on omega-one byFor a fixed $\alpha$, every $\beta >\alpha$ belongs to exactly one of these sets, so their union is the entire tail $(\alpha ,{\omega }_1)$. Its complement is the countable ordinal $\alpha +1$. For distinct $\alpha ,{\alpha }^{\prime }$ and fixed $n$, membership in both sets would give $e_{\beta }(\alpha )=e_{\beta }({\alpha }^{\prime })=n$ for some $\beta$ above both, contradicting injectivity. This verifies both requested properties.

To prove unboundedness, begin above any prescribed ordinal with ${\gamma }_0<\lambda$ and choose a strictly increasing sequence so thatThis upper bound is below $\lambda$: there are fewer than $\lambda$ countable sets in the union, and $\lambda$ is regular and uncountable. Put $\delta ={\sup }_m{\gamma }_m<\lambda$. For any $\alpha <\delta$, choose $m$ with $\alpha <{\gamma }_m$; then $B(\alpha )\subseteq {\gamma }_{m+1}\subseteq \delta$. Thus $\delta \in E$.

For closedness, suppose $\delta <\lambda$ is a limit point of $E$. Given $\alpha <\delta$, choose $\eta \in E$ with $\alpha <\eta <\delta$. Then $B(\alpha )\subseteq \eta \subseteq \delta$. Therefore $\delta \in E$ as well. Hence $E$ is a club set in $\lambda$. This is the club of closure points for countable set-valued functions.

Write ${◊}_S^{\prime }$ for the countable-family assertion in the PDF; its prime is not a superscript $c$. A single stationary diamond at a regular cardinal sequence gives such families by taking singletons, so ${◊}_S\Rightarrow {◊}_S^{\prime }$.

Conversely enumerate each countable family as $E_{\alpha }(n)$, $n<\omega$, padding finite families and allowing the empty set as a default. Fix a bijection $\pi :\lambda \times \omega \to \lambda$. The previous part applied to $B(\xi )=\{\pi (\xi ,n):n<\omega \}$ gives a club set $D$ on which $\pi [\alpha \times \omega ]\subseteq \alpha$. Define, for each $n$, a single candidate sequenceSuppose no candidate sequence witnesses ${◊}_S$. For each $n$ choose $X_n\subseteq \lambda$ and a club set $C_n$ such that $D_{\alpha }^n\ne X_n\cap \alpha$ for every $\alpha \in S\cap C_n$. Code all the counterexamples intoThe countable-family hypothesis guesses $X$ on a stationary set. Choose a guessing $\alpha$ in the club set $D\cap {\bigcap }_n{C}_n$, and choose $n$ with $E_{\alpha }(n)=X\cap \alpha$. For every $\xi <\alpha$, closure under $\pi$ givesThus $D_{\alpha }^n=X_n\cap \alpha$, contradicting $\alpha \in C_n$. At least one candidate is a diamond sequence, provingThis is the countable-family diamond equivalence, for every regular uncountable $\lambda$ and stationary $S\subseteq \lambda$.

There is a cofinal branch. We give a proof that does not require distinct limit-level nodes to have different predecessor chains.

The set $S=\{\alpha <\lambda :\mathrm{cf}(\alpha )=\kappa \}$ is stationary. Indeed a strictly increasing continuous $\kappa$-sequence in any club set has supremum in that club set, below $\lambda$, of cofinality $\kappa$. At each $\alpha \in S$, there are fewer than $\kappa$ pairs of nodes on $T_{\alpha }$. For every pair whose predecessor chains below $\alpha$ differ, choose a height where they differ. Since $\mathrm{cf}(\alpha )=\kappa$, all these heights are bounded by some ${\beta }_{\alpha }<\alpha$. Consequently nodes in $T_{\alpha }$ having the same predecessor at ${\beta }_{\alpha }$ have identical predecessor chains below $\alpha$.

The Fodor lemma states that a regressive function on a stationary subset of a regular uncountable cardinal is constant on a stationary subset. Applying it here, ${\beta }_{\alpha }$ has a constant value $\beta$ on a stationary subset $S^{\prime }$. Choose $t_{\alpha }\in T_{\alpha }$ for each $\alpha \in S^{\prime }$. The level $T_{\beta }$ has fewer than $\kappa <\lambda$ nodes. Partitioning $S^{\prime }$ according to the predecessor of $t_{\alpha }$ at height $\beta$, one fiber $S^{\prime \prime }$ is stationary, since the union of fewer than $\lambda$ nonstationary sets is nonstationary. Let its common predecessor be $t$.

For $\alpha <{\alpha }^{\prime }$ in $S^{\prime \prime }$, the predecessor of $t_{{\alpha }^{\prime }}$ at level $\alpha$ and $t_{\alpha }$ have the same predecessor $t$ at level $\beta$. Their chains below $\alpha$ therefore agree. For each $\nu <\lambda$, choose $\alpha \in S^{\prime \prime }$ above $\nu$ and let $b_{\nu }$ be the predecessor of $t_{\alpha }$ at level $\nu$. The preceding comparison makes $b_{\nu }$ independent of that choice. The nodes $b_{\nu }$ form a chain through every level:This proves the uniformly narrow regular-height tree branch theorem. The uniform bound below the smaller regular $\kappa$ is stronger than merely bounding each level below $\lambda$.