I'm currently working on §10 of "Topology" by James R. Munkres. I've got a problem with task 3:

Both $\{1,2\} \times \mathbb Z_+$ and $\mathbb Z_+ \times \{1,2\}$ are well-ordered in the dictionary order. Do they have the same order type?

$A := \{1,2\} \times \mathbb Z_+$

$B := \mathbb Z_+ \times \{1,2\}$

They have the same order type if there is an order preserving bijection between them. Since both have the same cardinality, I could construct a function

$f: A \to B$

$f(\min A) = \min B$

$f(\,\min\,(A-\{\min A\})\,) = \min\,(B - \{\min B\})$

and so forth.

This function preserves the order. Now my study partner disagrees with this, because f reaches every element of B whose second component is 1, but not the others. So the function would not be surjective. But f being injective would surely imply different cardinalities for A and B.

Can you tell us the correct solution?

  • 1
    $\begingroup$ It's worth noting that the existence of a strictly injective function $A\to B$ does not imply that their cardinalities are different. Consider the function $\Bbb Z_+\to\Bbb Z_+$ given by $n\mapsto n+1.$ This is strictly injective, but certainly we can't say that $\Bbb Z_+$ has a different cardinality than itself, can we? In order for the cardinalities to be different, there must be no bijection between them. In your case, there is a ready bijection $A\to B$ given by $\langle x,y\rangle\mapsto\langle y,x\rangle.$ $\endgroup$ – Cameron Buie Jun 14 '14 at 13:41
  • $\begingroup$ As a side note, you have shown that $A$ is order-isomorphic to a section of $B$ (to use Munkres's terminology). One can show that for any two well-ordered sets $A$ and $B,$ exactly one of the following holds: (i) $A$ and $B$ are order-isomorphic, (ii) $A$ is isomorphic to a section of $B$, or (iii) $B$ is isomorphic to a section of $A$. (I don't recommend that you try to prove it, but it can be proved.) Since your $A$ is isomorphic to a section of your $B,$ then they cannot be isomorphic--that is, they do not have the same order type. $\endgroup$ – Cameron Buie Jun 14 '14 at 13:46

Because every element with first coordinate $1$ always lies before any element with first coordinate $2$, the set $A$ looks like two copies of $\mathbb{Z}^+$, one after the other:


While we can order $B$ as


which looks just like $\mathbb{Z}^+$ (we just doubles all the points).

So intuitively we expect the order types to be different.

If $f: A \rightarrow B$ is an order preserving bijection, then suppose $f(2,0) = (n,i)$, for some $n \in \mathbb{Z}^+, i \in \{1,2\}$. But $(2,0)$ has infinitely many predecessors, but no element in $B$ has. Contradiction, as $f$ should be a bijection between them.

| cite | improve this answer | |

No. This is not the correct solution. Note that $\Bbb Q$ and $\Bbb Z$ have the same cardinality. Does that mean that they have the same order types too?

Let me give you a hint, one of these orders has an element which is not a minimum, nor it is a successor; the other one does not.

| cite | improve this answer | |

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.