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 John Armstrong | Fundamentals, Numbers, Orders

15 Comments »

You’ve incorrectly defined products and quotients of cuts. For example, by your definition, the right set of the square of the cut corresponding to -2 includes the product of 100 and -2, which is -200 (and the left set is empty).

Comment by Dave Milovich | December 5, 2007 | Reply
Never mind, I see the qualifier “positive cut.” You may delete my comment if you wish to avoid confusing your other readers.

Comment by Dave Milovich | December 5, 2007 | Reply
No, it’s worth emphasizing: the definitions of multiplication and reciprocals only apply to positive cuts. With more work you can manage to define it for all numbers, but it gets to be a huge pain, and what I’ve defined is enough to specify the field structure.

Comment by John Armstrong | December 5, 2007 | Reply
A nitpicky comment: you want to define your ordered set to be Dedekind complete if every non-empty set $S$ which possesses an upper bound possesses a least upper bound. (If $S$ is the set of reals, then every real is vacuously an upper bound of the empty set, etc.).

Comment by Todd Trimble | December 5, 2007 | Reply
Ah, you’re right, Todd. I’ll tweak that.

Comment by John Armstrong | December 5, 2007 | Reply
[…] used Dedekind cuts to “complete” the order on the rational numbers — to make sure that every […]

Pingback by Cuts and Sequences are Equivalent « The Unapologetic Mathematician | December 7, 2007 | Reply
According to John Conway (see On Numbers And Games), constructing the reals via Dedekind cuts is enough of a pain — what with all the special cases for multiplication — that it’s worth considering taking the construction as far as the rationals in the traditional way, and then building the reals as a subset of the surreals.

Comment by Blake Stacey | December 7, 2007 | Reply
Mark Chu-Carroll discussed this back in April, FWIW.

Comment by Blake Stacey | December 7, 2007 | Reply
Blake, I do like the surreals, but ultimately they always feel more like a curiosity or a nonstandard model than they do a useful construction. To be honest, I wouldn’t talk about cuts at all if it weren’t just so much easier to show the Dedekind-completeness of the reals with them than with Cauchy sequences.

Comment by John Armstrong | December 7, 2007 | Reply
[…] Whether we use Dedekind cuts or Cauchy sequences to construct the ordered field of real numbers (and it doesn’t matter […]

Pingback by Archimedean Fields « The Unapologetic Mathematician | December 7, 2007 | Reply
And what would life be like without curiosities? 😉

Still, your point is taken (I just have a tendency to note these things “for the record”).

Comment by Blake Stacey | December 7, 2007 | Reply
Asking for all upper-bounded sets to have a sup seems basically the same as asking for Cauchy-completeness.

Comment by isomorphismes | January 10, 2015 | Reply
They’re similar, but distinct. Upper-bounded sets are not necessarily sequences, which are key to the idea of Cauchy completeness. Cauchy sequences, on the other hand, are not required to increase to their limit.

But this similarity does point the way towards showing that the two completions of the real numbers are equivalent. The explicit isomorphism is in the next post.

Comment by John Armstrong | January 10, 2015 | Reply
- Oh, nice! Thanks for the extra details.
  
  I was actually thinking more along the lines that you say that lack of Dedekind-completeness is a “flaw” in ℚ, which is a word common in mathematical rhetoric that I’ve never understood. (Ditto for “nice”.) I get why ℚ doesn’t have this property, but not why that’s bad.
  
  Comment by isomorphismes | January 10, 2015 | Reply
Well, it depends what you want to do with it. For pure algebra, that’s fine. When you want to take limits, though, things become a problem. Let’s say, for instance, you want to use Newton’s method — just using the iterating function, not bothering with where it comes from — to solve $x^2-2=0$ . You set up a sequence with $x_0=1$ and

$\displaystyle x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}=\frac{x_n^2+2}{2x_n}$

This is a purely algebraic function, and every time we start with a rational input we’ll get a rational output. That is, $\{x_n\}\subseteq\mathbb{Q}$ . You can even show that it’s Cauchy. But what’s the limit of the sequence? If you only have the rational numbers to work with, this is a sequence that cannot converge even though we have a really simple, practical reason to want it to.

Comment by John Armstrong | January 11, 2015 | Reply

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects

Subjects
Archives

December 2007

M T W T F S S

1 2

3 4 5 6 7 8 9

10 11 12 13 14 15 16

17 18 19 20 21 22 23

24 25 26 27 28 29 30

31

« Nov Jan »
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider