Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 16J (Logic & Set Theory)

A choice function on a family $\mathcal{A}$ of nonempty sets satisfies $c(A)\in A$. Zermelo's theorem says every set has a total order under which every nonempty subset has a least element.

Choose from every nonempty subset of $X$. By transfinite recursion setwhile the remainder is nonempty. This cannot continue through Hartogs theorem's ordinal $h(X)$, since that would inject $h(X)$ into $X$. It therefore exhausts $X$ at some ordinal, and the selection order well-orders $X$.

Hessenberg's theorem in ZF states that every infinite well-orderable cardinal satisfies $\kappa \times \kappa =\kappa$; equivalently $|\alpha \times \alpha |=|\alpha |$ for every infinite ordinal $\alpha$.

Choice well-orders every infinite $X$, so Hessenberg gives $X^2\cong X$. Conversely assume this square identity for every infinite set. For arbitrary $X$, form the disjoint union $Y=X\bigsqcup h(X)$. A pairing $Y^2\cong Y$, together with the well-order on $h(X)$, yields by the standard tracing/comparison argument an injection either $h(X)\to X$ or $X\to h(X)$. The first is forbidden by Hartogs theorem, so the second well-orders $X$. This is Tarski cardinal-square theorem, and hence choice follows.