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)$.)

  • $\begingroup$ What does it mean "too long" in this case? $\endgroup$ – MaríaCC Jan 24 '15 at 19:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jan 24 '15 at 19:46
  • $\begingroup$ But $B$ is not defined. Maybe $B=A_0$? $\endgroup$ – MaríaCC Jan 24 '15 at 19:49
  • 1
    $\begingroup$ @María: Oops! Yes, it was supposed to be $A_0$; I’ve fixed it now. Thanks for catching that. $\endgroup$ – Brian M. Scott Jan 24 '15 at 19:50
  • $\begingroup$ 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$... $\endgroup$ – 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$.

  • $\begingroup$ Mmmmm... I've already prove that $\mathrm{WO}/\thicksim$ is well ordered but I don't understand the rest of your answer... $\endgroup$ – MaríaCC Jan 24 '15 at 19:22
  • 1
    $\begingroup$ 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$. $\endgroup$ – JDH Jan 24 '15 at 19:32
  • $\begingroup$ OK, I got that. Then, where is the contradiction? $\endgroup$ – MaríaCC Jan 24 '15 at 19:40
  • $\begingroup$ what is an order type? $\endgroup$ – MaríaCC Jan 24 '15 at 19:43
  • 1
    $\begingroup$ 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). $\endgroup$ – JDH Jan 24 '15 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.