Munkres Section 10: How are these order types different?

Question

Let $\mathbb{Z}^+$ denote the set of all positive integers in the usual order, let $n$ be a positve integer, and let the following sets have the dictionary order: $\{1, \ldots, n \} \times \mathbb{Z}^+$, $\mathbb{Z}^+ \times \mathbb{Z}^+$, and $\mathbb{Z}^+ \times \left( \mathbb{Z}^+ \times \mathbb{Z}^+ \right)$.

Now Munkres states that all these sets have different order types. My question is: how do we show that this is indeed the case?

Each of these sets has a smallest element, and in each set, every element has an immediate successor. In $\{1, \ldots, n \} \times \mathbb{Z}^+$, only finitely many elements fail to have immediate predecessors, namely, the elements $(1,1), \ldots, (n,1)$, whereas in $\mathbb{Z}^+ \times \mathbb{Z}^+$, there is an infinite subset of elements without immediate predecessors, viz., the set $\{ (1,1), (2,1), (3,1), \ldots \}$, and the situation is similar for the set $\mathbb{Z}^+ \times \left(\mathbb{Z}^+ \times \mathbb{Z}^+ \right)$.

Is this difference sufficient to distinguish the order types of $\{1, \ldots, n\} \times \mathbb{Z}^+$ from that of either $\mathbb{Z}^+ \times \mathbb{Z}^+$ or $\mathbb{Z}^+ \times \left( \mathbb{Z}^+ \times \mathbb{Z}^+ \right)$

And how do we know that the order types of $\mathbb{Z}^+ \times \mathbb{Z}^+$ and $\mathbb{Z}^+ \times \left( \mathbb{Z}^+ \times \mathbb{Z}^+ \right)$ are different?

Answer 1

Yes: it’s sufficient to distinguish the order type of $\{1,\ldots,n\}\times\Bbb Z^+$ from both of the other two. Distinguishing the order types of $\Bbb Z^+\times\Bbb Z^+$ and $\Bbb Z^+\times(\Bbb Z^+\times\Bbb Z^+)$ by elementary means is just a tiny bit little harder, but you can use a similar idea. In each of them look at the subset consisting of elements without an immediate predecessor. In $\Bbb Z^+\times\Bbb Z^+$ each of member of that set has only finitely many predecessors in that set. Is that true in $\Bbb Z^+\times(\Bbb Z^+\times\Bbb Z^+)$?

It may be helpful to visualize these three order types. If I use the symbol $\longrightarrow$ to stand for the order type of $\Bbb Z^+$, $\{1,\ldots,n\}\times\Bbb Z^+$ has the order type

$$\underbrace{\longrightarrow\longrightarrow\ldots\longrightarrow}_{n\text{ arrows}}\;,$$

and the elements without immediate predecessors are at the tails of the $n$ arrows.

$\Bbb Z^+\times\Bbb Z^+$ has the order type

$$\underbrace{\longrightarrow\longrightarrow\longrightarrow\longrightarrow\ldots}_{\text{a whole arrow of arrows}}\;,$$

and again the elements without immediate predecessors are at the tails of the $n$ arrows. If I abbreviate that picture to $\Longrightarrow$, I can represent the type of $\Bbb Z^+\times(\Bbb Z^+\times\Bbb Z^+)$ as

$$\underbrace{\Longrightarrow\Longrightarrow\Longrightarrow\Longrightarrow\ldots}_{\text{a whole arrow of arrows}}\;,$$

in which each $\Longrightarrow$ contains infinitely many elements without immediate predecessors.

In fact, the set of elements without immediate predecessor in $\{1,\ldots,n\}\times\Bbb Z^+$ is ordered like $\{1,\ldots,n\}$; that in $\Bbb Z^+\times\Bbb Z^+$ is ordered like $\Bbb Z^+$; and that in $\Bbb Z^+\times(\Bbb Z^+\times\Bbb Z^+)$ is ordered like $\Bbb Z^+\times\Bbb Z^+$.

Answer 2

Every ordered set you stated is well-ordered, and you can check that the first one is isomorphic to some initial segment of the second one. However, every initial segment of some well-ordered set is not isomorphic to the original set so the first one and the second one are not isomorphic. Similarly, you can prove that $\Bbb{Z}^+\times \Bbb{Z}^+$ is not isomorphic to $\Bbb{Z}^+\times (\Bbb{Z}^+\times \Bbb{Z}^+)$.

Answer 3

Suppose $a$ is the predecessor to $b$, and $\phi$ is an order-preserving isomorphism of sets. We want to show $\phi(a)$ is the predecessor to $\phi(b)$. Assume otherwise, that there is some other element $x$ such that $\phi(a) < x < \phi(b)$. Then $x = \phi(c)$ for some $c$, and because $\phi$ is order preserving, $a < c < b$ which is a contradiction.