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?
Best Answer
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).