Past exam of the logic and set theory course of the University of Oxford / 2010 / B / 6

Hartogs theorem says that for every set $A$ there is a least ordinal $h(A)$ that does not inject into $A$. This theorem requires no axiom of choice.

To prove it, collect all well-orderings of subsets of $A$. They are set-sized data, coded by pairs from $\mathcal{P}(A)$ and $\mathcal{P}(A\times A)$. Each has a unique ordinal order type, so replacement gives a set $H$ of their order types. If $\eta \in H$ and $\xi <\eta$, restricting the corresponding well-order to an initial segment shows $\xi \in H$. Hence $H$ is an ordinal. If this ordinal itself injected into $A$, its transported well-order would put $H$ among its own elements, impossible for an ordinal. Every smaller ordinal does inject by definition. Thus $h(A)=H$ has the asserted property.

The recursion printed in the source needs two boundary restrictions. Its new-row successor clause allows $\beta =\alpha$, which would assign a value at $(\alpha ,\alpha +1)$ outside the declared domain. Also, at $\alpha =0$, its row-start clause gives $g_1(0,0)=0$ while its column-start clause gives $g_1(0,0)=g_1(0,0)+1$. Taken literally, these clauses do not define a function.

The intended extension fills the new row first and the remaining new column second. Restrict the row successor clause to $\beta <\alpha$, and apply the column-start clause only when $\alpha >0$. With these two restrictions the domains are disjoint:All successors here are ordinal successors. Simultaneous transfinite induction proves a stronger result: $g_{\alpha }$ is a bijection of $\alpha \times \alpha$ onto an ordinal ${\gamma }_{\alpha }$, and the functions extend one another.

At zero this is the empty function. Assuming it at $\alpha$, the least missing ordinal is ${\gamma }_{\alpha }$. Recursion down the new row gives values ${\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$; recursion down the remaining column gives ${\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. These enumerate two disjoint consecutive ordinal intervals above the old range, so the extension is well defined and bijective, withAt a limit $\lambda$, take the union of the earlier functions. Compatibility makes it a function, and every pair of coordinates below $\lambda$ is already present at some earlier stage. Its range is the ordinal ${\bigcup }_{\alpha <\lambda }{\gamma }_{\alpha }$, and injectivity is preserved by the compatible union. This completes the construction of the row-and-column enumeration of an ordinal square.

For finite stages ${\gamma }_n=n^2$. For example the table of $g_3$, with the first coordinate indexing rows, isThe remaining parts refer to this domain-consistent construction. The source's literal boundary claims are preserved in the archive, rather than silently asserted as valid.

Let $\kappa =|\alpha |$ be the infinite initial ordinal of the given ordinal. A successor adds only one point, so $|\alpha +1|=\kappa$: one can absorb the additional point by shifting the initial copy of $\omega$ and fixing the rest.

The successor construction from part (a) partitions the new range into the old range, a new row of size $|\alpha +1|$, and a new column of size $|\alpha |$. By hypothesis each part has cardinality at most $\kappa$, and the old range already has cardinality $\kappa$.

A finite disjoint union of copies of a well-orderable infinite cardinal has that same cardinality without invoking the square theorem being proved. Explicitly, write each $\xi <\kappa$ uniquely as $\omega \eta +n$ with $n<\omega$. Interleave three copies byThis stays below $\kappa$ because an infinite initial ordinal is a limit ordinal and is closed under finite successor steps below it. It is injective by uniqueness of the quotient and finite remainder. The reverse injection is immediate, so the Cantor-Schröder-Bernstein theorem proves the finite-union claim.

Applying that bound to the three range pieces yieldsOnly the well-orderability of ordinals, not a choice principle for arbitrary families of sets, was used.

If zero is admitted as a limit case, the assertion there is immediate since ${\gamma }_0=0$. For a nonzero limit, let $\kappa =|\lambda |$, an infinite initial ordinal. There are two cases; separating them avoids choosing an entire family of bijections at earlier stages.

If $\kappa <\lambda$, the hypothesis applies at $\kappa$. Part (a) gives a bijection $g_{\kappa }:{\kappa }^2\to {\gamma }_{\kappa }$, whose range has cardinality $\kappa$ by hypothesis. Fix one bijection $\lambda \to \kappa$; taking its product gives ${\lambda }^2\cong {\kappa }^2$. Since $g_{\lambda }$ is also bijective onto its range, these maps give $\boxed{|{\gamma }_{\lambda }|=\kappa =|\lambda |}$.

If $\lambda =\kappa$ is itself an initial ordinal, suppose ${\gamma }_{\lambda }>\kappa$. Continuity gives ${\gamma }_{\lambda }={\bigcup }_{\alpha <\kappa }{\gamma }_{\alpha }$, so some earlier ${\gamma }_{\alpha }$ contains the ordinal $\kappa$. If $\alpha$ is finite then ${\gamma }_{\alpha }={\alpha }^2$ is finite, impossible. If $\alpha$ is infinite, the hypothesis gives $|{\gamma }_{\alpha }|=|\alpha |<\kappa$, again impossible because its ordinal range contains an initial segment of size $\kappa$.

Thus ${\gamma }_{\lambda }\le \kappa$. Conversely, transfinite induction gives ${\gamma }_{\alpha }\ge \alpha$: each successor appends a nonempty row and limits take unions. In particular ${\gamma }_{\lambda }\ge \lambda =\kappa$. Hence ${\gamma }_{\lambda }=\kappa$ in this case, proving the required cardinal equality as well. The argument includes $\lambda =\omega$, whose earlier stages are finite.

The finite-stage calculation gives ${\gamma }_{\omega }={\sup }_{n<\omega }{n}^2=\omega$, so the desired equality holds at the first infinite ordinal. Apply transfinite induction to all subsequent infinite ordinals. The successor step is part (b), and the limit step is part (c). ThusBy the well-ordering theorem, any infinite cardinal in the question may be represented by an infinite initial ordinal $\kappa$. The corrected recursion supplies a bijection $g_{\kappa }:\kappa \times \kappa \to {\gamma }_{\kappa }$, and the just-proved equality gives $|{\gamma }_{\kappa }|=\kappa$. ThereforeThe proof used only finite-copy interleaving before reaching this conclusion; using the square equality itself to estimate the successor or limit stages would have been circular.