# The Unapologetic Mathematician

## Dedekind Completion

There’s another sense in which the rational numbers are lacking and the real numbers fix them up. This one is completely about the order structure on $\mathbb{Q}$, and will lead to another construction of the real numbers.

Okay, so what’s wrong with the rational numbers now? In any partial order we can consider least upper or greatest lower bounds. That is, given a nonempty set of rational numbers $S$ the least upper bound or “supremum” $\sup S$ is a rational number so that $\sup S\geq s$ for all $s\in S$ — it’s an upper bound — and if $b$ is any upper bound then $\sup S\leq b$. Similarly the “infimum” $\inf S$ is the greatest lower bound — a lower bound that’s greater than all the other lower bounds.

There’s just one problem: there might not be a supremum of a given set. Even if the set is bounded above, there may be no least upper bound. For instance, the set of all rational numbers $r$ so that $r^2\leq 2$ is bounded above, since $2$ is an example of an upper bound, and $\frac{3}{2}$ is another. But no matter what upper bound we have in hand, we can always find a lower number which is still an upper bound for this set. In fact, the upper bound should be $\sqrt{2}$, but this isn’t a rational number!

Now we define an ordered field to be “Dedekind complete” if every nonempty set $S$ with an upper bound has a least upper bound $\sup S$. Considering the set consisting of the negatives of elements of $S$, every nonempty set with a lower bound will have a least lower bound. The flaw in the rational numbers is that they are not Dedekind complete.

So, in order to complete them, we will use the method of “Dedekind cuts”. Given a nonempty set $S$ with any upper bounds at all, the collection of all the upper bounds forms another set $S'$, and any element of $S$ gives a lower bound for $S'$. We then have the collection of all lower bounds of $S'$, which we call $S''$. Every rational number will be in either $S'$ or $S''$. Given a rational number $r$ if there is an $s\in S$ with $s\geq r$ then $r$ is a lower bound for $S'$, and is thus in $S''$. If not, then $r$ is an upper bound for $S$ and is thus in $S'$. However, one number may be in both $S'$ and $S''$. If $S$ has a rational supremum then it is in both $S'$ and $S''$. There can be no more overlap.

So we’ve come up with a way of cutting the rational numbers into a pair of sets $(X_L,X_R)$ — the “left set” and “right set” of the “cut” $X$ — with $x_L\geq x_R$ for every $x_L\in X_L$ and $x_R\in x_R$. We define a new total order on the set of cuts by $(X_L,X_R)\leq(Y_L,Y_R)$ if $X_L\subseteq Y_L$. Every rational number corresponds to one of the cuts which contains a one-point overlap at that rational number, and clearly this inclusion preserves the order on the rational numbers.

Now if I take any nonempty collection of cuts $(X^\alpha_L,X^\alpha_R)$ with an upper bound (in the order on the set of cuts) we can take the union of all the $X^\alpha_L$ and the intersection of all the $X^\alpha_R$ to get a new cut. The left set contains all the $X^\alpha_L$, and it’s contained in any other left set which contains them, so it’s the least upper bound. Thus the collection of cuts is now Dedekind complete.

We can also add field structures to this completion of an ordered field. For this purpose, it will be useful to denote a generic element of $X_L$ by $x_L$, and assume $x_L$ runs over all elements of $X_L$ wherever it appears. For instance, given cuts $(X_L,X_R)$ and $(Y_L,Y_R)$, we define their sum to be $(\{x_L+y_L\},\{x_R+y_R\})$. The negative of a cut $(X_L,X_R)$ will be $(\{-x_R\},\{-x_L\})$. The product of two positive cuts $(X_L,X_R)$ and $(Y_L,Y_R)$ will have as its right set the collection of all products $\{x_Ry_R\}$, and its left set defined to make this a cut. Finally, the reciprocal of a positive cut $(X_L,X_R)$ will have the set $\{\frac{1}{x_R}\}$ as its right set, and its left set defined to make this a cut.

This suffices to define all the field operations on the set of cuts, and if we start with $\mathbb{Q}$ we get another model of $\mathbb{R}$. I’ll leave verification of the field axioms as an exercise, and come back to prove that the method of cuts and the method of Cauchy sequences are equivalent. Once you play with cuts for a while, you may understand why I came at the real numbers with Cauchy sequences first. The cut approach seems to have a certain simplicity, and it’s less ontologically demanding since we’re only ever talking about pairs of subsets of the rational numbers rather than gigantic equivalence classes of sequences. But in the end I always find cuts to be extremely difficult to work with. Luckily, once we’ve shown them to be equivalent to Cauchy sequences it will establish that the real numbers we’ve been talking about are Dedekind complete, and we can put the messiness of this definition behind us.

December 5, 2007 Posted by | Fundamentals, Numbers, Orders | 15 Comments