DLO’s II – uniqueness of rationals

Now that we’ve proven that the rationals exist, we would like to know if it would make a difference had we picked another representative of the countable DLO’s without endpoints as our rationals. Would any candidate have been suitable or is our choice of \left<\mathbb{Q},\prec_\mathbb{Q}\right> special? It turns out that there is no such difference, as given by the theorem:

Theorem (Cantor). Let \left<A,\prec_A\right> and \left<B,\prec_B\right> be countable dense linear orderings without endpoints. Then \left<A,\prec_A\right>\cong\left<B,\prec_B\right>.

Proof. Since both A and B are countable, we list them as A=\{a_i\mid i<\omega\} and B=\{b_i\mid i<\omega\}. Our plan is to construct a series of partial isomorphisms f_i:dom(f_i)\cong ran(f_i), which satisfies f_i\subset f_{i+1} for all i<\omega as well as dom(f_i)\subset A and ran(f_i)\subset B. By doing this, it is straightforward to check that f:=\bigcup_{i<\omega} f_i would grant the desired isomorphism f:A\cong B. We define the f_i's recursively; start by defining f_0:=\emptyset. Now assume that f_i has been defined. We define f_{i+1} through a method called back-and-forth. Firstly, define g:\left<dom(g),\prec_A\right>\to\left<ran(g),\prec_B\right> satisfying dom(g)=dom(f_i)\cup\{a_i\}.

Claim. There is a j<\omega such that if g=f_i\cup\{\left<a_i,b_j\right>\}, then g:\left<dom(g),\prec_A\right>\cong\left<ran(g),\prec_B\right>.

Proof of claim. If a_i is the greatest element of dom(g), then because \left<B,\prec_B\right> has no right endpoint, we can pick b_j to be bigger than every b\in ran(f_i). Likewise if a_i is the least element of dom(g). If neither, we can find a_k,a_l such that a_k\prec_A a_i\prec_A a_l and every other a_j\in dom(g) is either greater than a_l or less than a_k, which is possible due to dom(g) being finite. Then f_i(a_k)\prec_B f_i(a_l) with no b_j\in ran(f_i) satisfying f_i(a_k)\prec_B b_j\prec_B f_i(a_l). Since \left<B,\prec_B\right> is dense, we can pick a b_k\in B such that f_i(a_k)\prec_B b_k\prec_B f_i(a_l). Now set b_j:=b_k.

\lozenge

Now define h:\left<dom(h),\prec_A\right>\to\left<ran(h),\prec_B\right> satisfying ran(h)=ran(g)\cup\{b_i\}. Then with the same argument, mutatis mutandis, as in the previous claim, we find that there is a_j\in A satisfying that if h=g\cup\{\left<a_j,b_i\right>\} then h:\left<dom(h),\prec_A\right>\cong\left<ran(h),\prec_B\right>. Now, set f_{i+1}:=h. Then by the previously stated argument, f:=\bigcup_{i<\omega}f_i:\left<A,\prec_A\right>\cong\left<B,\prec_B\right>.

\blacksquare

As we’re moving on from the rationals to the reals, one might wonder how to characterize the reals from the rationals exactly. There is a notion of completeness to be defined; that is, the notion that captures, say, \sqrt{2}. Or, can it even be defined directly? Interestingly enough, it can be proven that this notion cannot be defined by direct means (that is, through a first-order sentence). To explain why, we state the following corollary without proof:

Corollary. Let \left<A,<\right> and \left<B,<\right> be two DLO’s without endpoints. Then every sentence \sigma (in the language of \{<\}) is true in \left<A,<\right> iff it is true in \left<B,<\right>.

If we now assume that \sigma was a sentence such that \sigma was true in some structure \left<M,\prec_M\right> iff \prec_M was a complete order, then by the corollary, either every DLO without endpoints is completely ordered or none is. But since we know that \left<\mathbb{Q},\prec_\mathbb{R}\right> is a DLO without endpoints which aren’t complete, as well as \left<\mathbb{R},\prec_\mathbb{R}\right> is a DLO without endpoints which is complete, we arrive at a contradiction. So “completeness” can thus not be defined through first-order logic!. As for the question how we can be sure that the reals even exist, you’ll have to be patient for the next blog post!

Advertisements

One thought on “DLO’s II – uniqueness of 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