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

By choice-function well-ordering construction, use transfinite recursion to choosewhenever the set on the right is nonempty. The chosen elements are distinct, so if this construction continued through the Hartogs theorem ordinal $h(x)$, the map $\beta \mapsto x_{\beta }$ would inject $h(x)$ into $x$, a contradiction. It therefore stops at some ordinal $\alpha <h(x)$. At the stopping stage every element of $x$ has been selected, and henceis a bijection $\alpha \to x$.

Assuming the axiom of choice, every set $x$ has such a choice function on its nonempty subsets. Transporting the membership order on $\alpha$ across the bijection well-orders $x$. Thus the axiom of choice implies the well-ordering theorem.

Apply the stated cardinal comparability principle to $x$ and its Hartogs ordinal $h(x)$. The Hartogs theorem rules out an injection $h(x)\to x$, so comparability supplies an injectionOrder $x$ by $u\prec v$ exactly when $j(u)\in j(v)$. This is the restriction of an ordinal well-order and therefore well-orders $x$. Hence every set can be well-ordered. The well-ordering theorem is equivalent to the axiom of choice: for a family of nonempty sets, well-order its union and choose the least member of each set. The comparison statement therefore implies choice.

An initial ordinal is an ordinal $\kappa$ that is not equipotent to any smaller ordinal. Equivalently, it is the least ordinal having its cardinality. The aleph numbers enumerate the infinite initial ordinals:${\aleph }_{\alpha +1}$ is the least initial ordinal greater than ${\aleph }_{\alpha }$, and at a limit $\lambda$, ${\aleph }_{\lambda }$ is the least initial ordinal greater than every ${\aleph }_{\beta }$ for $\beta <\lambda$.

Each ${\aleph }_{\alpha }$ is infinite and initial by construction. Conversely, let $\kappa$ be an infinite initial ordinal. The infinite initial ordinals below $\kappa$ form a set and therefore have an ordinal order type $\alpha$. The recursive enumeration above lists exactly those predecessors before stage $\alpha$, so its next value is ${\aleph }_{\alpha }=\kappa$.

Read literally, “has cardinality ${\aleph }_{\alpha }$” is too weak: $\omega +1$ has cardinality ${\aleph }_0$ but is not initial. The valid characterization isIf “has cardinality” in the question means “is the cardinal represented by,” this is precisely the requested statement.

This is König theorem for cardinal numbers. Since ${\kappa }_i<{\lambda }_i$, map $(i,\alpha )$ in the disjoint union to the element $s_{i,\alpha }$ of the product defined byHere $\alpha <{\kappa }_i$ implies $\alpha +1<{\lambda }_i$. The unique nonzero coordinate and its value recover $(i,\alpha )$, so this is an injection

For strictness, suppose $F$ mapped the disjoint union onto the product. For each $i$, the sethas cardinality at most ${\kappa }_i$, so it cannot exhaust ${\lambda }_i$. Choose $b_i\in {\lambda }_i\setminus A_i$. Then $b=(b_i{)}_{i\in I}$ differs from $F(i,\alpha )$ in coordinate $i$ for every $(i,\alpha )$, contradicting surjectivity. By Cantor-Schröder-Bernstein theorem, an injection in the reverse direction would combine with the displayed injection to give a bijection and hence a surjection. Therefore

Apply König theorem for cardinal numbers with $I=\omega$, ${\kappa }_i={\aleph }_i$, and ${\lambda }_i={\aleph }_{i+1}$. Standard infinite cardinal arithmetic giveswhereas every factor in the product is at most ${\aleph }_{\omega }$. Hence

Now suppose $2^{{\aleph }_{\omega }}={\aleph }_{\omega }$. The exponent laws for infinite cardinals would givecontradicting the strict inequality. Therefore