Linear Orderings: The Architecture Underneath the Numbers [Linear Orderings Part 2]

You've spent your whole life using the number line, and you've probably never thought to ask: what exactly makes it a line? It's not the individual numbers — it's the relationship between them. The fact that $3 < 5 < 7$, that between any two rationals there is another, that the integers have gaps. These are not properties of the numbers themselves but of the ordering structure they come equipped with.

The study of these ordering structures — independently of what the elements actually are — is order theory. And it is one of the most beautiful corners of mathematics I have come across.

A linear ordering on a set $L$ is a relation $<$ satisfying:

  Transitivity: if $x < y$ and $y < z$, then $x < z$.
  Totality: for any distinct $x, y \in L$, either $x < y$ or $y < x$.
  Irreflexivity: $x \not< x$ for all $x$.

Think of it as a ranking of elements on a line — everyone has a place, no two people share a place (unless they're the same person), and position respects transitivity. Simple rules, but the variety of structures they generate is staggering. 
 

The Standard Orderings

The natural numbers $(\mathbb{N}, <)$: The ordering $0 < 1 < 2 < 3 < \cdots$ satisfies all three axioms trivially. Transitivity: clear from arithmetic. Totality: given any two natural numbers, one is smaller. Irreflexivity: nothing is less than itself.

The integers $(\mathbb{Z}, <)$: The ordering $\cdots < -2 < -1 < 0 < 1 < 2 < \cdots$ similarly satisfies all three. The key difference from $\mathbb{N}$ is that there is no smallest element — you can always go further left.

The rationals $(\mathbb{Q}, <)$: The standard ordering on $\mathbb{Q}$ is also a linear ordering. But $\mathbb{Q}$ has an additional property that neither $\mathbb{N}$ nor $\mathbb{Z}$ has: density. Between any two rationals $p < q$, there exists another rational $\frac{p+q}{2}$. There are no gaps.

All three are genuine linear orderings. $\checkmark$

Infinitely Many Rankings on $\mathbb{N}$

Now here is where things get fun. The elements of $\mathbb{N}$ are fixed — they're just $0, 1, 2, 3, \ldots$ — but we are free to rearrange them in whatever order we like, as long as we maintain a linear ordering. Here are some examples:

\[
\underbrace{0 < 1 < 2 < 3 < \cdots}_{standard}
\]
\[
1 < 2 < 3 < \cdots < 0 \quad 
\]
\[
2 < 3 < 4 < \cdots < 0 < 1 \quad 
\]
\[
3 < 4 < 5 < \cdots < 0 < 1 < 2 \quad 
\]

In general, for any $k \in \mathbb{N}$, consider the ordering where $k, k+1, k+2, \ldots$ come first in their natural order, followed by $0, 1, \ldots, k-1$ in their natural order. These are all valid linear orderings on $\mathbb{N}$, and they are all different for different values of $k$. So yes, there are infinitely many rankings on $\mathbb{N}$.

Infinitely Many Non-Isomorphic Rankings

This is the more subtle question. Two linear orderings are isomorphic if you can relabel the elements of one to get the other — more precisely, if there's a bijection $f: L_1 \to L_2$ that preserves the ordering: $x <_1 y \iff f(x) <_2 f(y)$.

You may think however if I can just relabel any element then all orderings would be isomorphic right? Just change the values and you have a new ordering! However, look at \[1 < 2 < 3 < \cdots < 0 \] This can be written as 1 is in 0s place (1 maps to 0), 2 maps to 1, 3 maps to 2, etc. But what does 0 map to? n maps to n-1 and \(0-1 = -1\) however this is a re-ordering of natural numbers so we do not have negatives. We may be tempted to say that 0 maps to infinity however just as the new patron of the  Hilbert hotel couldn't walk to infinity infinity is not a tangible mapping for any value. 

It just takes the form of \(\cdots\). Thus, 
\[
1 < 2 < 3 < \cdots < 0
\]
is a fundamentally different structure to
\[
0<1 < 2 < 3 < \cdots 
\]
The way I got intuition think of isomorphism as ``same form'' The orderings $1 < 2 < 3$ and $a < b < c$ are isomorphic even though they use different symbols — their structure is identical. For the non isomorphic orderings like the re-orderings of the natural numbers, we use the same shape intuition. Suppose you're holding an infinitely long stick. The stick is such that as you look to infinity the stick appears transparent. Of course, as you approach larger numbers the opacity increases and the more larger numbers consequently become the translucent ones. This is an analogue of the \(
0<1 < 2 < 3 < \cdots 
\) ordering. Now, imagine that while far into the horizon where the rod is already transparent at infinity there is a \(100\%\) opaque block. You can never reach it but it is opaque next to the almost transparent infinity. This is the 0 at the end of the \(\cdots\). This is similar to having a lightsaber that is capped at the end (the integers are then like Darth Maul's famous double bladed lightsaber).

Now, can we find infinitely many rankings on $\mathbb{N}$ with genuinely different shapes? Yes! Consider the following rankings.
a) All the even numbers followed by all the odd numbers:
\[0<2<4<6<8<10<\cdots<1<3<5<7<9<11<\cdots\]
b) All the \(n \equiv0 \;mod(3)\) followed by \(n \equiv1 \;mod(3)\) followed by the \(n \equiv2 \;mod(3)\):
\[0<3<6<9<12<15<\cdots<1<4<7<10<13<16<\cdots<2<5<8<11<14<17<\cdots\]

The pattern is now noticeable. For each $k \geq 1$, define the ordering $L_k$ on $\mathbb{N}$ by placing all numbers $\equiv 0 \pmod{k}$ first, then $\equiv 1 \pmod{k}$, then $\equiv 2 \pmod{k}$, and so on
So $L_1$ is the standard ordering, $L_2$ is example (a), $L_3$ is example (b), and so on. This gives us infinitely many rankings on $\mathbb{N}$. We claim no two of these are isomorphic.

The key invariant is the number of infinite blocks --- the number of equivalence classes under $\sim$ (elements finitely far apart). Suppose $f: L_1 \to L_2$ were an isomorphism. In $L_2$, the element $1$ (the start of the second block) has the property that infinitely many elements lie below it and infinitely many above it, with no element of the first block above it. There is no such element in $L_1$. The same logic continues. Since an isomorphism $f: L_j \to L_k$ must send each $\sim$-class of $L_j$ to a $\sim$-class of $L_k$ (order-preserving bijections preserve the notion of ``finite distance between elements''), it would induce a bijection between the $\sim$-classes of $L_j$ and those of $L_k$. But $L_j$ has $j$ classes and $L_k$ has $k$ classes, so if $j \neq k$, no such bijection exists.

Hence $L_1, L_2, L_3, \ldots$ are pairwise non-isomorphic, giving us infinitely many non-isomorphic rankings on $\mathbb{N}$.

Ranking of $\mathbb{N}$ Isomorphic to $\mathbb{Z}$

We can see using the structure intuition that a valid ordering would be\[\cdots<8<6<4<2<0<1<3<5<7<\cdots\]

Ranking of $\mathbb{N}$ Isomorphic to $\mathbb{Q}$

This one feels almost impossible at first. $\mathbb{Q}$ is dense — between any two rationals there is another — and $\mathbb{N}$ with its usual ordering has obvious gaps. But remember: we are not using $\mathbb{N}$'s usual ordering! We are asking whether we can rearrange the elements of $\mathbb{N}$ to produce the same structural shape as $\mathbb{Q}$.

This is in fact possible, by a beautiful back-and-forth argument (which is essentially the content of B7, Cantor's theorem). The key observation is that $\mathbb{N}$ is countably infinite — just like $\mathbb{Q}$ is countably infinite.

List $\mathbb{Q} = \{q_0, q_1, q_2, \ldots\}$. Define ordering on $\mathbb{N}$ by $m <' n$ iff $q_m < q_n$. Then $(\mathbb{N}, <') \cong (\mathbb{Q}, <)$ by construction.

Embedding Any Countable Linear Order into $\mathbb{Q}$

This result is the backbone of everything that follows. It says: no matter how you arrange a countable set, you can always faithfully represent that arrangement inside the rational numbers.

Let $L$ be a countable linear order. Then there exists an order-preserving injection $\bar{\cdot}: L \to \mathbb{Q}$, i.e., a function assigning to each $x \in L$ a rational $\bar{x}$ such that $x < y \Rightarrow \bar{x} < \bar{y}$.


List the elements of $L$ as $x_0, x_1, x_2, \ldots$ (since $L$ is countable). We build $\bar{x}_n$ inductively.

Base case: Set $\bar{x}_0 = 0$.

Inductive step: Suppose we have assigned rationals $\bar{x}_0, \ldots, \bar{x}_{n-1}$ in an order-preserving way. To assign $\bar{x}_n$:

• Let $A = \{\bar{x}_i : i < n, \; x_i < x_n\}$ and $B = \{\bar{x}_i : i < n, \; x_n < x_i\}$.
• All elements of $A$ are less than all elements of $B$ (by the inductive hypothesis preserving order).
•  Since $\mathbb{Q}$ is dense and has no endpoints, there exists a rational strictly between $\sup A$ and $\inf B$ (or just greater than all of $A$ if $B = \emptyset$, or just less than all of $B$ if $A = \emptyset$). Pick any such rational as $\bar{x}_n$.

The result is an order-preserving injection.


The visual intuition here is compelling: think of $\mathbb{Q}$ as an infinitely stretchy, infinitely divisible ruler. Whatever shape your countable linear order has, you can always ``fit'' it onto this ruler without distorting the relative order of points. The rationals are universal for countable linear orders.

Cantor's Theorem — Any Two Countable Dense Orderless Linear Orders are Isomorphic

This is a masterpiece of mathematics. The statement: any two countable linear orders that have no smallest element, no largest element, and no gaps (i.e., are dense) are isomorphic to each other — and hence isomorphic to $\mathbb{Q}$.

There are actually two ways to see this, and they feel quite different in spirit. The first is a direct construction. The second is the famous back-and-forth method. Both are worth understanding --- they illuminate different aspects of why the theorem is true.

Proof via the embedding approach:

Recall that any countable linear order can be order-preservingly embedded into $\mathbb{Q}$. That is, given any countable linear order $L$, we can find an injection $\bar{\cdot}: L \to \mathbb{Q}$ that respects the ordering.

Now suppose $L_1$ and $L_2$ are both countable, dense, and without endpoints. Apply B6 to $L_1$: we get an order-preserving embedding $\phi: L_1 \hookrightarrow \mathbb{Q}$. The image $\phi(L_1)$ is a countable sub-ordering of $\mathbb{Q}$. 

But is $\phi(L_1)$ isomorphic to $L_2$? Not immediately --- $\phi(L_1)$ might not be all of $\mathbb{Q}$, and $L_2$ might not sit inside $\mathbb{Q}$ in the same way. The embedding approach alone gets us inside $\mathbb{Q}$ but does not immediately hand us the isomorphism between $L_1$ and $L_2$ directly.

Here is the fix. Apply B6 twice: embed $L_1$ into $\mathbb{Q}$ via $\phi$, and embed $L_2$ into $\mathbb{Q}$ via $\psi$. Both images are countable dense sub-orderings of $\mathbb{Q}$ without endpoints. Now the key insight: a countable dense sub-ordering of $\mathbb{Q}$ without endpoints is itself a countable dense linear order without endpoints --- so by the very theorem we are trying to prove, it is isomorphic to $\mathbb{Q}$. 

This feels circular! And honestly, it is --- the B6 approach alone cannot close the loop without already assuming the conclusion. It tells us that every such ordering embeds into $\mathbb{Q}$, which is a strong and useful fact, but it does not by itself prove that any two such orderings are isomorphic to each other. For that, we need something more.

Proof via Back-and-Forth:

This is where Cantor's real idea lives. Instead of embedding both orderings into a common host and comparing them there, we build the isomorphism directly between $L_1$ and $L_2$, piece by piece.

Imagine you and a friend are each handed an infinite jigsaw puzzle. You are told nothing about the picture --- only that both puzzles are countable, dense, and have no edges. Your job is to prove the two puzzles are identical in structure, without ever seeing the full picture at once. How do you do it? You match pieces one at a time. You pick a piece from your puzzle, find where it belongs in your friend's, then your friend picks a piece from theirs and you find where it belongs in yours. Back and forth, forever. The density condition is your guarantee that you never get stuck: whenever you need to place a new piece between two already-placed ones, density promises there is always room. The no-endpoint condition guarantees you can always extend outward in either direction. The proof uses the same logic. List $L_1 = \{a_0, a_1, a_2, \ldots\}$ and $L_2 = \{b_0, b_1, b_2, \ldots\}$. We build an isomorphism $f: L_1 \to L_2$ in stages.

Stage 0 (forth): Set $f(a_0) = b_0$.

Stage 1 (back): Ensure $b_1$ is in the range of $f$. Look at where $b_1$ sits relative to $b_0$: if $b_1 < b_0$, use the fact that $L_1$ has no minimum to find an unused $a_i < a_0$ and set $f(a_i) = b_1$; if $b_1 > b_0$, find an unused $a_i > a_0$ and set $f(a_i) = b_1$.

Stage 2 (forth): Take the next unmatched element of $L_1$. It sits in some position relative to already-matched elements. The density of $L_2$ guarantees there is an available element of $L_2$ in exactly the correct relative position. Match them.

Alternating forth and back, every element of $L_1$ eventually gets an image, and every element of $L_2$ eventually gets hit. The result is an order-preserving bijection. 
$\square$


What makes back-and-forth strictly stronger than the embedding approach is that it builds a surjective map, not just an injective one. Embedding only gets us into $L_2$;  back-and-forth gets us onto $L_2$ as well, by attending to both sides simultaneously. The alternation is everything.

The punchline is striking: up to renaming, there is essentially one countable dense linear order without endpoints. Call it what you like --- $\mathbb{Q}$, $\eta$, the rationals. All roads lead here. The rationals are not special because of what their elements are. They are special because of the shape they form.