An algorithmic approach to constructing the real numbers

Question

To specify a real number, we can describe a rule which, given any rational number, tells you whether it's Too Big or Too Small. The rule should be self-consistent, in the sense that if $a$ is Too Big and $b > a$, then $b$ must be Too Big, and if $a$ is Too Small and $b<a$, then $b$ must be Too Small. For example, the rule for $\sqrt 2$ is to square the rational number and test if the result is greater than or less than $2$.

So far this is just Dedekind cuts. But a Dedekind cut just says that all numbers are either Too Big or Too Small, it doesn't worry about whether or not it's feasible to work out in practice which of the two a number is.

Let's suppose that we have a rules like this for two real numbers $x$ and $y$. To define the sum of $x$ and $y$, we want a rule which says that a rational $a$ is Too Big if it can be expressed as the sum of a rational Bigger Than $x$ and a rational Bigger Than $y$, and that $a$ is Too Small if it can be expressed as the sum of a rational Smaller Than $x$ and a rational Smaller Than $y$.

Can we define such a rule (algorithm) in terms of the rules for $x$ and $y$? Can we do the same for multiplication?

Of course the obvious answer is to systematically test every different representation of $a$ as a sum of two rationals, but there isn't any upper bound on how long this might take.

Answer 1

The following sets of real numbers are all the same:

• The computable real numbers (by definition)

• The set of real numbers for which there is an algorithm that, given $n$, produces the $n$th digit of a decimal expansion (where negative values of $n$ give the integer part and positive values give the fractional part of the expansion). This is, essentially, the definition that Turing originally proposed.

• The set of real numbers for which there is a computable Dedekind cut, that is, a pair of computable subsets $A,B$ of $\mathbb{Q}$ with $A \cup B = \mathbb{Q}$; $A,B \not = \emptyset$; and $a < b$ for all $a\in A$, $b \in B.$

• The set of all real numbers for which there is a sequence of rationals $(a_n)$ that converges to the real number and such that $|a_n - a_m| < 2^{-n}$ for all $m > n$. These are called quickly converging Cauchy sequences.

So the computable real numbers are robust under various computable representations.

The arithmetic operation on real numbers, though, are not as robust. In every one of the three representations I mentioned, the sum, difference, and product of two computable real numbers is computable, and the quotient of a computable real by a nonzero computable real is computable. But only in the representation by Cauchy sequences is there a single algorithm that, given the representation of two computable reals and the operation to be performed, produces a representation of the result of applying that operation.

For the Dedekind cut and decimal expansion representations, in order to perform the operation, it is often necessary to first know whether the output real is actually equal to a rational. If it is, then one algorithm is used, and if not then another algorithm is used. This is one advantage of the representation by quickly converging Cauchy sequences. However, if we only care about whether the numbers are computable, not whether the operations are (uniformly) computable, then all three representations work perfectly well.

Answer 2

Yes, if two real numbers $x$ and $y$ are defined in terms of algorithms as above, then we have algorithms for $x+y$ and $xy$ as well.

To see this, note that there is an algorithm to obtain arbitrarily close bounds on $x$ and on $y$. That is, given a rational $\epsilon$ and an algorithmic description of a real number $a$, this algorithm outputs rationals $a^-<a^+$ with $a^+ - a^- < \epsilon$, $a^+$ is Greater Than $a$ and $a^-$ is Less Than $a$.

To simplify, let's say we're only trying to construct the positive reals from the positive rationals. It shouldn't be hard to use the same idea for all reals.

Try all integers starting from $0$, in order, until you get to one which is Greater Than $a$. Now you have bounds $n<a<n+1$. Now try all fractions of the form $k/10$ between $n$ and $n+1$, from $k=0$ to $10$, until you hit one which is Greater Than $a$. You know have better bounds for $a$. Keep going with fractions of the form $k/10^p$ for $p=2, 3, 4...$ until you get the desired precision.

Now suppose we want to know if a rational $q$ is Greater Than or Less Than $x+y$. Run the algorithm above to get bounds $x^- < x < x^+$ and $y^-<y<y^+$. Then $x^-+y^-$ is Less Than $x+y$ and $x^++y^+$ is Greater Than $x+y$ by definition. Thus we can determine the nature of $q$ by showing that either $q<x^-+y^-$, or $q>x^++y^+$. But if the distance between $x^-,x^+$ and $y^-,y^+$ is sufficiently small, one of these conditions must be true. Therefore simply run the preceding algorithm over and over with smaller and smaller values of $\epsilon$ and you will be able to determine the nature of $q$ after a finite number of steps.

Essentially the same method should work for the product $xy$.