Hartogs Number, Well-Ordering, and the Axiom of Choice

The dividing line. Many cardinality facts are theorems of plain ZF; others genuinely need the Axiom of Choice (AC). A reliable exam skill is telling the two apart. The Hartogs construction sits exactly on this border: it is a powerful tool provable without AC, yet it is what makes AC strong enough to well-order everything.

Hartogs number $\aleph(X)$ — pure ZF

For a set $X$, define $\aleph(X) = \{\beta \text{ ordinal} : \beta \preceq X\},$ the collection of all ordinals that inject into $X$ (equivalently, that $X$ surjects onto; a surjection $X \twoheadrightarrow \beta$ and an injection $\beta \hookrightarrow X$ convert into each other here because the ordinal $\beta$ is already well-ordered, so you pick least preimages — no choice function needed). Three ZF facts:

• It is a set (by Replacement). Every such $\beta$ is the order type of a well-ordering of a subset of $X$, and all those well-orderings live inside the set $\mathcal{P}(X \times X)$. Replacement turns this set of well-orderings into the set of their order types.
• It is an ordinal. $\aleph(X)$ is a set of ordinals that is transitive ($\gamma < \beta \preceq X \Rightarrow \gamma \preceq X$), and a transitive set of ordinals is an ordinal.
• It is the threshold. $\aleph(X) \not\preceq X$ — otherwise $\aleph(X) \in \aleph(X)$, violating Foundation — while every $\beta < \aleph(X)$ does inject into $X$. So $\aleph(X)$ is the least ordinal that does not inject into $X$.

Critically, none of this uses AC. It works for every set, even sets that cannot be well-ordered without choice.

Where AC actually enters

AC is needed to compare $X$ itself with the ordinals. Hartogs gives you an ordinal $\aleph(X)$ that $X$ cannot reach; AC closes the gap the other way.

The pattern in the ZF rows: when everything in sight is a definable subset or power of the canonically well-ordered $\mathbb{N}$, you get explicit enumerations (take the least element; prime-power code a sequence) and choice silently disappears.

Mini-example: Hartogs $\Rightarrow$ Well-Ordering from AC

Given AC, well-order any $X$: by AC fix a choice function on $\mathcal{P}(X)\setminus\{\varnothing\}$ and use it to map ordinals injectively into $X$, one new element at each step, $\beta \longmapsto g(\beta) = \text{choice}\big(X \setminus \{g(\gamma) : \gamma < \beta\}\big).$ This transfinite recursion cannot run forever: it must halt, and it can only halt at the first $\beta$ for which $X \setminus \{g(\gamma):\gamma<\beta\}=\varnothing$, i.e. when $g$ has enumerated all of $X$ — and that ordinal is below $\aleph(X)$, the Hartogs bound that $X$ cannot exceed. The resulting bijection $\beta \to X$ transports the well-order of $\beta$ onto $X$. Without the Hartogs number you would have no a priori ceiling guaranteeing the recursion stops on a set.

Exam trick: "Set of all ordinals that map onto / inject into $X$, and ZF shows it is a set" is the Hartogs number $\aleph(X)$ — a nonzero ordinal (since $0 \preceq X$) and the least ordinal not embeddable in $X$, all in ZF, no choice. AC is the extra axiom you need to push $X$ itself up to an ordinal (well-order it); it is not needed merely to build $\aleph(X)$ or to enumerate definable subsets/powers of the well-ordered $\mathbb{N}$.