# Dedekind Cuts and Computable Numbers

Can someone please tell me where I'm wrong? I'm not able to figure out where is the error:

First let's define what a computable number is: a number is computable if there is a Turing Machine that can return the decimal expansion of that number with arbitrary precision.

1) Rational are computable by a Turing Machine. Since all rational can be written by definition like a quotient of two integers: n/m, for any rational there must exist an algorithm that compute that number. We call this type of Turing Machine: "ArbitraryPrecisionQNumber". It is important to note that even if I'm not able to see how to construct the Turing Machine for example the rational: "a² < 2". This Turing Machine must exist by definition.

2) Dedekind cuts are defined with 2 rationals.

3) The pair of rationals that defines the Dedekind cut can be computed with 2 Turing Machines. From my point of view this 2 Turing Machines describes completely the Dedekind cut since the are able to compute the 2 rational numbers with arbitrary precision.

4) The number of Turing Machines is countable and the number of two Turing Machines is also countable since it is equivalent of the claim that ordered pairs of natural numbers are countable.

Lets "choice" a pair of "ArbitraryPrecisionQNumber" Turing Machines that validates the property of expressing a Dedekind cut: for example the TM that computes the rational a² < 2 and the TM that computes the rational b² > 2 for the square root of 2.

It is important to note that even if this property between the two Turing Machines can not be verified this pair must exist since The two Turing Machine exist. (this is a non constructive argument and I think that we must invoke the axiom of choice to be able to talk about this pair).

We can construct a Turing Machine called "ArbitraryPrecisionRealNumber made of this pair of "ArbitraryPrecisionQNumber" that compute any real number defined with a Dedekind cut.

In essence we can say: "this construction of a Turing Machine is a description of the real number defined by the Dedekind Cut". The problem with this sentence is evident since we have:

1) the set of Dedekind cuts forms a bijection with the set of reals.

2) there are as many Dedekind cuts as reals. So the set of Dedekind cuts are uncountable.

So we have a set of countable Turing Machine of every Dedekind cut but the set of Dedekind cut is uncountable. I think that this also can be restated in the following manner: There are uncomputable reals but all Dedekind cut can be computed.

UPDATE:

I think all the problem comes from this point: "Dedekind cuts are defined with 2 rationals"

I will elaborate a little bit more my thoughts. It is true that from an "absolute perspective" Dedekind Cut can not be defined by 2 rationals. One good argument for this is that a rational set does not have a supremum for example so you are not able to define a Turing Machine that compute this (non-existent) number.

I was more concerned with an "infinite approximation" perspective of a real. In my opinion if we define a process that can define in the limit a real number (at infinity) then it is a definition of a real number

So in fact we could restate all this question like this: "Could we define 2 Turing Machines that approximates from above and from bellow to the infinity a real number?" If we can, then I think the conclusion that I gave is correct and this two TM would be equivalent to Dedekind Cuts.

I had doubts if this could be possible but if the real number is no definable in a finite way then this two Turing Machines does not exist by definition.

The main issue with my argument is the next one: there is infinite undefinable real numbers.

• To 2) : "Dedekind cuts are defined with 2 rationals." This means that, due to the fact that the set $\mathbb Q^2$ of couples of rationals is countable, also the set $\mathbb D$ of Dedekind cuts is countable. Thus, it does not define all the real, that are uncountable. Conclusion : 2) is not true. – Mauro ALLEGRANZA Mar 8 '15 at 13:17
• @MauroALLEGRANZA Dedekind cut are defined by two sets that are defined using two rationals. What is the difference? Given both rational a² > 2 and b² < 2 I can generate the Dedekind cut. – J.F. Mar 8 '15 at 13:43
• I think that you have to review the definition ... See Ethan Bloch, The real numbers and real analysis (2011), page 35 : "Definition : Let $A \subseteq \mathbb Q$ be a set. The set $A$ is a Dedekind cut if the following three properties hold. a) $A \ne \emptyset, A \ne \mathbb Q$. b) Let $x \in A$. If $y \in \mathbb Q$ and $y \ge x$, then $y \in A$. c) Let $x \in A$. Then there is some $y \in A$ such that $y < x$. – Mauro ALLEGRANZA Mar 8 '15 at 13:53
• A D.cut is not a couple of rationals but a couple of sets of rationals and the "number" of sets of rationals is uncountable. – Mauro ALLEGRANZA Mar 8 '15 at 14:18

Every $A\subseteq \Bbb N$ is the union of $A_n=A\cap\{0,\ldots,n-1\}$. Since $\Bbb N$ is arithmetical (definable in the language of arithmetics), and every finite set is arithmetical, it follows that $A=\bigcup_{n\in\Bbb N}A_n$ is also arithmetical.
And of course that not every subset of $\Bbb N$ is definable in the language of arithmetic. This will contradict many many theorems that have solid proofs (Cantor's theorem, Tarski's theorem)
So what happened in your argument? The fact that every $q\in\Bbb Q$ is computable doesn't mean that every subset of $\Bbb Q$ is computable.