What are the order types of all the total orders on $\mathbb{N}$?

286 Views Asked by At

Two ordered sets have the same order type if there exists an order-preserving bijection between them whose inverse is also order-preserving. My question is, what are the order types of all the total orders on the set of natural numbers.

Can you start with all the countable ordinals, as well as the order type of the rational numbers, and then construct all the order types using order type addition, order type multiplication, and the dual operation? Or is there some total order on $\mathbb{N}$ whose order type cannot be constructed in this way?

2

There are 2 best solutions below

4
On

This isn't a full answer, but classifying total orders on $\mathbb N$ is the same as classifying countable total orders (since we don't use any structure on $\mathbb N$ except the set itself).

Now, any countable total order is order-isomorphic to a subset of $\mathbb Q$ with its natural order. A proof can be found here.

6
On

[It seems to me that the order type of $\mathbb{Q} \sqcup 2 \sqcup \mathbb{Q} \sqcup 2 \sqcup ...$ does not fall in this category.] edit: as you pointed out, it does on the contrary. In fact, only $\aleph_1$ many order types can be constructed using your conditions, "while" there are $2^{\aleph_0}$ countable linear order types.

Indeed, for each binary sequence $u: \mathbb{N} \rightarrow \{0;1\}$, consider the transfinite sum $L_u= \sum \limits_{n\in \mathbb{N}} Q_{u(n)}$ where $Q_1= \mathbb{Q}+\mathbb{Z}$ and $Q_0 = 2$. I would say that $L_u$ can be constructed using your rules iff $u$ is eventually periodic, but a proof would require a bit of care. Perhaps a form of "pumping lemma" would apply here.