3
$\begingroup$

I just watched a video that shows how real numbers are constructed using Dedekind cuts, and what I understood was that a real number is a subset of Q which, among a few other conditions, contains no greatest element. The video also shows an example of how this property can be proven for $\sqrt 2$. I also found these proofs for $pi$ and $e$.

I was wondering if there was another way to construct the reals using Turing machines, since the Dedekind cut feels a bit like a "by negation" kind of definition, and a Turing machine would be more of a procedural, actual way to construct them. But it turns out Turing machines are countable and reals are not, so there must be real numbers that can't be computed by Turing machines.

Which then led me to this other question, in which they give a few samples of non-computable real numbers. But now I wonder, given any of these numbers (say Chaitin's constant), can we prove that the Dedekind cut that corresponds to this number (and to every other number that we intuitively think of as a real number) has no greatest element? Or could it be the case that Chaitin's constant turns out to be a non-real number (which I have no idea what it'd even mean, since it definitely seems to be a point on the real line)?

I know there are other ways to construct real numbers that I haven't learned about yet, so perhaps one of them can be used to prove it?

$\endgroup$
  • $\begingroup$ Dedekind cuts are used to prove that $\mathbb{R}$ is complete. You probably confused the definitions of "rational cuts" with $\mathbb{Q}$? So, since $\mathbb{R}$ is complete, the numbers you refer must be in $\mathbb{R}$ (don't confuse this with algebraic completeness, which leads to $\mathbb{C}$). For example Chaitin's constant is a probability and $\in [0,1]$. $\endgroup$ – rtybase Jun 9 '18 at 8:28
  • 3
    $\begingroup$ @rtybase Dedekind cuts aren't used to prove anything. They are used to construct $\mathbb{R}$ so that it is complete. $\endgroup$ – Adayah Jun 9 '18 at 8:30
  • $\begingroup$ @rtybase I may be missing something, but then what's the point of proving that $\sqrt 2$ has no greatest element? Isn't it to show that it is a real number? $\endgroup$ – Juan Jun 9 '18 at 8:30
  • $\begingroup$ @Adayah have a look at this proofwiki.org/wiki/Dedekind%27s_Theorem ... it basically says that in $\mathbb{R}$ all cuts are rational. $\endgroup$ – rtybase Jun 9 '18 at 8:32
  • $\begingroup$ @Juan You misunderstood that part of the video. The point was to prove that the set $A = \{ x \in \mathbb{Q} : x^2 < 2 \}$ has no greatest element, hence, by definition of $\mathbb{R}$, it is a real number. Then we can proceed to prove that $A \cdot A$ (with multiplication as it's defined for cuts) equals $2$, hence $A = \sqrt{2}$. In the video he wasn't proving that $\sqrt{2}$ has no greatest element, since it is true by the very definition of a real number. $\endgroup$ – Adayah Jun 9 '18 at 8:33
3
$\begingroup$

The Dedekind cut $A$ representing a certain real number $\alpha$ consists of all rational numbers that are $<\alpha$. Among the numbers in $A$ there are arbitrarily precise rational approximations to $\alpha$, but also totally uninteresting numbers in reference to the value of $\alpha$. But the latter play no rôle in the subsequent construction. The reason why we are carrying them along is that we want a single and simple mathematical object $A$ representing the number $\alpha$, without having to bother about extra data like error bounds.

The condition that such a cut should have no maximal element is not a "definition by negation", but of a purely technical nature. A cut defining an irrational number, like $\pi$, automatically has no maximal element. But we want to have the rational numbers as ordinary real numbers as well. Without taking care a rational number $\rho$ could be represented by all rational numbers $<\rho$ as well as by all rational numbers $\leq\rho$. In order to avoid ambiguities one requires once and for all that the second kind of "cuts" is excluded.

$\endgroup$
0
$\begingroup$

Your reasoning about counting Turing machines versus counting real numbers has a certain weakness. You might imagine to make a list of all Turing machines; this can be done automatically, since the description of a TM is syntactically clear, and they would be numbered from 1,2,3,... and onwards. Having done that, you might imagine to examine each Turing machine, starting from number 1, then number 2, and so on, to isolate those that happen to compute real numbers, which obviously only some of them would do. If you determine that TM numbered n computes a real number, you would give that real number a label i(n) to show that it is the i(n)'th real number computable by a TM.

It leaves the small obstacle to have to determine whether a given TM computes a real number or not. You probably see where this is going. The solution to the halting problem says that you cannot even determine whether the given TM ever halts, much less whether it halts and outputs a real number description that you desire.

It follows that you cannot argue in this way that there is any "set of computable real numbers", nor that such a set would be countable.

Something like Chaitin's constant is obviously a well-defined real number, since it is given by a description of the individual decimals in its decimal expansion. It is easy in principle to construct a corresponding Dedekind cut or a Cauchy sequence. Not so much in practice.

$\endgroup$
  • 2
    $\begingroup$ This isn't my area, but I don't think you're correct. The computable reals are both well-defined and countable. en.wikipedia.org/wiki/Computable_number $\endgroup$ – Joe Jul 30 '18 at 13:51
  • $\begingroup$ Further, the argument you make falls apart with the observation that all we need to do is provide the upper bound "there are no more reals that can be produced by TMs than there are TMs". Just because I can't tell you which TM produces which number, that doesn't mean we can't reason about the class. $\endgroup$ – Joe Jul 30 '18 at 13:52
  • $\begingroup$ Those are good points. I deliberately wrote that you cannot "do it this way", because it is a little more tricky than one might first think. Examining each of a countable set of Turing machines for whether or not it happens to compute some real number certainly is out of the question, and you have to be more clever. $\endgroup$ – Tommy R. Jensen Jul 30 '18 at 14:43
  • $\begingroup$ Actually it is undecidable whether a given TM halts. In particular it is also undecidable whether it computes a real number. If it does, then that real number x is computable, and if not, then x (probably) isn't. This is interesting for our perception of the reality and meaning of computable numbers. $\endgroup$ – Tommy R. Jensen Jul 30 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.