Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 16H (Logic and Set Theory)

For a well-order $(A,r)$, define recursivelyTransfinite recursion makes $F$ an isomorphism from $(A,r)$ onto a transitive set of transitive sets, hence onto an ordinal. If two ordinals were isomorphic, the first point where the isomorphism differed from the identity would contradict preservation of their initial segments. Thus this ordinal is unique.

The ordinal $\beta$ is the ordered concatenation of its initial segment $\alpha$ and its tail $\beta \setminus \alpha$. If the tail has order type $\gamma$, this concatenation has order type $\alpha +\gamma$. Hence $\alpha +\gamma =\beta$.

Every proper initial segment of ${\omega }_1\setminus \omega$ is countable, while the whole tail is uncountable. Its order type is therefore the least uncountable ordinal itself:Equivalently, part (b) gives $\omega +\gamma ={\omega }_1$, and the unique possible uncountable initial ordinal $\gamma$ is ${\omega }_1$.

Write the nonzero ordinal in Cantor normal formwhere ${\delta }_1>\cdots >{\delta }_r$ and $0<n_i<\omega$. Taking $\delta ={\delta }_1$, $n=n_1$, andgives $\alpha ={\omega }^{\delta }n+\eta$ with $\eta <{\omega }^{\delta }$.

Use the shuffle bound: if a well-order is partitioned into subsets of order types $\xi$ and $\eta$, its order type is at most the Hessenberg natural sum $\xi \#\eta$. This follows by merging the two induced well-orders and comparing their Cantor-normal-form terms.

If both $X$ and $Y$ had order type strictly below ${\omega }^{\delta }$, each would have leading Cantor exponent below $\delta$. Their natural sum would still be below ${\omega }^{\delta }$. The shuffle bound would then givea contradiction. Thus at least one part has order type ${\omega }^{\delta }$.

The shuffle bound gives $\alpha \le \beta \#\beta$. By part (d), writeNatural addition doubles corresponding Cantor coefficients, soOn the other hand, ordinary ordinal addition absorbs each intermediate lower-order remainder, givingConsequently $\alpha <\beta +\beta +\beta$.

The stronger inequality with two copies is false. Take $\beta =\omega$, $\alpha =\omega +\omega$, let $X$ be the first block and $Y$ the second. Both have order type $\omega$, but $\alpha =\beta +\beta$.