Show that the following $4$ well-ordered sets are all countably infinite, but they all have different order types. (Munkres "Topology 2nd Edition")

Question

I am reading "Topology 2nd Edition" by James R. Munkres.

The well-ordered sets $$\mathbb{Z}_{+},\\\{1,\dots,n\}\times\mathbb{Z}_{+},\\\mathbb{Z}_{+}\times\mathbb{Z}_{+},\\\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$$ are all countably infinite, but they all have different order types, as you can check.

Note: $\{1,\dots,n\}\times\mathbb{Z}_{+},\mathbb{Z}_{+}\times\mathbb{Z}_{+},\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ are well-ordered in the dictionary order.

I verified $\mathbb{Z}_{+}$ and $\{1,\dots,n\}\times\mathbb{Z}_{+}$ don't have the same order type.
I verified $\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ don't have the same order type.
I verified $\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ don't have the same order type.
I couldn't verify $\{1,\dots,n\}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ don't have the same order type.
I couldn't verify $\{1,\dots,n\}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ don't have the same order type.
I couldn't verify $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ don't have the same order type.

Please tell me how to verify $\{1,\dots,n\}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ don't have the same order type.
Please tell me how to verify $\{1,\dots,n\}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ don't have the same order type.
Please tell me how to verify $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ and $\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ don't have the same order type.

My partial solution is here:

Assume that there exists a bijective function $f:\mathbb{Z}_{+}\to\{1,\dots,n\}\times\mathbb{Z}_{+}$ such that $a<b\implies f(a)<f(b)$.
Let $a$ be an element of $\mathbb{Z}_{+}$ such that $f(a)=(2,1)$.
Then $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\{y\in\{1,\dots,n\}\times\mathbb{Z}_{+}\mid y<(2,1)\}$ have the same order type.
Obviously, $\{y\in\{1,\dots,n\}\times\mathbb{Z}_{+}\mid y<(2,1)\}$ and $\mathbb{Z}_{+}$ have the same order type.
So, $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\mathbb{Z}_{+}$ have the same order type.
But $\{x\in\mathbb{Z}_{+}\mid x<a\}$ is finite and $\mathbb{Z}_{+}$ is infinite.
So, there exists no bijection from $\{x\in\mathbb{Z}_{+}\mid x<a\}$ to $\mathbb{Z}_{+}$.
This is a contradiction.

Assume that there exists a bijective function $f:\mathbb{Z}_{+}\to\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ such that $a<b\implies f(a)<f(b)$.
Let $a$ be an element of $\mathbb{Z}_{+}$ such that $f(a)=(2,1)$.
Then $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\{y\in\mathbb{Z}_{+}\times\mathbb{Z}_{+}\mid y<(2,1)\}$ have the same order type.
Obviously, $\{y\in\mathbb{Z}_{+}\times\mathbb{Z}_{+}\mid y<(2,1)\}$ and $\mathbb{Z}_{+}$ have the same order type.
So, $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\mathbb{Z}_{+}$ have the same order type.
But $\{x\in\mathbb{Z}_{+}\mid x<a\}$ is finite and $\mathbb{Z}_{+}$ is infinite.
So, there exists no bijection from $\{x\in\mathbb{Z}_{+}\mid x<a\}$ to $\mathbb{Z}_{+}$.
This is a contradiction.

Assume that there exists a bijective function $f:\mathbb{Z}_{+}\to\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})$ such that $a<b\implies f(a)<f(b)$.
Let $a$ be an element of $\mathbb{Z}_{+}$ such that $f(a)=(1,(2,1))$.
Then $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\{y\in\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})\mid y<(1,(2,1))\}$ have the same order type.
Obviously, $\{y\in\mathbb{Z}_{+}\times(\mathbb{Z}_{+}\times\mathbb{Z}_{+})\mid y<(1,(2,1))\}$ and $\mathbb{Z}_{+}$ have the same order type.
So, $\{x\in\mathbb{Z}_{+}\mid x<a\}$ and $\mathbb{Z}_{+}$ have the same order type.
But $\{x\in\mathbb{Z}_{+}\mid x<a\}$ is finite and $\mathbb{Z}_{+}$ is infinite.
So, there exists no bijection from $\{x\in\mathbb{Z}_{+}\mid x<a\}$ to $\mathbb{Z}_{+}$.
This is a contradiction.

Answer 1

For order type distinction, we just need to find order-theoretic properties of a set that it doesn't share with the other ordered set.

The set $\{1,2,\ldots,n\} \times \Bbb Z_+$ ($n \ge 2$) has an element with infinitely many predecessors (e.g. $(2,0)$) and this doesn't hold for $\Bbb Z_+$. So the order types are different.

$\{1,2,\ldots,n\} \times \Bbb Z_+$ has only finitely many points that do not have a direct predecessor. This does not hold for $\Bbb Z_+ \times \Bbb Z_+$, nor for $\Bbb Z_+ \times (\Bbb Z_+ \times \Bbb Z_+)$. The mentioned property is obviously preserved by any order preserving bijection. So it serves to distinguish the order type of the second set from the last two.

$\Bbb Z_+ \times (\Bbb Z_+ \times \Bbb Z_+)$ can also be distinguished from $\Bbb Z_+ \times \Bbb Z_+$ using such properties. It has infinitely many elements without a direct predecessor that each have infinite number of predecessors without a direct predecessor. A bit convoluted, but I think it works.

Answer 2

A general result on well-orders, called trichotomy theorem of well-orders, establishes that, for any two well-ordered sets $A, B$, existence of an order-isomorphism between $A$ and $B$, existence of an order-isomorphism between $A$ and and a proper lower set of $B$ and existence of an order-isomorphism between $B$ and a proper lower set of $A$ are mutually exclusive conditions, and specifically exactly one of these occurs. This makes short work of the exercise.

Another approach could be as follows. Preliminarly, notice $\Bbb Z_+$ is isomorphic to $\{1,\cdots,n\}\times\Bbb Z_+$ for $n=1$. Also, label those things (i), (ii), (iii) and (iv).

Given an order $(X,\le)$, call $$L(X)=\{x\in X\,:\, (\forall w< x,\lvert \{y\in X\,:\, w<y<x\}\rvert\ge\aleph_0)\land (\exists w\in X, w<x)\}.$$ In other words, the subset of the elements that aren't minimal and for which there are infinitely many elements between them and any other element smaller than them. The type of order of $(L(X),\le)$ (restricted order) is isomorphism-invariant. Calculating we obtain:

1. $L(\Bbb Z_+)=\varnothing$;
2. $L(\{1,\cdots, n\}\times\Bbb Z_+)=\{2,\cdots, n\}\times\{1\}$
3. $L(\Bbb Z_+\times\Bbb Z_+)=\Bbb Z_+\times \{1\}$
4. $L(\Bbb Z_+\times(\Bbb Z_+\times\Bbb Z_+))=\Bbb Z_+\times(\Bbb Z_+\times\{1\})$

These identities are meant as subsets, but you should convince yourself that they are also equalities of orders (i.e. that the restricted order on the left ofthe idenities is isomorphic to the lexicographic order on the right via the tautolgical map sending each pair to itself). Therefore:

• by a cardinality argument on $L(X)$ it is clear that (i) and (ii) aren't isomorphic to (iii) or (iv), and that (i) and (ii) are isomorphic (if and) only if $n=1$.

• notice that (3) is order-isomorphic to (i), while (4) is order-isomorphic to (iii). By the previous remark, (3) and (4) aren't order-isomorphic, and therefore (iii) and (iv) aren't.