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<bc 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<bc\Leftrightarrow a'd'<b'c'. 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<bc then by necessity a'd'<b'c' since otherwise adb'c'<bca'd'.

\lozenge

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

Claim 3. \left<B,\prec_B\right> 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<B,\prec_B\right> 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<bc and cf<de. Then adcf<bcde\Leftrightarrow afcd<becd \Leftrightarrow af<be.

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<bc\Leftrightarrow 2ad<2bc. 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<b(a+1). 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<b\cdot 0, 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<A,\prec_A\right> 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<b+1\Leftrightarrow ab<a(b+1), 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<A,\succ_A\right>^\frown\left<B,\prec_B\right>, 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<A,\succ_A\right> is a DLO without endpoints by claim 5 and \left<B,\prec_B\right> 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!

Advertisements

2 thoughts on “DLO’s I – existence of the rationals

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