An example with Dedekind cuts

In this post, I will briefly describe an example in computability theory that is well known, but not easy to find in the literature. It gives one reason why Dedekind cuts are difficult to work with computationally.

Theorem. There is no (uniform) algorithm that, given two left Dedekind cuts $A$ and $B$, produces a left cut for the number $A – B$.

Here a left Dedekind cut is a nonempty, downward closed subset of the rationals that does not contain every rational.

Proof. Consider a computable functional $\phi$ which is supposed to compute the cut corresponding to the difference of two real numbers that are presented by left Dedekind cuts. We can therefore assume that $\phi(A,B)$ is total when $A$ and $B$ are left Dedekind cuts.

Let $A$ be a Dedekind cut for $\pi$. The cut $B$ will be decided in stages. Let $(b_i)$ be a strictly increasing sequence of rationals that converges to $\pi$ and let $(c_i)$ be a strictly decreasing sequence of rationals that converges to $\pi$. Let $C = \phi(A,A)$. Then $C$ is, by assumption, a left Dedekind cut. We will have two cases depending on whether $0 \in C$ or not.

In the case that $0 \in C$, choose $N$ large enough so that, during the computation of $\phi(A,A)$, no rational number between $b_N$ and $c_N$ was queried. Then let $B$ be a Dedekind cut for some irrational number in the interval $(\pi, c_N)$. We should have that $0 \not \in \phi(A,B)$, because $A – B < 0$, but $\phi(A,B)$ will be the same as $\phi(A,A)$ because of the construction of $B$. So in this case, we have that $\phi(A,B)$ is not the Dedekind cut for $A - B$.

In the case that $0 \not \in C$, we do the same thing, but now we choose the irrational to be in the interval $(b_N, \pi)$. Then $A – B > 0$, so we should have $0$ in the cut of $A – B$, but again $\phi(A,B)$ will be the same as $\phi(A,A)$ and will not contain $0$. This ends the proof. $\Box$

There are sometimes concerns, with Dedekind cuts for rationals, whether the cut is prohibited from including the rational to which it is equal (these are called “open cuts”) or whether the cut may include the rational or not at its discretion. That distinction is not relevant to the proof above, because both $A$ and $B$ are irrational. If we add a condition on $\phi$ that $0$ is not allowed to be in $\phi(A,A)$, the simply means that we know that the second case will be followed in the proof, in which case $B$ will be less than $\pi$, so that $0$ should be included in $\phi(A,B)$, but then $0$ would have to be included in $\phi(A,A)$, which would be forbidden.

This entry was posted in Musings, Results worth knowing. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *