Hartogs' Theorem

Hartogs' theorem shows that for every set, there exists an ordinal that cannot be injected into it. This foundational result does not require the axiom of choice and provides ordinals "measuring" the size of sets.

Statement

Theorem4.7Hartogs' theorem

For every set $A$ , there exists an ordinal $\alpha$ such that there is no injection $f: \alpha \hookrightarrow A$ . The least such ordinal is called the Hartogs number of $A$ , denoted $\aleph(A)$ or $h(A)$ .

Proof

Define $W$ to be the set of all well-orderings of subsets of $A$ . More precisely:

$W = \{(B, R) : B \subseteq A,\, R \subseteq B \times B,\, R \text{ is a well-ordering of } B\}.$

By the axioms of power set and separation, $W$ is a set.

For each $(B, R) \in W$ , let $\mathrm{otype}(B, R)$ be the unique ordinal isomorphic to $(B, R)$ . Define:

$\alpha = \{\mathrm{otype}(B, R) : (B, R) \in W\}.$

Claim 1: $\alpha$ is a set of ordinals. By the axiom of replacement, the image of $W$ under the order-type function is a set.

Claim 2: $\alpha$ is an ordinal. If $\beta \in \alpha$ , then $\beta$ is the order type of some $(B, R) \in W$ . Any $\gamma < \beta$ is the order type of an initial segment of $(B, R)$ , which is also a well-ordered subset of $A$ , so $\gamma \in \alpha$ . Thus $\alpha$ is transitive and well-ordered by $\in$ .

Claim 3: There is no injection $\alpha \hookrightarrow A$ . Suppose $f: \alpha \hookrightarrow A$ is injective. Then $f[\alpha] \subseteq A$ inherits a well-ordering from $\alpha$ , so $(f[\alpha], f_*(\in))$ is a well-ordered subset of $A$ with order type $\alpha$ . Thus $\alpha \in \alpha$ , contradicting the axiom of foundation.

Claim 4: $\alpha$ is the least such ordinal. For any $\beta < \alpha$ , by definition $\beta$ is the order type of some well-ordered $B \subseteq A$ , so there exists an injection $\beta \hookrightarrow B \hookrightarrow A$ . $\blacksquare$

■

Properties and Applications

ExampleComputing Hartogs numbers

If $|A| = n$ (finite), then $\aleph(A) = n + 1$ (or more precisely, $\omega$ since all countable ordinals up to $\omega$ inject into $\mathbb{N}$ ... actually $\aleph(A) = n+1$ only for the strict definition using bijections; with injections, $\aleph(\{0,\ldots,n-1\}) = \omega$ ).
$\aleph(\mathbb{N}) = \omega_1$ (the first uncountable ordinal), since every countable ordinal embeds into $\mathbb{N}$ , but $\omega_1$ does not.
$\aleph(\mathbb{R}) = \omega_2$ if $|\mathbb{R}| = \aleph_1$ (CH), but this depends on the continuum hypothesis.

RemarkHartogs' theorem without choice

Hartogs' theorem is provable in ZF (without the axiom of choice). It is used to prove that the axiom of choice is equivalent to the well-ordering theorem: given any set $A$ , the Hartogs number $\aleph(A)$ provides an ordinal "just bigger" than $A$ , which combined with Zorn's lemma or similar principles allows a well-ordering to be constructed.