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<A,\prec_A\right>
  2. Define from A another structure \left<B_C,\prec_{B_C}\right> which satisfies completeness
  3. Construct \left<A_C,\prec_{A_C}\right>, being dense in \left<B_C,\prec_{B_C}\right>, which is isomorphic to \left<A,\prec_A\right>
  4. Find an isomorphic copy \left<B,\prec_B\right> of \left<B_C,\prec_{B_C}\right>, which satisfies that A\subseteq B
  5. This results in \left<A,\prec_A\right> being dense in the complete \left<B,\prec_B\right>
  6. \left<B,\prec_B\right> is then our “reals”

Picture 1
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<A,\prec_A\right> and \left<B,\prec_B\right> be linear orderings with A\subseteq B. Then \left<A,\prec_A\right> is said to be dense in \left<B,\prec_B\right> 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<A,\prec_A\right> is said to have the supremum property if for every subset S\subseteq A, if S has an upper bound in \left<A,\prec_A\right>, it has a supremum in \left<A,\prec_A\right> 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<A,\prec_A\right> 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<A,\prec_A\right> be a countable dense linear ordering without endpoints. Then there exist \left<B,\prec_B\right> such that

  • \left<B,\prec_B\right> is a dense linear ordering without endpoints
  • \left<A,\prec_A\right>\leq\left<B,\prec_B\right>
  • A is dense in \left<B,\prec_B\right>
  • \left<B,\prec_B\right> 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<B_C,\prec_{B_C}\right> fits the demand of the second part of the aforementioned “proof plan”, which is split up into the following three claims:

Claim 1. \left<B_C,\prec_{B_C}\right> 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<A,\prec_A\right> 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<B_C,\prec_{B_C}\right> 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<A,\prec_A\right> 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<B_C,\prec_{B_C}\right> has no endpoints.

\lozenge

Claim 3. \left<B_C,\prec_{B_C}\right> has the supremum property.
Proof of claim. Suppose S\subseteq B_C is a nonempty subset with an upper bound in \left<B_C,\prec_{B_C}\right>. 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<B_C,\prec_{B_C}\right>
  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<B_C,\prec_{B_C}\right> satisfies completeness, we will now find a substructure \left<A_C,\prec_{A_C}\right>\leq\left<B_C,\prec_{B_C}\right>, which satisfies \left<A,\prec_A\right>\cong\left<A_C,\prec_{A_C}\right>. 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<A,\prec_A\right>\cong\left<A_C,\prec_{A_C}\right>, which is clearly seen to be an isomorphism by construction of A_C.

Claim 4. \left<A_C,\prec_{A_C}\right> is dense in \left<B_C,\prec_{B_C}\right>.
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<B,\prec_B\right> satisfying \left<B,\prec_B\right>\cong\left<B_C,\prec_{B_C}\right>. 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<A,M\right>. First of all, f is clearly an injection due to \left<A,M\right>=\left<A,N\right>\Leftrightarrow M=N. Also, \left<A,M\right>\notin A, since else A\in\{A\}\in\{\{A\},\{A,M\}\}=\left<A,M\right>\in A, contradicting Foundation.

Now, define \left<B,\prec_B\right> 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

Advertisements

One thought on “DLO’s III – from rational to real

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s