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 special? It turns out that there is no such difference, as given by the theorem:
Theorem (Cantor). Let and be countable dense linear orderings without endpoints. Then .
Proof. Since both and are countable, we list them as and . Our plan is to construct a series of partial isomorphisms , which satisfies for all as well as and . By doing this, it is straightforward to check that would grant the desired isomorphism . We define the recursively; start by defining . Now assume that has been defined. We define through a method called back-and-forth. Firstly, define satisfying .
Claim. There is a such that if , then .
Proof of claim. If is the greatest element of , then because has no right endpoint, we can pick to be bigger than every . Likewise if is the least element of . If neither, we can find such that and every other is either greater than or less than , which is possible due to being finite. Then with no satisfying . Since is dense, we can pick a such that . Now set .
Now define satisfying . Then with the same argument, mutatis mutandis, as in the previous claim, we find that there is satisfying that if then . Now, set . Then by the previously stated argument, .
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, . 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 and be two DLO’s without endpoints. Then every sentence (in the language of is true in iff it is true in .
If we now assume that was a sentence such that was true in some structure iff was a complete order, then by the corollary, either every DLO without endpoints is completely ordered or none is. But since we know that is a DLO without endpoints which aren’t complete, as well as 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!