Hartog's lemma: does a proof for $\mathbb N$ generalise?

Question

I'm reading some online notes taken from Imre Leader's Cambridge lectures on logic and set theory. I find the notes very clear on the whole, but one particular proof - the proof of Hartog's Lemma on page 21 - strikes me as odd.

Hartog's lemma: For any set $X$, there exists an ordinal that does not inject into $X$.

In the notes, Hartog's lemma is first proved in the special case where $X = \mathbb N$, which is merely the statement that there exists an uncountable ordinal. To prove this special case, one considers the set $B$ consisting of distinct ordinals defined on subsets of $\mathbb N$. One then constructs the ordinal $\omega_1 = \sup B$, the least upper bound on the ordinals in $B$. (This ordinal $\omega_1$ is constructed by thinking of the ordinals within $B$ as being nested inside one another and patching them together, as described in detail on pages 19 and 20 of the notes.) One then argues that $\omega_1$ must be an uncountable ordinal. For if $\omega_1$ is countable, then the ordinal $\omega_1^+$, defined as $\omega_1^+ = \omega_1 \cup \{ x \}$ where $y < x$ for all $y \in \omega_1$, is also countable, and is greater than $\omega_1$, contradicting the fact that $\omega_1$ is by definition an upper bound on countable ordinals.

What confuses me is when the notes claim that the above proof for $X = \mathbb N$ generalises immediately to arbitrary sets $X$.

To me, this seems like invalid reasoning. Here are some examples where the proof seems to fall over:

• If $X$ is a finite set and $B$ is the set of distinct ordinals defined on subsets of $X$, then $\omega_1 = \sup B$, as a set, is $X$ itself. The construction has failed to produce an ordinal bigger than $X$.

• If $X$ is an infinite set other than $\mathbb N$, we can follow the same construction, producing an ordinal $\omega_1 = \sup B$ as before. We then want to argue that if $\omega_1$ has the same cardinality as $X$, then $\omega_1^+ = \omega_1 \cup \{ x \}$ has the same cardinality as $X$ too. But it isn't obvious to me that an arbitrary infinite set plus one extra element has the same cardinality as the infinite set without this extra element. (Except for when the infinite set is countable.)

What am I missing?

Answer 1

If $|X|=n$, the construction produces $\{k\in\omega:k\le n\}=n+1>n$.

More generally, let $\alpha$ be the set of ordinals that inject into $X$. Then $\alpha$ is a transitive set of ordinals, so $\alpha$ is an ordinal. Of course $\alpha\notin\alpha$, so $\alpha$ does not inject into $X$.

Alternatively, if $X$ is infinite, you can come closer to imitating the earlier argument by observing that if $\alpha$ injected into $X$, then the ordinal $\alpha+1$ would also inject into $X$ (since for infinite $\alpha$ there is an easy bijection between $\alpha$ and $\alpha+1$), and clearly $\alpha+1\notin\alpha$. It appears that at this point Leader had not proved that a transitive set of ordinals is an ordinal, so he may well have done it this way (or expected his audience to fill in this detail).

Answer 2

In fact, the proof is even simpler than that. An ordinal injects into $X$ iff there is some well order on a subset of $X$ which the ordinal is the order type of. Therefore, the class of ordinals which inject into $X$ is a set.

Since the class of all ordinals cannot form a set, the class of all ordinals isn't the class of all ordinals which inject into $X$; that is, it cannot be that every ordinal can inject into $X$. Then there is an ordinal which cannot inject into $X$.

The proof you gave does in fact generalise to arbitrary $X$.

Step 1: show that the class of ordinals which inject into $X$ forms a set.

Step 2: take the supremum. This is an ordinal.

Step 3: take an ordinal strictly greater than the supremum (by taking the successor of the supremum). If this ordinal could inject into $X$, it would be less than or equal to the supremum. This is a contradiction. Therefore, this ordinal ($\omega_1^+$ in your question) can't inject into $X$.

As you can see, nothing about these steps relies in any way on $X = \mathbb{N}$.

In the case where $X$ is finite (WLOG a natural number), we have $\omega_1 = X$ and therefore $\omega_1^+ = X + 1$. It is not the case that $\omega_1$ can't inject into $X$, but it is clear that $\omega_1^+$ can't inject into X and the theorem only requires that there is some ordinal which can't inject into $X$.

In the case that $X$ is infinite, it is clear that so too must $\omega_1$ be. Then $\omega_1 \geq \omega$; that is, there is a countably infinite initial segment of $\omega_1$. In this case, it is clear that $\omega_1$ and $\omega_1^+$ can be put into bijection.