4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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^+$.

$\endgroup$
1
$\begingroup$

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}^+)$.

$\endgroup$
  • $\begingroup$ Your answer is not fully comprehensible to me, I'm afraid. $\endgroup$ – Saaqib Mahmood Dec 16 '14 at 6:57
1
$\begingroup$

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.

$\endgroup$

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.