# Order Type of $\mathbb Z_+ \times \{1,2\}$ and $\{1,2\} \times \mathbb Z_+$

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?

• 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.$ – Cameron Buie Jun 14 '14 at 13:41
• 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. – 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:

$$(1,0),(1,1),(1,2),\ldots,(2,0),(2,1)(2,2),\ldots$$

While we can order $B$ as

$$(0,1),(0,2),(1,1),(1,2),(2,1),(2,2),\ldots$$

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.

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.