# DLO’s III – from rational to real

From the last two posts we managed to prove both the existence and the uniqueness of the rationals, which could be done by explicit definitions using known facts about the natural numbers. However, we also showed that the property that distinguished the real numbers from the rationals, namely completeness, couldn’t be defined in first-order logic. This also means that we can’t proceed to prove the existence of the reals in a direct matter as the rationals, and we will do so by indirect means. More specifically, the proof will consist of the following steps, illustrated in figure 1 below:

1. Start of with our “rationals” $\left$
2. Define from $A$ another structure $\left$ which satisfies completeness
3. Construct $\left$, being dense in $\left$, which is isomorphic to $\left$
4. Find an isomorphic copy $\left$ of $\left$, which satisfies that $A\subseteq B$
5. This results in $\left$ being dense in the complete $\left$
6. $\left$ is then our “reals”

Figure 1. Structure of the proof.

But before we state the theorem and get started on the actual proof, we need to get some definitions down:

Definition 1. Let $\left$ and $\left$ be linear orderings with $A\subseteq B$. Then $\left$ is said to be dense in $\left$ if for every $x,y\in B$ there is $z\in A$ such that $x\prec_B y\to x\prec_B\ z\prec_B y$.

Definition 2. A linear ordering $\left$ is said to have the supremum property if for every subset $S\subseteq A$, if $S$ has an upper bound in $\left$, it has a supremum in $\left$ as well.

The last definition is crucial for the proof and underlines the whole idea of it as well, the notion of Dedekind cuts:

Definition 3. Let $\left$ be a linear ordering and let $C\subsetneq A$ be a nonempty proper subset. Then $L$ is said to be a left-cut if it satisfies:

• $\forall x\in A, y\in C(x\prec_A y\to x\in C)$
• $\forall x\in C\exists y\in C(x\prec_A y)$

Said in words, $C$ is a nonempty proper subset of $A$ closed to the left and with no right endpoint. We can now state our theorem, which due to Dedekind:

Theorem (Dedekind). Let $\left$ be a countable dense linear ordering without endpoints. Then there exist $\left$ such that

• $\left$ is a dense linear ordering without endpoints
• $\left\leq\left$
• $A$ is dense in $\left$
• $\left$ has the supremum property

Proof. Define $B_C:=\{C\subseteq A\mid C\text{ is a left-cut}\}$ and the ordering $\prec_{B_C}$ defined as $C_1\prec_{B_C}C_2\Leftrightarrow C_1\subsetneq C_2$. We want to prove that this defined $\left$ fits the demand of the second part of the aforementioned “proof plan”, which is split up into the following three claims:

Claim 1. $\left$ is a strict linear ordering.
Proof of claim.
Irreflexivity and transitivity is trivial from the definition, so we show that the ordering is linear. Let $C_1,C_2\in B_C$ and assume that $C_2\nsubseteq C_1$; we show $C_1\subsetneq C_2$. Since $C_2\nsubseteq C_1$, we can pick $y\in C_2\backslash C_1$. Let $x\in C_1$. Because $\left$ is a linear ordering, either $x\preceq_A y$ or $y\prec_A x$. Suppose $x\preceq_A y$. Then because $C_2$ is closed to the left, $x\in C_2$. Suppose instead that $y\prec_A x$. Then because $C_1$ is closed to the left, $y\in C_1$, contradiction; so $x\in C_2$. Since $x$ was arbitrary, $C_1\subsetneq C_2$; being proper because $y\in C_2\backslash C_1$.

$\lozenge$

Claim 2. $\left$ has no endpoints.
Proof of claim. Let $C\in B_C$. Since $C$ is a left-cut, $C\neq\emptyset$ and $C\neq A$; so pick $y\in C$ and $z\in A\backslash C$. Define $C_y:=\{x\in A\mid x\prec_A y\}$ and $C_z:=\{x\in A\mid x\prec_A z\}$, which are clearly left-cuts and satisfies $C_y\subsetneq C\subseteq C_z$. Since $\left$ has no right endpoint, one can pick $z'\in A$ such that $z\prec_A z'$. Then $C_z\subsetneq C_{z'}$, meaning $C_y\subsetneq C\subsetneq C_{z'}$; so $C$ is not an endpoint. Since the choice of $C$ was arbitrary, $\left$ has no endpoints.

$\lozenge$

Claim 3. $\left$ has the supremum property.
Proof of claim. Suppose $S\subseteq B_C$ is a nonempty subset with an upper bound in $\left$. Define $M:=\bigcup S$. We must show that $M\in B_C$ (i.e. is a left-cut) and that $\sup(S)=M$. The following must be satisfied:

1. $M\neq\emptyset$
2. $M\subsetneq B_C$
3. $\forall x\in A, y\in M(x\prec_A y\to x\in M)$
4. $\forall x\in M\exists y\in M(x\prec_A y)$
5. $M$ is an upper bound in $\left$
6. $M$ is the least such upper bound.

$M$ is clearly nonempty since $S$ is. For (2) let $s\in S$. Then $s$ is a left-cut and thus $s\subsetneq A$. Thus for every $x\in s$, $s\in A$, meaning $M\subseteq A$. Moreover, $M\neq A$, since for every $x\in M$ there is $y\in A$ such that $x\prec_A y$, due to $x$ being in some left-cut. (3) and (4) follow analogously. (5) is seen by definition of union, since $\forall s\in S(s\subset M)$, meaning $\forall s\in S(s\preceq_{B_C} M)$. Lastly we show (6), that $M$ is the least such. Let $N\in B_C$ be an upper bound for $S$. We must show that $M\subseteq N$. Suppose it is not the case, meaning that $N\subsetneq M$ by linearity of the ordering. Then we can pick some $y\in M\backslash N$. Since $y\in M$, $y$ is in some left-cut $s\in S$. But then since $s\subseteq N$, $y\in N$, contradiction.

$\lozenge$

By having found that $\left$ satisfies completeness, we will now find a substructure $\left\leq\left$, which satisfies $\left\cong\left$. The reason for this is because we cannot be sure sure that $A\subset B_C$. Define then for each $y\in A$ the set $L_y:=\{x\in A\mid x\prec_A y\}$, $A_C:=\{L_y\mid y\in A\}$ and lastly $\prec_{A_C}:=\prec_{B_C}\upharpoonright A_C$. Now construct the map $g:\left\cong\left$, which is clearly seen to be an isomorphism by construction of $A_C$.

Claim 4. $\left$ is dense in $\left$.
Proof of claim.
Suppose $K,M\in B_C$ with $K\prec_{B_C} M$, meaning $K\subsetneq M$ by definition. Now pick $y\in M\backslash K$. Since $M$ is a left-cut, it has no right endpoint, so we can pick $z\in M$ such that $y\prec_A z$. Now $K\preceq_{B_C} L_y\prec_{B_C} L_z \prec_{B_C} M$, making $L_z\in A_C$ satisfy the condition.

$\lozenge$

This completes the third point on our proof agenda. As our last task, we would like to construct $\left$ satisfying $\left\cong\left$. Construct the map $f:B_C\to ran(f)$ by $f(L_x):=x$ if $x\in A$ and for $M\in B_C\backslash A_C$ define $g(M):=\left$. First of all, $f$ is clearly an injection due to $\left=\left\Leftrightarrow M=N$. Also, $\left\notin A$, since else $A\in\{A\}\in\{\{A\},\{A,M\}\}=\left\in A$, contradicting Foundation.

Now, define $\left$ as $B:=ran(f)$ and for all $L,M\in B_C$, $L\prec_{B_C}M\Leftrightarrow f(L)\prec_B f(M)$. Now $f$ is clearly seen to be the wanted isomorphism.

$\blacksquare$