You might look at the title and ask yourself: what is a linearly ordered set? A good example of such a set would be counting the number of years that have passed since the Big Bang—the age of the universe. It will look something like this:
$$
\overset{\text{Bang!}}{0} \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow \dots \rightarrow \overset{\text{Now?}}{\text{13,772,000,000}} \rightarrow \cdots
$$
More formally, a set $S$ is a collection of objects $x$, and if an object is in a set it is called an element of the set: $x \in S$. Simply put, a linearly ordered set is an arrangement of the elements of a set one after another. If we assume that the universe will exist forever, our example represents a linear arrangement for the set $\mathbb{N}$ of non-negative integers. This specific order is called the natural order on $\mathbb{N}=\mathbb{Z}^+\cup\{0\}$. Keep this example in mind while we define what a linear order is.
We begin by introducing a relation $\rightarrow$ on a set $S$, which determines the arrangement of elements of $S$; for convenience we shall use the symbol $\rightarrow$ whenever there are elements $x,y \in S$, and $x$ comes before (or to the left of) $y$ in the order of elements, writing $x \rightarrow y$.
We need the relation $\rightarrow$ to have some useful properties to become a linear order on $S$. First, the order needs to be consistent in some sense across the whole set, so we require the relation to have the transitivity property: if $x \rightarrow y$ and $y \rightarrow z$, then $x \rightarrow z$. Second, we want the order to apply to every element of the set $S$, so it is necessary for the relation to have the trichotomy property: for all $x,y \in S$, exactly one of the following holds: \begin{align*} x &\rightarrow y& x&=y& y &\rightarrow x \end{align*} Enforcing transitivity and trichotomy properties allows us to avoid ‘loops’ in the linear order like \[ x \rightarrow y \rightarrow z \rightarrow x \] If $\rightarrow$ is a linear order on $S$, then $S$ together with the relation $\rightarrow$ is called a linearly ordered set. Applying this definition to the natural order on $\mathbb{N}$, we see that the relation $\rightarrow$ is represented by the more familiar ‘less than’ relation $<_{\mathbb{N}}$ on the elements of $\mathbb{N}$.
Dense orders
Broadly speaking, there are two types of linear orders: dense and non-dense orders. A linear order on a set is dense if between any two elements of the set one can always find a third element of the same set. Otherwise, a linear order is non-dense. We challenge the reader to answer this question: is it possible to make a dense order on a set with a finite number of elements?
An example of a dense linear order is well known to all of us. It is formed by the set of positive rational numbers, $\mathbb{Q}^+$, and the relation $<_{\mathbb{Q}^+}$. With respect to $<_{\mathbb{Q}^+}$, between any two positive rational numbers, one can find a third positive rational number. For example, if $x,y \in \mathbb{Q}^+$ and $x <_{\mathbb{Q}^+} y$, then their average is also a rational number and is between them with respect to $<_{\mathbb{Q}^+}$:
$$
x <_{\mathbb{Q}^+} \frac{x+y}{2} <_{\mathbb{Q}^+} y
$$
You need an infinite set to have a dense order, but this does not mean that every linear order on an infinite set is dense! The natural order of non-negative integers is not dense, despite being infinite. For example, there is no integer between 2 and 3.
Though we are limited to integers here we can still construct a dense linear order on the set $\mathbb{N}$! Here is an example. On a straight line we start step $0$ by marking out $0$ and $1$. Then at step $1$ we place $2$ at a midpoint between $0$ and $1$ on the straight line. We continue from left to right and at step $2$ find midpoints between $0$ and $2$, $2$ and $1$ and placing $3$ and $4$ at those midpoints respectively. We continue like this forever. From step $1$ onwards, for each $i\in\mathbb{Z}^+$ we fit the numbers $2^{i-1}+1$ through to $2^i$ into all the gaps between numbers in the previous step. The relative location of the first $17$ elements of $\mathbb{N}$ according to the linear order is shown in the figure below.
Constructing the dense order on the natural numbers.
So is this linear order dense? At any step imagine two natural numbers $a$ and $b$ which have no numbers between them. On the next step we will put a number at the midpoint between $a$ and $b$ so that $a$ and $b$ are not ‘immediate’ neighbours any more. We built a dense order indeed! By applying this algorithm, we ‘packed’ all the integers inside the interval $[0,1]$ in order to construct a dense order on $\mathbb{N}$.
Cantorian order
Looking at how many more rationals there seem to be in comparison with the natural numbers (after all, there is an infinite number of rationals between $0$ and $1$), you might expect that every linear order on $\mathbb{Q}^+$ is a dense order. Not at all! German mathematician Georg Cantor showed that there is a linear order on $\mathbb{Q}^+$ that is not dense. Can you come up with one?
Let us introduce the Cantorian order $\overset{\mathbb{Q}^+}{\longrightarrow}$ on $\mathbb{Q}^+$ via a diagram:
The order is created by forming a plane of fractions where numerators increase as one goes diagonally right and denominators increase as one goes diagonally left. Then, by travelling along a path back and forth, one creates a linear order on $\mathbb{Q}^+$. Fractions which simplify are skipped: for example, $1/2$ is present, but $2/4$, $3/6$ and so forth are skipped (they are crossed out on the diagram). We can see that there are no elements in between adjacent fractions, yet this linear order contains every possible fraction, thus covering the whole set $\mathbb{Q}^+$.
Relative to the Cantorian order one can speak of the first positive rational number, the second positive rational number and so on. In other words, one can construct a one-to-one mapping from $\mathbb{Z}^+$, the set of positive integers, to $\mathbb{Q}^+$ since two different positive rational numbers are always in two different positions in the Cantorian order. So there are the same number of positive rational numbers as there are positive integers! If you think of the apparent abundance of positive rational numbers relative to the apparent sparseness of positive integers on the number line, you will find this conclusion a bit mind-bending. Unsurprisingly, Cantor’s contemporaries were shocked by his findings, and many rejected his research. Cantor’s thinking was clearly ahead of his time!
A bigger picture
Georg Cantor.
Cantor had grander ideas than just defining a weird linear order. After all, at the time he was developing what is now known as modern set theory. One of the problems Cantor faced was how to define infinity; he thought of an elegant approach to grasp this ethereal concept. We’ll walk ourselves through it. To start off, we know that every positive integer has a successor—just add $1$ to it. Thus you can count positive integers. The number of elements in a set like $\mathbb{Z}^+$ is called the cardinality of the set. The infinite set whose elements can be counted is called countably infinite. Other sets that can be put into one-to-one mapping with positive integers are also countably infinite. Cantorian order proves that $\mathbb{Q}^+$ is countably infinite.
Countably infinite sets have some interesting properties. All of their subsets are either finite or countably infinite. For example, you can map one-to-one positive integers to positive even integers, which is a subset of $\mathbb{Z}^+$. Another property is that if you combine two countably infinite sets, the resulting set would be countably infinite. Let’s combine the set $\mathbb{N}$ with the set of negative integers $\{\dots,-3,-2,-1\}$ and place the combined set in the following linear order \begin{equation*} 0 \rightarrow -1 \rightarrow 1 \rightarrow -2 \rightarrow 2 \rightarrow -3 \rightarrow 3 \rightarrow \dots \end{equation*} In other words, odd terms are defined by $(i-1)/2$ and even terms are defined by $-i/2$ where $i \in \mathbb{Z}^+$ is the position of the number in the linear order. This linear order shows that the combined set is countably infinite.
But there is more to infinite sets! Cantor showed that there are at least two types of infinity: countable as we have discussed above and uncountable. With uncountably infinite sets it is impossible to construct a one-to-one mapping between their elements and the positive integers. The set of real numbers $\mathbb{R}$ is uncountably infinite. In fact, its subset $[0,1) \subset \mathbb{R}$ turns out to be uncountably infinite too. Cantor showed that there is no one-to-one mapping between $\mathbb{Z}^+$ and $[0,1)$.
So let’s illustrate Cantor’s idea by trying to construct some linear order for the real numbers from $[0,1)$ which is equivalent to the natural order on $\mathbb{Z}^+$ and see where this goes wrong. For our linear order we will be continuously generating random numbers $x \in [0,1)$ and placing them one after another, skipping numbers which were already generated. We might get a linear order similar to this example:
\begin{equation*}
0.739\ldots \rightarrow 0.055\ldots \rightarrow 0.349\ldots \rightarrow \cdots \rightarrow 0.281\ldots7\ldots \rightarrow \cdots
\end{equation*}
Now Cantor’s diagonal argument will help us to construct a mysterious real number from $[0,1)$ that does not fit into the linear order! In our approach we plan to construct the new real number so that it differs from every number in the linear order in at least one digit. The new number has its first digit different from the first digit of the first number in the linear order, its second digit different from the second digit of the second number in the linear order, and so on. We change digits by taking the original digit and adding $1$ to it if the digit is from $0$ to $8$ and substitute the digit $9$ with $0$. In other words, we take diagonal digits of elements from the original linear order and add $1$ to each of them or substitute $9$ with $0$ and construct the new real number from this array of digits. For our example the new real number would be \begin{equation*} 0.860\!\ldots\!8\!\ldots \end{equation*} This new number cannot appear in the linear order: it differs from the first number in the linear order with its first digit, with the second number in the order with its second digit and so on. Yet it is a perfectly good real number! So there are more real numbers in $[0,1)$ than positive integers. We come to a conclusion that these sets do not have equal sizes.
There are plenty more surprises in set theory! We have seen that there are at least two different sizes of infinity, but are there any infinities which are bigger than countable, but smaller than uncountable? For that question Cantor formulated his continuum hypothesis which reads: ‘There is no set whose cardinality is strictly between that of the positive integers and the real numbers.’ The continuum hypothesis can neither be proven nor disproven using the standard axioms of set theory; it stands independent of those axioms. In other words, you can create a set theory where the continuum hypothesis is true, or you can create a set theory where it is not. Cantor’s work creating set theory led to captivating results by other mathematicians, like Russell’s paradox—a famous logical contradiction which has profound implications for the foundations of mathematics. So dive in to learn more!
More from Chalkdust
Can computers prove theorems?
And will we soon all be out of a job? Kevin Buzzard worries us all.
In conversation with Clifford Cocks
We chat to the crypto chief about inventing RSA... but not being able to tell anyone
On √2
Yiannis Petridis connects square roots and continued fractions
Spotlight on: Pamela Harris
Pamela E Harris's story, as told by Talithia Williams
Artificial music
Carmen Cabrera Arnau explores the use of AI in composition
They might not be giants
Angela Brett might not be standing on their shoulders