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 $x$ is determined by its lower set $L_x$ and its upper set $U_x$:

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)$ of sets of rational numbers satisfying these conditions:

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

Actually, this definition is redundant; any pair $(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)$ is a Dedekind cut, then we define $a<x$ to mean that $a\in L$ and define $x<b$ to mean that $b\in U$.

Motivation

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

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

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

Properties

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

• Asymmetry: If $x<y$ and $y<x$, pick $a$ such that $x<a<y$ and $b$ such that $y<b<x$. Applying (8) in two ways, $a<b$ and $b<a$, which is impossible.
• Comparison: If $x<z$ and $y$ is a Dedekind cut, then pick $a$ such that $x<a<z$. Using (5) or (6), we can generalise this to two rational numbers $a$ and $b$ such that $x<a<b<z$. Applying (7) to $a<b$, we get $x<y$ (if $a<y$) or $y<z$ (if $y<b$).
• Connectedness: Suppose that $x<y$ and $y<x$ both fail, and suppose that $a<y$. By (5), we have $a<b<y$ for some $b$. Applying (7), we have $a<x$ or $x<b$. Since $x<b<y$ contradicts our assumptions, we have $a<x$. In summary, $a<y\Rightarrow a<x$. We can prove $a<x\Rightarrow a<y$, $b<x\Rightarrow b<y$, and $b<y\Rightarrow b<x$ similarly. Therefore, $x$ and $y$ are equal (as pairs of subsets).

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

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

• If $x<y$ as rational numbers, then let $a$ be the rational number $(x+y)/2$; we have $x<a<y$, so $x<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)$ 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 $\sup L$ be the union of the left halves of the cuts that appear in $L$, and let $\inf U$ be the union of the right halves of the cuts that appear in $U$. Then one can prove that $x≔(\sup L,\inf U)$ is a Dedekind cut (of rational numbers), and furthermore that $L$ and $U$ may be recovered from $x$ 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}$.

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 $<$ is a connected relation on Dedekind cuts fails; but instead we identify cuts $x$ and $y$ whenever $x\le y\le 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<b$ are rational numbers with $b\in L$, then $a\prime \in L$ for some $a\prime <a$.
• 4′: If $a<b$ are rational numbers with $a\in U$, then $b\prime \in U$ for some $b\prime >b$.
• 7′: If $a<b$ are rational numbers, then $a\prime \in L$ for some $a\prime <a$ or $b\prime \in U$ for some $b\prime >b$.

Just as (3,4) follow from (7,8), so (3′,4′) follow from (7′,8). Again, $<$ 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 $a$ belongs to $L$ if and only if there exists a rational number $b\in L$ such that $a<b$.
• (4&6): A rational number $b$ belongs to $U$ if and only if there exists a rational number $a\in U$ such that $a<b$.

Covering cuts

Another approach is to strengthen (7):

• 7″: Every rational number belongs to $L$ or $U$.

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 $L$ and demand (1,3,5), the axioms that refer only to $L$. Any such set $L$ of rational numbers is a lower cut. Similarly, a set $U$ that satisfies (2,4,6) is an upper cut. If we demand that the set $L$ or $U$ 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 $L$ and $U$, 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:

In addition, the unbounded lower cut $L≔\mathbb{Q}$ represents $\mathrm{\infty }$, while the unbounded upper cut $U≔\mathbb{Q}$ represents $-\mathrm{\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},\varnothing )$, or $(\varnothing ,\mathbb{Q})$. While the bounded cuts represent real numbers, the other two extended cuts represent $\pm \mathrm{\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]$ for $x\le y$, where $x$ is a lower real and $y$ is an upper real. If we use only (1–6), then we allow for back-to-front intervals $[x,y]$ where $x\le 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 $ℝ$ (although you have to know what $ℝ$ is to state this). For example, we could start with the real algebraic numbers or the computable number?s.

The basic theory also generalises immediately to any unbounded, dense? linearly ordered set $S$; again, the result is equivalent as long as $S$ 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 (if we ever discuss it there) or Sections 4.31–39 of HAF.

References

• Richard Dedekind; 1872; Stetigkeit und irrationale Zahlen:

  • Google Books (in Fraktur font),
  • retyped

• Paul Taylor; 2007–2009(?); Dedekind cuts

• HAF, 4.31–4.39