# Infinite linear (non-well) orderings

I can rather easily imagine the infinite linear (non-well) orderings $(\mathbb{Z},\leq)$, $(\mathbb{Q},\leq)$, $(\mathbb{R},\leq)$, each one of its own order type.

Are there "essentially" other infinite linear (non-well) orderings, next to or between the three above?

If not so: Why not?

If so: (How) can they be imagined? Examples?

• Where are they "located"?

• Are there any "between" $\mathbb{Z}$ and $\mathbb{Q}$?

• Are there any "between" $\mathbb{Q}$ and $\mathbb{R}$?

• Or are they all "beyond" $\mathbb{R}$?

• (What) does the latter have to do with the continuum hypothesis?

• Or are there other "locations"?

-
Between $\mathbb Z$ and $\mathbb Q$ you can interleave discrete and dense sections, like $\mathbb Z \cup ((n,n+1) \cap \mathbb Q)$ for a collection of $n$'s. You can even have an infinite discrete stretch. – Ross Millikan Aug 30 '12 at 21:38
Then it comes to dispute about what is "essentially different" (from $\mathbb{Z}$ and $\mathbb{Q}$). – Hans Stricker Aug 30 '12 at 21:46
@HansStricker I would say isomorphic as order structures. – William Aug 30 '12 at 21:47
Check the book "Linear orderings" by Rosenstein. The theory of linear orderings is very rich. – sdcvvc Aug 30 '12 at 21:57
This story is quite complicated. Even the questions of "how many" $\omega_1$-dense sets of the reals there are is independent of the usual axioms. Under CH, the answer is the largest possible. With strong forcing axioms, the answer is 1. ($\omega_1$-dense: The intersection with any open interval has size $\omega_1$.) This is typical: CH tends to give non-structure results (many non-isomorphic structures), while PFA or the like give strong classification results. For a bit more, see math.stackexchange.com/questions/38575/… – Andrés Caicedo Aug 31 '12 at 0:59

Given any infinite ordinal $\kappa$, regardless to any assumptions additional to ZF (not even choice!) we can linearly order $\mathcal P(\kappa)$:

$$A\prec B\iff \min(A\Delta B)\in A$$

It is not hard to see that this is a linear order. It is worth noting that it is dense, any set containing $0$ will be smaller than $\{0\}$. In fact the singletons are dense in this linear order, and between two sets there are $\kappa$ many others. This is somewhat similar to $\mathbb R$, but for even larger cardinalities.

You may want to read Justin Moore's paper:

Moore, A five element basis for the uncountable linear orders, Annals of Mathematics (2) 163 (2006), n 2, pp. 669--688.

about consistency of linear orderings in ZFC (+large cardinals). It might be a good jumping point to the topic, including the references. In fact his homepage's publication list has several more papers about linear orderings.

Between $\mathbb Q$ and $\mathbb Z$ there are many non-isomorphic orders, but they are all countable orders so they have to look a little bit like $\mathbb Z$ and $\mathbb Q$, namely partitioned into intervals (with or without endpoints) of order type $\mathbb Z$ (or $\mathbb N$); isolated points; and $\mathbb Q$.

Between $\mathbb Q$ and $\mathbb R$ there are of course many many orderings, and they very much depend on the continuum hypothesis. If $\mathbb R$ has size $\aleph_2$ then we can find a linear order of size $\aleph_1$ inside the real numbers and use it to construct new orderings using the same trick as with $\mathbb Q$ and $\mathbb Z$; of course if the continuum is even larger then we can find even more of these orderings.

Regardless to that, however, there are order types of the continuum which are not bi-embeddable with $\mathbb R$. For example $\omega_1^\ast+\omega_1$; Sierpinski has defined such linear order as well; there is one more by Specker, I believe. All those cannot be embedded into one another, and all of size continuum (if $\mathbb R$ has a larger cardinality, replace $\omega_1$ by the suitable ordinal, of course).

You might also want to locate Shelah's paper indexed as Sh:100

Shelah, Independence results, J Symbolic Logic 45 (1980) 563-573.

It has some consistency results regarding the existence of linear orderings of size $\aleph_1$.

I should probably add a word on the Suslin line: this is a c.c.c. space which is not separable. Assuming $V=L$ such linear order exists and it is of size continuum, but it is consistent with ZFC that no Suslin line exists either.

-
More generally, given any well-ordering $\kappa$ and a linear ordering $A$ it is possible form $A^{\kappa}$. – sdcvvc Aug 31 '12 at 0:00

First, note that since there is a bijection between $\mathbb{Q}$ and $\mathbb{Z}$, you can endow the set $\mathbb{Q}$ with the order type of the usual $(\mathbb{Z}, <)$ and visa-versa. To do this, suppose $f : \mathbb{Q} \rightarrow \mathbb{Z}$ is a fixed bijection. You can define a new well-ordering on the set $\mathbb{Q}$ as follows: $q_1 \prec q_2$ if and only if $f(q_1) < f(q_1)$, where $<$ is the usual ordering on $\mathbb{Z}$. Hence $(\mathbb{Q}, \prec)$ is an ordering on $\mathbb{Q}$ that is isomorphic to $(\mathbb{Z}, <)$.

From the above, you can see that it is not clear what "between" $\mathbb{Q}$ and $\mathbb{Z}$. Well-orderings can be compared since you can prove that any two well ordering $W_1$ and $W_2$, one can embed in the other.

For your question of whether essentially other infinite linear order, the answer is yes. The usual way to say that a two linear ordering are the same is if there exists an order-preserving bijection between the two linear ordering. The example of $\mathbb{Q}$ above indicates that $\mathbb{Q}$ has at least two different order type: the usual one and an order type that is isomorphic to $(\mathbb{Z}, <)$. There are some very simple ways to construct even more non-isomorphic linear ordering. For example $\mathbb{Z}$ followed by another copy of $\mathbb{Z}$, with the ordering that all elements from the first copy is larger than all element from the second. Within the same copy of $\mathbb{Z}$, it would possess the usual ordering.

The continuum hypothesis is about cardinals. $\aleph_1$ denotes the least infinite ordinal (transitive well-ordered set) that is not in bijection with any previous ordinal. The continuum hypothesis asserts whether $\aleph_1$ is in bijection with the real numbers.

-
I think that you are missing the point in the part about CH. I think Hans is trying to figure out whether or not the truth value of CH implies the existence of such linear orders between $\mathbb Q$ and $\mathbb R$, or something like that. – Asaf Karagila Aug 30 '12 at 21:59
The experts won't be astonished but I am: The constructions I learn about here - attaching several copies of $\mathbb{Z}$ and the like to get non-standard linear orderings - strongly remind me of non-standard models of arithmetic: math.stackexchange.com/questions/37418/… Both seem to be two sides of one medal. – Hans Stricker Aug 31 '12 at 23:21