# Understanding proof of Hartogs’ Theorem on Set Theory

I'm trying to understand the proof of the Hartogs’ Theorem on page 100 of this book.

My especific question is:

If we have for each set $A$

$$\mathrm{WO}(A)=\{ (U,\leq_{U}) \, | \, U\subseteq A \, \wedge \, (\leq_{U}) \text{ is a wellordering on }U \}.$$

and this relation on $\mathrm{WO}(A)$

$$U \thicksim V \Longleftrightarrow \text{There is an order preserving bijection between } U \text{ and } V$$

Is it true that there is no injection between $\mathrm{WO}(A)/\thicksim$ and $A$?

I'm trying to show that $\mathrm{WO}(A)/\thicksim$ has the same cardinal as $\mathcal{P}(A)$. By the definition I can see that $\mathcal{P}(A)\leq_c \mathrm{WO}(A)$, but when doing the quotient I don't know how to do. I can't see the proof clearly on the book, because it is written that

$$\mathrm{WO}(A)/\thicksim\subseteq \mathcal{P}(\mathrm{WO}(A))$$ and I can't see how this show the result.

Thank you for any help.

HINT: For $[U],[V]\in\operatorname{WO}(A)/\!\!\sim$ define $[U]\preceq[V]$ iff $\langle U,\le_U\rangle$ is order-isomorphic to an initial segment (not necessarily proper) of $\langle V,\le_V\rangle$. Prove that $\preceq$ is a well-defined well-ordering of $\operatorname{WO}(A)/\!\!\sim$. Now suppose that $h:\operatorname{WO}(A)/\!\!\sim\,\to A$ is an injection. Let $A_0$ be the range of $h$, and define a relation $\sqsubseteq$ on $A_0$ by $a\sqsubseteq b$ iff $h^{-1}(a)\preceq h^{-1}(b)$. Show that $\langle A_0,\sqsubseteq\rangle\in\operatorname{WO}(A)$, and get a contradiction because $\langle A_0,\sqsubseteq\rangle\in\operatorname{WO}(A)$ is ‘too long’.

(Note that it isn’t helpful to think about the cardinality of $\langle A_0,\sqsubseteq\rangle\in\operatorname{WO}(A)$.)

• What does it mean "too long" in this case? – MaríaCC Jan 24 '15 at 19:44
• @María: Each member of $\operatorname{WO}(A)$ will be order-isomorphic to a proper initial segment of $\langle B,\sqsubseteq\rangle$, so $\langle B,\sqsubseteq\rangle$ can’t be in $\operatorname{WO}(A)$ after all. – Brian M. Scott Jan 24 '15 at 19:46
• But $B$ is not defined. Maybe $B=A_0$? – MaríaCC Jan 24 '15 at 19:49
• @María: Oops! Yes, it was supposed to be $A_0$; I’ve fixed it now. Thanks for catching that. – Brian M. Scott Jan 24 '15 at 19:50
• Haha thank you. My brain is totally frozen today. I cannot see why each member of $\mathrm{WO}(A)$ is isomorphic to a proper initial segment of $A_0$... – MaríaCC Jan 24 '15 at 19:58

It isn't generally true that $\text{WO}(A)/\sim$ has the same cardinality as $P(A)$; this would be true under the GCH and indeed the assertion that it is true for all infinite $A$ is equivalent to the GCH in ZFC.

Meanwhile, there is no injection from $\text{WO}(A)/\sim$ to $A$, because if there were, you could use the image of that injection to make an order-type that does not occur in $\text{WO}(A)$, which would be a contadiction. Basically, you should show that $\text{WO}(A)/\sim$ is itself well-ordered, and so the injection induces a well-ordering of a subset of $A$, and this order type is strictly larger than anything in $\text{WO}(A)$. This order is the order-type of the smallest well-ordering that does not embed into $A$.

• Mmmmm... I've already prove that $\mathrm{WO}/\thicksim$ is well ordered but I don't understand the rest of your answer... – MaríaCC Jan 24 '15 at 19:22
• Well, if $\text{WO}/\sim$ is well-ordered, and you've injected it into $A$, then you can copy over that well-ordered relation to get a well-ordering of a subset of $A$. – JDH Jan 24 '15 at 19:32
• OK, I got that. Then, where is the contradiction? – MaríaCC Jan 24 '15 at 19:40
• what is an order type? – MaríaCC Jan 24 '15 at 19:43
• Two order relations have the same order type when they are order isomorphic. The contradiction is that the order type of WO(A)/$\sim$ itself cannot arise as one of the elements of WO(A). – JDH Jan 24 '15 at 20:13