So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.

I understand the overall argument but have a problem regarding one caveat mentioned in my book.

My book says that some real numbers like 2.000... and 1.999... have different decimal representations but are actually the same real numbers. Suppose we have a bijection $ f: N \rightarrow R$ where $N$ and $R$ are the sets of natural and real numbers respectively. Now, suppose $f(1) = 1.999...$ and no $x \in N$ exists such that $f(x) = 2.000...$. In such a scenario it is possible that the diagonalization argument ends up constructing the real number $2.000...$ which is already in our list since $1.999...$ and $2.000...$ are the same real numbers. To get around this problem, we never select 0 or 9 when constructing our number.

I don't understand two things. First, why do $1.999...$ and $2.000...$ represent the same real number? Second, how never selecting 0 or 9 solves the problem this poses?

  • 5
    $\begingroup$ I'm voting to close this question as off-topic because it is purely mathematical and has no computational content. It should be on Mathematics. $\endgroup$ – David Richerby Oct 24 '19 at 6:56
  • $\begingroup$ @DavidRicherby the question comes from a CS book. It is true that the argument is mathematical, but at the same time all the arguments and proofs that have to do with set theory and logic are mathematical (and you know better than me that there are so many in the literature). For consistency we should close dozens of other questions. $\endgroup$ – Yamar69 Oct 24 '19 at 7:17
  • $\begingroup$ @Yamar69 It doesn't matter where the question came from, and voting to close this question doesn't oblige us to actively seek out other questions to close. $\endgroup$ – David Richerby Oct 24 '19 at 7:35
  • $\begingroup$ @DavidRicherby Mathematics is a large part of Computer Science. $\endgroup$ – Shashank Kumar Oct 24 '19 at 7:41
  • $\begingroup$ @ShashankKumar Mathematics that relates directly to computation is on-topic, here. This question has nothing to do with computation; it's about the cardinality of the set of real numbers. $\endgroup$ – David Richerby Oct 24 '19 at 7:51

There are several issues with your question but perhaps I can clarify some issues.

First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$.

Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more complicated answer that I find satisfactory. The easy answer is that $1 = \sum_{i=1}^{\infty}9*10^{-i}$ (the general form $(N - 1)*N^{-i}$ holds for all $N$) and $0.99...$ is definitionally $\sum_{i=1}^{\infty}9*10^{-i}$

A more satisfactory answer comes from understanding the representation of real numbers as you would in an analysis class and understanding when we define two real numbers to be equal. There are many different representations and I'll get details wrong here if I try and give you a precise example but the basic idea of most representations is to represent a real number as a sequence (sometimes its not a sequence but generally) of finite (generally rational) approximations. So $[1/1, 1/1, ...]$ is a real number representing 1.0 and $A = [9/10, 99/100, 999/1000, ...]$ is another that as we shale see is equivlent. Notice that the terms in that are the finite sums of $\sum_{i=1}^{\infty}9*10^{-i}$. We define the summation to be the sequence of its finite summations. If the sum converges then this defines a valid real number. Why does $[2/1, 2/1, ...] = [19/10, 199/100, ...]$? Because for any $\epsilon > 0$ I choose you can find an $N$ such that the difference of the $N$th elements of each sequences is within $[-\epsilon, \epsilon]$ or in a nutshell, the approximations become arbitrarily close. Take this paragraph with a grain of salt though, I'm being handy wavy and imprecise.

The traditional proof of cantor's argument that there are more reals than naturals uses the decimal expansions of the real numbers. As we've seen a real number can have more than one decimal expansion. So when converting a bijection from the naturals to the reals into a list of decimal expansions we need to choose a canonical choice. The axiom of choice just lets us do this for free but it sounds like your book tried to do something different. It isn't clear to me what your book did exactly from your description. Here's a potential way but it relies on further knowledge of reals and decimal expansions.

Take for granted that only the rationals with terminating decimal expansions (e.g. not 1/7 or 1/3 but 1/2 = 0.5 and 1/8 = 0.125 etc.. are valid) have two representations. Then its clear that every real number has exactly one non-terminating representation. So for our decimal expansions if we restrict ourselves to the non-terminating expansions we have no ambiguity.


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