# DLO’s I – existence of the rationals

One of the very first things we learn at higher math education is the different kinds of number sets, e.g. the naturals, rationals and reals. These are however just taken for granted, and we merely assume that these actually exist and are well-defined. I’ll spend the next few blog posts to characterize the rationals and the reals from facts known from the natural numbers alone. This post will be dedicated to proving the existence of the rationals, i.e. the theorem:

Theorem. There exist a countable dense linear ordering without endpoints.

Proof. Define $S:=\omega\times\omega\backslash 1$ and the relation $\sim\in S\times S$ given by $(a,b)\sim(c,d)\Leftrightarrow ad=bc$.

Claim 1. $\sim$ is an equivalence relation.

Proof of claim. Reflexivity and symmetry follows directly from commutativity of $\cdot$ in $\left<\mathbb{N},+,\cdot\right>$. Transitivity: Assuming $(a,b)\sim(c,d)$ and $(c,d)\sim(e,f)$, meaning $ad=bc$ and $cf=de$ by definition. Now if $c=0$ then $a=e=0$ by necessity as well and we’re done. Assume thus $c\neq 0$, which then implies $adcf=bcde\Leftrightarrow afdc=bedc \stackrel{(\dagger)}{\Leftrightarrow} af=be\Leftrightarrow(a,b)\sim(e,f)$, where the assumption was used at $(\dagger)$.

$\lozenge$

Now define $[(a,b)]_\sim$ for the equivalence class of $(a,b)$ and define $B:=S/\sim:=\{[(a,b)]_\sim\mid(a,b)\in S\}$. These will resemble our intuition of fractions, such that for instance 1/2=2/4, which is stated as $[(1,2)]_\sim=[(2,4)]_\sim$. We now want to define order on our rationals:

Claim 2. $[(a,b)]_\sim\prec_B [(c,d)]_\sim\Leftrightarrow ad defines a relation $\prec_B$ on $B$.

Proof of claim. We need to show that the relation is independent of the choice of representatives. Let thus $(a',b'),(c',d')\in S$ be such that $(a,b)\sim(a',b')$ and $(c,d)\sim(c',d')$. We have to show that $ad. Since $(a,b)\sim(a',b')$ then $ab'=ba'$ and likewise $cd'=dc'$. Then $adb'c'=bca'd'$. Now it is seen that the bi-implication holds, since e.g. assuming $ad then by necessity $a'd' since otherwise $adb'c'.

$\lozenge$

Having defined the order, we show that it fits the DLO requirements and almost satisfying having no endpoints:

Claim 3. $\left$ is a countable dense linear ordering with no right endpoint and $[(0,1)]_\sim$ as left endpoint.

Proof of claim. Since $|B|\leq|S|\leq|\omega\times\omega|=\aleph_0$, $B$ is countable. We show that $\left$ is a DLO. Reflexivity and symmetry follows directly from commutativity of $\cdot$ in $\left<\mathbb{N},+,\cdot\right>$.

Transitive: Assume $[(a,b)]_\sim\prec_B[(c,d)]_\sim$ and $[(c,d)]_\sim\prec_B[(e,f)]_\sim$, meaning $ad and $cf. Then $adcf.

Linearity: Assume $[(a,b)]_\sim\npreceq_B[(c,d)]_\sim$. It has to be shown that $[(c,d)]_\sim\prec[(a,b)]_\sim$. By definition, $[(a,b)]_\sim\nprec_B[(c,d)]_\sim\Leftrightarrow ad\nless bc$ and $[(a,b)]_\sim\neq[(c,d)]_\sim$ $\Leftrightarrow ad\neq bc$. Thus by totality of <, $ad>bc\Leftrightarrow [(c,d)]_\sim\prec_B[(a,b)]_\sim$.

Density: Assume $[(a,b)]_\sim\prec_B[(c,d)]_\sim\Leftrightarrow ad. Since both $2ad$ and $2bc$ are even numbers, there exist an odd number $2ad+1$ satisfying $2ad<2ad+1<2bc$. Then $2ad2bd<(2ad+1)2bd$ as well, implying $[(2ad,2bd)]_\sim\prec_B[(2ad+1,2bd)]_\sim$ and thus $[(a,b)]_\sim\prec_B[(2ad+1,2bd)]_\sim$ and likewise to show that $[(2ad+1,2bd)]_\sim\prec_B[(c,d)]_\sim$.

Lastly we have to prove the facts about the endpoints. It has no right endpoint since given any $[(a,b)]_\sim$ then $[(a,b)]_\sim\prec_B[(a+1,b)]_\sim$ since $ab. Assume now that $[(0,1)]_\sim$ is not the left endpoint. Then there is $[(a,b)]_\sim$ satisfying $[(a,b)]_\sim\prec_B[(0,1)]_\sim$, meaning $1\cdot a, but $a\in\omega$, contradiction.

$\lozenge$

Now define $A:=B\backslash[(0,1)]_\sim$ and let $\prec_A:=\prec_B\upharpoonright A\times A$. Following intuition, this should fix our problem with the left endpoint – and indeed, our intuition is correct, as the following claim shows:

Claim 4. $\left$ is a countable dense linear ordering with no endpoints.

Proof of claim. Clearly it is a DLO with no right endpoint as removing a single element doesn’t change these properties. Now given $[(a,b)]_\sim$ we have $[(a,b+1)]_\sim\prec_A[(a,b)]_\sim$ since $b, due to $a\neq 0$.

$\lozenge$

Now technically we’ve proven our stated theorem, but we’d like to show our usual idea of the rationals also exists, which includes “the negative fractions”. This requires a reversed order, which motivates the following claim:

Claim 5. $\left< A,\succ_A\right>$ is a countable dense linear ordering with no endpoints.

Proof of claim. Only the order is reversed, so countability and DLO properties still hold. Only change is that $[(0,1)]_\sim$ is now the right endpoint instead of left, but an argument analogous to that in claim 4 shows that it has no endpoints as well.

$\lozenge$

Now finally define the well-known rationals $\left<\mathbb{Q},\prec_\mathbb{Q}\right>:=\left^\frown\left$, which is the two orderings concatenated after each other (juxtaposition). We show the final claim that this in fact fits the requirement:

Claim 6. $\left<\mathbb{Q},\prec_\mathbb{Q}\right>$ is a countable dense linear ordering with no endpoints.

Proof of claim. Since $|\omega\cup\omega|=\aleph_0$, $\mathbb{Q}$ is countable due to $|A\cup B|\leq|\omega\cup\omega|$. Since $\left$ is a DLO without endpoints by claim 5 and $\left$ is a DLO without a right endpoint and $[(0,1)]_\sim$ as left endpoint by claim 3, then $\left<\mathbb{Q},\prec_\mathbb{Q}\right>$ has no endpoints and is a DLO as well.

$\lozenge$
$\blacksquare$

And there we have it! The rationals as we know them along with their well-known properties actually exist. But the question is now if there are different “kinds” of rationals, or are they in fact unique? We already saw another DLO without endpoints in claim 4 of the proof, but is this version equivalent to our rationals? This will be the focus of the next post!