This is a problem (10.11) from Munkres, Topology, 2 ed.

Problem: Let $A$ and $B$ be two sets. Using the well-ordering theorem, prove that either they have the same cardinality, or one has cardinality greater than the other.

Well-ordering theorem: If $A$ is a set, there exists an order relation on $A$ that is a well-ordering.

Two sets $A$ and $B$ are said to have the same cardinality if there is a bijection of $A$ with $B$. Let $A$ and $B$ be two nonempty sets. If there is an injection of $B$ into $A$, but no injection of $A$ into $B$, we say that $A$ has greater cardinality than $B$.

The hint to the problem makes reference to this theorem: Let $J$ and $C$ be well-ordered sets; assume that there is no surjective function mapping a section of $J$ onto $C$. Then there exists a unique function $h: J\to C$ satisfying the equation $$h(x)=\text{smallest}[C-h(S_x)].$$

I do not quite see the relationship between this last theorem to the problem at hand. The theorem implies that if there is no surjection of $A$ onto $B$ then there has to be an injection of $A$ into $B$. But how should I use it on the problem at hand? Thank you very much!

  • $\begingroup$ If you know Zorn's lemma, you do not need to use the well-ordering theorem. $\endgroup$ – Andrés E. Caicedo Jan 9 '14 at 23:44
  • $\begingroup$ math.stackexchange.com/questions/421638/… and a list of other threads: math.stackexchange.com/questions/421638/… $\endgroup$ – Asaf Karagila Jan 10 '14 at 10:38
  • $\begingroup$ Interestingly, the statement you prove is actually equivalent to the well-ordering theorem: suppose any two cardinalities are comparable. Let $A$ be a set you want to well-order, and let $\aleph$ denote the Hartogs ordinal of $A$. By the definition of the Hartogs ordinal, there is no injection $\aleph\hookrightarrow A$, so, by hypothesis, there is an injection $A\hookrightarrow\aleph$. Now the well order on $\aleph$ induces a well order on $A$. $\endgroup$ – John Gowers Jan 13 '17 at 15:38

You say:

The theorem implies that if there is no surjection of $A$ onto $B$ then there has to be an injection of $A$ into $B$.

Then if there is no injection $A\to B$, then then there is a surjection $A\to B$ and hence an injection $B\to A$ (AC again). So $\lvert A\rvert\le \lvert B\rvert$ or $\lvert B\rvert\le \lvert A\rvert$.

By the way, the construction to define the function $h\colon J\to C$ actually either yields an order isomorphism from $J$ to an initial segment of $C$ or, if it fails, an order isomorphism from an initial segment of $J$ to $C$. In the latter case, this directly yields an injection from $C$ to $J$.

  • $\begingroup$ Thank you for the answer. From your answer, I understand that if there is no injection of $A$ into $B$, then there has to be an injection of $B$ into $A$. In that case, $A$ would have greater cardinality than $B$. There is still one last thing I am not sure about: What if there is an injection of $A$ into $B$, as well as an injection of $B$ into $A$? Intuitively, I think that implies that there is a bijection of $A$ with $B$, but how should one demonstrate that? Thank you! $\endgroup$ – Fang Jing Jan 10 '14 at 21:19
  • 1
    $\begingroup$ You are right, this is the Cantor-Bernstein Theorem. It's proof is elementary, but a bit tricky. $\endgroup$ – Carsten S Jan 11 '14 at 1:42

We may assume $A,B$ well-ordered. If there exists a surjection $g\colon A\to B$, then we obtain an injection $f\colon B\to A$, $b\mapsto \min g^{-1}(\{b\})$. If on the other hand there is no such surjection, then there is an injection $h\colon A\to B$. At any rate, $A$ and $B$ can be compared carinalitywise.

  • $\begingroup$ You do not really need the well ordering for the first part. If $g\colon A\to B$ is a surjection then by the vanilla axiom of choice, $g$ has a right inverse $f\colon B\to A$. But now $f$ has a left inverse ($g$), so it is an injection. $\endgroup$ – John Gowers Jan 13 '17 at 15:40

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.