Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 19 / 2

In the usual tail-normalized version, an Ulam matrix on omega-one is a family $A_{\alpha ,n}$ such that, for each $\alpha <{\omega }_1$, the sets indexed by $n<\omega$ partition the tail $(\alpha ,{\omega }_1)$, while for each fixed $n$ the sets indexed by $\alpha <{\omega }_1$ are pairwise disjoint. Empty cells are allowed; harmless bounded-tail variants give the same applications.

For a concrete realization, choose injections $e_{\beta }:\beta \to \omega$ for every countable ordinal $\beta$, and setFor fixed $\alpha$ each $\beta >\alpha$ chooses exactly one $n$; for fixed $n$, injectivity of $e_{\beta }$ prevents one $\beta$ from belonging to two cells. This verifies the two matrix conditions explicitly.

König theorem for cardinal numbers states that if ${\kappa }_i<{\lambda }_i$ for each $i\in I$, then ${\sum }_i{\kappa }_i<{\prod }_i{\lambda }_i$. Its cofinality formulation gives, for every infinite cardinal $\kappa$,Taking a cofinal sequence of smaller cardinals in $\kappa$ and comparing their sum with the product of their successors gives this inequality. Another standard consequence, for infinite $\lambda$ and $\kappa \ge 2$, isIndeed, if $\mu =\mathrm{cf}({\kappa }^{\lambda })\le \lambda$, the preceding inequality at ${\kappa }^{\lambda }$ would contradict $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \mu }={\kappa }^{\lambda }$.

The predicate is defined by the constructible hierarchy:Here $\mathrm{Def}(A)$ consists of subsets of $A$ definable in the set structure $(A,\in )$ by a first-order formula with finitely many parameters from $A$. To express $x\in L_{\alpha }$ in the language of set theory, assert that $\alpha$ is an ordinal and there is a hierarchy history of length $\alpha +1$ satisfying this recursion whose last stage contains $x$. Formulas are coded by natural numbers and truth is the definable satisfaction for a set structure. Transfinite recursion gives a unique history. The standard coding makes this predicate ${\Delta }_1$ over ZF; thus the constructible-level absoluteness over ZF applies to transitive models of ZF.

The bounding number $\mathfrak{b}$ is the least size of an unbounded family in $({\omega }^{\omega },{\le }^{\ast })$. The almost disjointness number $\mathfrak{a}$ is the least size of an infinite maximal almost disjoint family on omega of infinite subsets of $\omega$. Requiring the family to be infinite excludes trivial finite maximal partitions.

A countable family $\{f_i:i<\omega \}$ is bounded by $g(n)=1+{\max }_{i\le n}{f}_i(n)$. Thus ${\aleph }_1\le \mathfrak{b}$.

Suppose an infinite almost disjoint family on omega $\mathcal{A}$ has size less than $\mathfrak{b}$. Choose distinct members $A_n$ and put $C_n=A_n\setminus {\bigcup }_{i<n}{A}_i$. These are infinite and pairwise disjoint. For each $B\in \mathcal{A}$, define $h_B(n)=\max ((B\cap C_n)\cup \{0\})$ whenever the intersection is finite. If $B=A_n$ at the exceptional index $n$, set $h_B(n)=0$. These are the only possible infinite intersections. A single $g$ eventually dominates every $h_B$, because there are fewer than $\mathfrak{b}$ of them. Pick $x_n\in C_n$ with $x_n>g(n)$ and put $X=\{x_n:n<\omega \}$.

For $B$ not among the selected $A_n$, only finitely many $x_n$ can lie in $B$. The same is true for $B=A_j$, with its single exceptional index $j$ ignored. Thus $X$ is infinite and almost disjoint from every member of $\mathcal{A}$, so the family was not maximal. This bounding-to-almost-disjointness inequality proves $\mathfrak{b}\le \mathfrak{a}$.

Finally start with an infinite pairwise disjoint family and use Zorn's lemma to extend it to a maximal almost disjoint family on omega. It is a family of subsets of $\omega$, so has cardinality at most $2^{{\aleph }_0}$. Therefore

Fix $a,\vec{p}\in L$ and a formula $\theta (x,\vec{p})$. The reflection theorem for definable hierarchies supplies a stage $L_{\beta }$ containing these parameters at which the finitely many subformulas of $\theta$ have the same truth values as in $L$, for arguments in $L_{\beta }$.

This reflection can be proved in the ambient ZF without presupposing Axiom schema of separation in $L$: starting at a stage containing the parameters, collect for each relevant existential subformula and every tuple in the current stage the least constructible stage in which a witness occurs, whenever a witness exists in $L$. Ambient Axiom schema of replacement bounds these ordinals. Iterate these witness-stage bounds for $\omega$ steps and take their supremum. Induction on subformulas gives the required finite reflection at the resulting union stage. Only the least stage is chosen, so no ambient axiom of choice is needed.

Since $L_{\beta }$ is transitive and contains $a$, the desired separated subset isIt is definable over $L_{\beta }$ with parameters there, so $b\in \mathrm{Def}(L_{\beta })=L_{\beta +1}\subset L$. Reflection gives $b=\{x\in a:{\theta }^L(x,\vec{p})\}$. Hence ZF proves every Axiom schema of separation instance relativized to $L$. This is a direct Separation proof in the constructible universe, not an appeal to the assertion being proved.

Use the transitive-model convention for “standard” in this assertion: the domain is a transitive set and membership is actual membership. A standard membership model of set theory without transitivity is a weaker notion and would not justify the asserted absoluteness. Ordinalhood is bounded-formula absolute, so the internal ordinals are precisely $A\cap \mathrm{Ord}$. Satisfaction for a set structure is absolute between transitive ZF models containing that structure: the domain, finite parameter tuples, formula codes and the recursive truth clauses are the same. Equivalently one may use the ${\Delta }_1$ absoluteness of the predicate defining $L_{\alpha }$.

Transfinite induction now gives $L_{\alpha }^{\mathbb{A}}=L_{\alpha }$ for each ordinal $\alpha \in A$. At successors both computations use the same definable subsets of the same set structure; at limits they take the same union over all smaller ordinals, which belong to $A$ by transitivity. ThusFor a set-sized model of ordinal height $\theta$, this is $L_{\theta }$. The restriction to actual ordinals makes the printed union precise. Mere well-foundedness of a nontransitive membership substructure would not justify these absoluteness steps; transitivity is the intended standard-model convention.

Let $N$ be any transitive class model of ZF containing every ordinal. By part (b), all its internally computed constructible levels are the actual levels, and each belongs to, and is contained in, $N$. Their union therefore gives $L\subseteq N$. Using the permitted fact that $L\models \mathrm{ZF}$, and that $L$ itself contains every ordinal, we concludeThe word class matters: a set cannot contain every ordinal. Set-sized standard models instead contain their own truncated constructible universe as described in part (b).

Let $E=\{\alpha <\kappa :\mathrm{cf}(\alpha )=\omega \}$. This set is stationary: in any club set, choose a strictly increasing countable sequence and take its supremum, which lies in the club set and has cofinality $\omega$. For each $\alpha \in E$ choose an increasing cofinal sequence $c_{\alpha }:\omega \to \alpha$.

Fix $\beta <\kappa$. For every $\alpha \in E$ above $\beta$, some $c_{\alpha }(n)$ exceeds $\beta$. Partition this stationary tail by the least such $n$. A countable union of nonstationary sets is nonstationary, because fewer than $\kappa$ club sets have club filter completeness, so some cell is stationary. On it the regressive function $\alpha \mapsto c_{\alpha }(n)$ has, by Fodor lemma, a stationary fiber at a value $\gamma >\beta$.

Let $I_n=\{\gamma <\kappa :\{\alpha \in E:c_{\alpha }(n)=\gamma \}\text{ is stationary}\}$. The preceding argument says ${\bigcup }_n{I}_n$ is unbounded in $\kappa$. Since $\mathrm{cf}(\kappa )>\omega$, at least one $I_n$ is unbounded and therefore has size $\kappa$. Its fibers are pairwise disjoint stationary sets. Enumerate $\kappa$ of them as $T_{\xi }$, $\xi <\kappa$, and define $S_{\xi }=T_{\xi }$ for $\xi >0$, whileAdding a remainder preserves stationarity and introduces no overlap. ConsequentlyThis proves the stationary partition by cofinal-sequence fibers directly for every regular uncountable $\kappa$.