nLab
Dedekind cut

Dedekind cuts

Idea

Dedekind cuts are a way to make precise the idea that a real number is that which can be approximated (in the absolute value metric) by rational numbers.

In 1872, Richard Dedekind published Stetigkeit und irrationale Zahlen (Continuity and irrational numbers), in which he pointed out that a real number may be uniquely determined its order relationships with rational numbers. That is, the real number xx is determined by its lower set L xL_x and its upper set U xU_x:

(1)L x{a:|a<x}, U x{b:|x<b}. \begin {split} L_x \coloneqq \{ a\colon \mathbb{Q} \;|\; a \lt x \} ,\\ U_x \coloneqq \{ b\colon \mathbb{Q} \;|\; x \lt b \} .\end {split}

Dedekind had found great success understanding the ‘ideal numbers’ of ring theory as certain sets, which are what we now understand as ideals. So he defined a ‘real number’ as a pair of sets of rational numbers, the lower and upper sets shown above (actually a slight variation). Such a pair of sets of rational numbers he called a ‘Schnitt’ (English ‘cut’), nowadays called a ‘Dedekind cut’.

Definitions

Exactly which pairs of sets of rational numbers can appear this way? We will define a Dedekind cut to be any pair (L,U)(L,U) of sets of rational numbers satisfying these conditions:

  1. LL is inhabited; that is, some rational number belongs to LL.
  2. Similarly, UU is inhabited.
  3. LL is downward-closed; that is, if a<ba \lt b are rational numbers with bLb \in L, then aLa \in L.
  4. Similarly, UU is upward-closed: if a<ba \lt b are rational numbers with aUa \in U, then bUb \in U.
  5. LL is upward-open; that is, if aLa \in L, then a<ba \lt b for some bLb \in L.
  6. Similarly, UU is downward-open: if bUb \in U, then a<ba \lt b for some aUa \in U.
  7. If a<ba \lt b are rational numbers, then aLa \in L or bUb \in U.
  8. If aLa \in L and bUb \in U, then a<ba \lt b.

Actually, this definition is redundant; any pair (L,U)(L,U) that satisfies (7&8) must also satisfy (3&4). However, we state (3&4) explicitly to simplify the description of the variations below.

If x(L,U)x \coloneqq (L,U) is a Dedekind cut, then we define a<xa \lt x to mean that aLa \in L and define x<bx \lt b to mean that bUb \in U.

Motivation

The point of condition (7) is that we can estimate xx as closely as we like by choosing appropriate rational numbers.

This is entirely constructive. We have a 0<xa_0 \lt x for some a 0a_0 (by 1) and x<b 0x \lt b_0 for some b 0b_0 (by 2), so if we wish to estimate xx to within a positive rational number ϵ\epsilon, then we simply let nn be 2/ϵ\lceil{2/\epsilon}\rceil and apply (7) to each of the finitely many (n(b 0a 0)\lceil{n(b_0-a_0)}\rceil) rational numbers with denominator nn that lie between a 0a_0 and b 0b_0. This will eventually give us a numerator ii such that (i1)/n<x<(i+1)/n(i-1)/n \lt x \lt (i+1)/n, so we have estimated xx within 2/nϵ2/n \leq \epsilon. Alternatively, to estimate xx to nn digits after a decimal point (with an uncertainty of 11 in the last digit), apply (7) to each of the (b 0a 0)×10 n\lceil{(b_0-a_0) \times 10^n}\rceil numbers between a 0a_0 and b 0b_0 that have nn digits after the decimal point. (We can never constructively determine the final digit with perfect certainty; for example, if we successively estimate xx as 0.5,0.50,0.500,0.5, 0.50, 0.500, \ldots, no finite number of such estimates can ever ensure that xx won't come out to 0.499999980.4999\cdots9998 when we go one digit farther.)

Besides giving us a place to begin our estimation, (1&2) ensure that xx is finite. Condition (8) enforces the transitivity law a<x<ba<ba \lt x \lt b \implies a \lt b; (3&4) are likewise forms of transitivity. (5&6) ensure that, even if xx happens to be a rational number, we are using the sets L xL_x and U xU_x given in (1) instead of their closures (defined with \leq instead of <\lt).

Properties

We define x<yx \lt y to mean that there exists a rational number aa such that x<a<yx \lt a \lt y; that is, some rational number belongs to both the upper set of xx and the lower set of yy. It is then straightforward to prove that <\lt is a linear order:

  • Asymmetry: If x<yx \lt y and y<xy \lt x, pick aa such that x<a<yx \lt a \lt y and bb such that y<b<xy \lt b \lt x. Applying (8) in two ways, a<ba \lt b and b<ab \lt a, which is impossible.
  • Comparison: If x<zx \lt z and yy is a Dedekind cut, then pick aa such that x<a<zx \lt a \lt z. Using (5) or (6), we can generalise this to two rational numbers aa and bb such that x<a<b<zx \lt a \lt b \lt z. Applying (7) to a<ba \lt b, we get x<yx \lt y (if a<ya \lt y) or y<zy \lt z (if y<by \lt b).
  • Connectedness: Suppose that x<yx \lt y and y<xy \lt x both fail, and suppose that a<ya \lt y. By (5), we have a<b<ya \lt b \lt y for some bb. Applying (7), we have a<xa \lt x or x<bx \lt b. Since x<b<yx \lt b \lt y contradicts our assumptions, we have a<xa \lt x. In summary, a<ya<xa \lt y \implies a \lt x. We can prove a<xa<ya \lt x \implies a \lt y, b<xb<yb \lt x \implies b \lt y, and b<yb<xb \lt y \implies b \lt x similarly. Therefore, xx and yy are equal (as pairs of subsets).

As usual with a linear order, we define xyx \leq y to mean that y<xy \lt x is false. In particular, connectedness of <\lt corresponds to antisymmetry of \leq.

We can also derive a Dedekind cut from any rational number xx by taking (1) to be the definition of xx as a Dedekind cut. Thus every rational number is interpreted as a real number. This is a strict inclusion of linear orders:

  • If x<yx \lt y as rational numbers, then let aa be the rational number (x+y)/2(x+y)/2; we have x<a<yx \lt a \lt y, so x<yx \lt y as real numbers.

In this way, the Dedekind cuts form an extension of the linearly ordered set of rational numbers. More than that, this extension is Dedekind-complete, which basically means that you cannot extend further by taking Dedekind cuts of Dedekind cuts.

To be explicit, suppose that (L,U)(L,U) is a pair of sets of Dedekind cuts (rather than of rational numbers) that satisfies (1–8), using Dedekind cuts in place of rational numbers. Let supL\sup L be the union of the left halves of the cuts that appear in LL, and let infU\inf U be the union of the right halves of the cuts that appear in UU. Then one can prove that x(supL,infU)x \coloneqq (\sup L, \inf U) is a Dedekind cut (of rational numbers), and furthermore that LL and UU may be recovered from xx as in (1), again using Dedekind cuts in place of rational numbers.

We say that the Dedekind cuts form the Dedekind completion of the linear order \mathbb{Q}.

Remark

Being a member of the lower (resp. the upper) set of a Dedekind cut is almost stable (under double negation): For any rational number aa it holds that aLa \in L iff there exists a rational number b>ab \gt a such that ¬¬(bL)\neg\neg(b \in L). “Only if” is by condition (5). “If” is by condition (7): We have aLa \in L or bUb \in U. In the first case we’re done; in the second case it follows that ¬(bL)\neg(b \in L) by (8), which is a contradiction to ¬¬(bL)\neg\neg(b \in L).

Remark

Equality of Dedekind cuts is stable (under double negation).

Variations

A Dedekind cut is, in full clarity, a bounded, open, rounded, located, two-sided Dedekind cut of rational numbers. But there are several simple variations on the definition above, many of which may be found in the literature.

Overdetermined cuts

The conditions (5&6) are not really necessary. If you leave them out, then the result that <\lt is a connected relation on Dedekind cuts fails; but instead we identify cuts xx and yy whenever xyxx \leq y \leq x. Then the linearly ordered set of real numbers becomes a quotient set of the set of cuts. In a similar vein, we can weaken (3,4,7) as follows:

  • 3′: If a<ba \lt b are rational numbers with bLb \in L, then aLa' \in L for some a<aa' \lt a.
  • 4′: If a<ba \lt b are rational numbers with aUa \in U, then bUb' \in U for some b>bb' \gt b.
  • 7′: If a<ba \lt b are rational numbers, then aLa' \in L for some a<aa' \lt a or bUb' \in U for some b>bb' \gt b.

Just as (3,4) follow from (7,8), so (3′,4′) follow from (7′,8). Again, <\lt is no longer connected, but we still get a linear order on a quotient set. The weakest axiom system that will give the correct linear order on the quotient is (1,2,7′,8). Incidentally, you can also recover the original definition using (3,4,7′) in place of (7).

To emphasise that one does require (5,6), one may speak of an open cut. To emphasise that one does require (3,4), one may speak of a rounded cut.

Note that we may elegantly (although requiring a fancier logic) combine (3,4,5,6) into two conditions as follows:

  • (3&5): A rational number aa belongs to LL if and only if there exists a rational number bLb \in L such that a<ba \lt b.
  • (4&6): A rational number bb belongs to UU if and only if there exists a rational number aUa \in U such that a<ba \lt b.

Covering cuts

Another approach is to strengthen (7):

  • 7″: Every rational number belongs to LL or UU.

While (7″) alone does not imply (7), it does together with (8). Also note that, using (8), we can even change ‘or’ to ‘xor’ in (7″).

The cuts that satisfy (1–6, 7″, 8) are precisely the cuts that define irrational numbers. If we remove either (5) or (6), then the resulting axioms define one cut for each rational number as well. If we remove both (5) and (6), then we get two cuts for each rational number and must (as in the previous section) pass to a quotient; this was actually Dedekind's original 1872 system. These versions are not acceptable constructively (and we cannot even prove that they are closed under addition), but they work fine if you use excluded middle. (Actually, the somewhat weaker limited principle of omniscience? seems to suffice.)

One-sided cuts

Suppose that we consider only LL and demand (1,3,5), the axioms that refer only to LL. Any such set LL of rational numbers is a lower cut. Similarly, a set UU that satisfies (2,4,6) is an upper cut. If we demand that the set LL or UU is a proper subset, then we have a bounded lower/upper cut. If we wish to emphasise that we are discussing a cut as defined above, with both LL and UU, we speak of a two-sided cut.

Assuming excluded middle, every bounded lower or upper cut generates a two-sided cut, by whichever of these rules is needed:

(2)U{b:|aL,a<b}, L{a:|bU,a<b}. \begin {split} U \coloneqq \{ b\colon \mathbb{Q} \;|\; \forall a \in L,\; a \lt b \} ,\\ L \coloneqq \{ a\colon \mathbb{Q} \;|\; \forall b \in U,\; a \lt b \} .\end {split}

In addition, the unbounded lower cut LL \coloneqq \mathbb{Q} represents \infty, while the unbounded upper cut UU \coloneqq \mathbb{Q} represents -\infty.

In constructive mathematics, one-sided cuts define a potentially more general notion of real number, called a lower real or upper real (with the same direction as the cut). Unlike the covering cuts in the previous section, these are actually of interest constructively. If we wish to emphasise or clarify that we are discussing a two-sided cut as in our original definition, rather than a one-sided cut which has been made two-sided through (2) (which may not satisfy (7) constructively), then we may speak of a located cut.

Unbounded cuts

If we drop conditions (1&2), then the result is an extended cut; these represent extended real numbers. If we wish to emphasise or clarify that we are discussing a cut that satisfies (1,2), then we may speak of a bounded cut.

By excluded middle, every extended cut is either a Dedekind cut, (,)(\mathbb{Q},\empty), or (,)(\empty,\mathbb{Q}). While the bounded cuts represent real numbers, the other two extended cuts represent ±\pm\infty.

Interval cuts

If we drop (7) (but keep 3&4), then the result is an interval cut; these represent intervals of the form [x,y][x,y] for xyx \leq y, where xx is a lower real and yy is an upper real. If we use only (1–6), then we allow for back-to-front intervals [x,y][x,y] where xyx \leq y is no longer required. Even classically, we cannot represent back-to-front intervals as subsets of the real line, but it is still possible to compute with them.

Whereas a located Dedekind cut can be approximated as closely as we wish, an interval cut represents a number as we measure it in the real world, where we may not be technically able (or even theoretically able, as in quantum physics) to make a more precise measurement. A back-to-front interval indicates that we have made contradictory measurements, perhaps as a result of experimental error.

An article on interval arithmetic? is probably the right place to talk about these systems (although there are many varieties of interval arithmetic).

Cuts of other numbers

Instead of starting with rational numbers, we could use any dense? subset of \mathbb{Q}; the result would be equivalent. For example, we could start with the dyadic number?s to show more explicitly how real numbers are represented by rational numbers written in binary notation. Alternatively, we could start with something larger than (or incomparable with) \mathbb{Q} that is still a dense subset of \mathbb{R} (although you have to know what \mathbb{R} is to state this). For example, we could start with the real algebraic numbers or the computable numbers.

The basic theory also generalises immediately to any unbounded, dense? linearly ordered set SS; again, the result is equivalent as long as SS is a countably infinite set. The theory may be generalised further even to orders which may not be unbounded, dense, or even linear, but this requires modifications; see Dedekind completion for unbounded dense quasiorders or Sections 4.31–39 of HAF for even more generality.

References

Revised on September 25, 2014 11:35:46 by Ingo Blechschmidt (137.250.162.16)