7
$\begingroup$

If, for every real number I can think of, I can always find a new natural number to pair with it, then why are the reals non-enumerable ? If the definition of enumerable is that I can pair a natural number with it, and there are infinite natural numbers, then I can always find a bigger natural number to pair with whatever real number I can think of, regardless of the number of digits, and regardless of whether or not I found them through diagonalization.

$\endgroup$
6
  • 8
    $\begingroup$ This question may seem elementary to some of us, but it is a perfectly sensible question for a thoughtful beginner to ask. It does not deserve the downvote. $\endgroup$
    – David
    Jun 23 at 3:29
  • 21
    $\begingroup$ "If, for every real number I can think of..." There's your problem: What about all of the real numbers you didn't think of? $\endgroup$
    – mweiss
    Jun 23 at 3:37
  • 2
    $\begingroup$ "If, for every real number I can think of..." I think the flaw in your informal way of phrasing is that it is not about doing this for any one number (as if asked by someone one number at a time "Here's 3.9856474, gimme a natural number! - "5."), but to simultaneously do it for ALL real numbers without repeating a natural number. That, indeed, is not possible. $\endgroup$ Jun 23 at 12:05
  • 2
    $\begingroup$ @David It may be a perfectly sensible question to wonder about, but I can't imagine that it would be difficult to find the answer with a simple Google search. $\endgroup$
    – NotThatGuy
    Jun 23 at 13:12
  • 2
    $\begingroup$ "Regardless of whether or not I found them through diagonalization": Cantor's argument starts by assuming that the natural numbers have already been mapped one-to-one to the real numbers. You can't just "find a bigger natural number" because they've all been used up. Diagonalization proves that even that isn't enough. $\endgroup$
    – Purple P
    Jun 23 at 13:24

7 Answers 7

5
$\begingroup$

Maybe you would prefer Cantors original proof: suppose that the reals are countable and denote such a countable sequence by $x_n$. Now, let $m$ be the smallest natural number such that $x_m>x_1$. With this, we can produce two subsequences in tandem.

Define $a_1=x_1$ and $b_1=x_m$. Define $a_n$ as the first member of the sequence $x_i$ such that $a_{n-1}<x_i<b_{n-1}$ and define $b_n$ as the first member of the sequence $x_i$ such that $a_n<x_i<b_{n-1}$. For example, if our sequence $x_n$ is

$$\{x_n\}_{n=1}^\infty =\{1,10,3,13,7,4,9,12,5,...\}$$

Then

$$\{a_n\}_{n=1}^\infty=\{1,3,4,...\}$$

$$\{b_n\}_{n=1}^\infty=\{10,7,5,...\}$$

Now, obviously $a_n$ is an increasing sequence and $b_n$ is a decreasing sequence. Further, $a_n$ is clearly bounded above by $b_1$ and $b_n$ is clearly bounded below by $a_1$. Thus, both sequences converge to some limits, call them $A$ and $B$ respectively. Now, is it possible that $A<B$? This is impossible since for some $s\in\mathbb{N}$ we have $x_s=\frac{A+B}{2}$ which implies that eventually $x_s$ will be the first member of the sequence such that $a_n<x_s<b_n$ or $a_n<x_s<b_{n-1}$. Thus, it must be the case that $A=B$. But again, this is impossible since there exists $t$ such that $x_t=A$. The logic is the same: there must be a point where $x_t$ is the first member of the sequence such that either $a_n<x_t<b_n$ or $a_n<x_t<b_{n-1}$. This is a contradiction as it implies either $a_{n+1}>A$ or $b_{n+1}<A$ respectively. We conclude the real numbers are not countable.

$\endgroup$
5
$\begingroup$

"If, for every real number I can think of, I can always find a new natural number to pair with it, then why are the reals non-enumerable?"

It is not true that for every real number one can think of, there is always a new natural number that we can pair with it. If it was, there would be a surjection from $\mathbb{N}$ to $\mathbb{R}$ and $\mathbb{R}$ would be countable, which is not the case.

Think about it like this: can you pair natural numbers and real numbers in a way such that no real number is left after you're done? No, you cannot: Cantor's diagonal argument proves that any function $f: \mathbb{N} \to \mathbb{R}$ is not surjective: there are always real numbers left over, no matter what list of natural numbers you start with.

$\endgroup$
3
$\begingroup$

Cantor cleverly figured out a way to produce a real not in any list of reals. He does this by changing the value on the diagonal of the decimal representations of the numbers.

There are just a few details to clear up after this.

$\endgroup$
3
$\begingroup$

If, for every real number I can think of, I can always find a new natural number to pair with it, then why are the reals non-enumerable ?

The problem is that you can't think of all of the real numbers. Even if you sat there and named real numbers for all of eternity, there would still be infinitely many real numbers that you never end up naming or thinking of.

Cantor gave two proofs of this which the other answers describe well.

$\endgroup$
1
$\begingroup$

Suppose you did complete the assignment, what would that look like? We could list out the natural numbers on the left, and then on the right we put the associated real number

$$\begin{align*} 1 \ &| \ 0.1857356... \\ 2 \ &| \ 0.3623575... \\ 3 \ &| \ 0.2503946... \\ \vdots \end{align*}$$

Cantor's argument says that you actually didn't complete the assignment, because he can tell you a real number that definitely isn't in your list. Indeed, we make a number whose first digit (after the decimal) is different from the first digit of the number associated to $1$, and whose second digit is different from the second digit of the number associated to $2$, and so on.

When presented with this number, there is nowhere in your list you could point to and say you have it. After all, if you pointed to the number next to $n$, the $n$-th digit would certainly differ from this number by construction. Thus, your list is missing a number and must not have been complete in the first place.

$\endgroup$
1
  • $\begingroup$ A constructive objection would be "How could you suppose you completed the assignment if there are no algorithms for the reals, and for the naturals it would take eternity ?" The acceptance of the proof requires a classical way of thinking where you assume the existence of objects you can't build, and this is the key. $\endgroup$
    – Rafael
    Jun 27 at 16:10
0
$\begingroup$

The error in your argument lies in the assumption that you can think of all real numbers. Thinking of real numbers is in of itself an enumeration. Unsurprisingly, when you assume real numbers are enumerable you arrive at the conclusion that they are.

$\endgroup$
0
$\begingroup$

Enumerability is not about whether you can find a natural number for every element of the set you can come up with, it's about whether you can put the elements of the set in a specific order such that the resulting list will contain all elements of the set.

For any real number, you'd need to be able to say what's the next real number in a deterministic way. And if you start from some real number and you get the next one, and the one after that, and so on, then any possible real number should eventually be reached.

With integers you can do something like this: $[0, 1, -1, 2, -2, 3, -3, ...]$. This would include all integers, and integers are therefore enumerable.

With real numbers you can't do the same.

There are formal proofs of why you're unable to come up with such an ordering, but that's the basic idea.

$\endgroup$
1
  • $\begingroup$ That makes sense. I realized even if you try all combinations of digits in an effort to build the set of reals you would never leave 0.xxx because you could always add a digit and make it 0.xxxx and so forth Hence the non-existence of an algorithm to build all the reals. I was thinking constructively(my tendency as a programmer) but realized the proof has to do with the classical approach where objects exist without requiring a demonstration of their construction. There are objections to Cantor's ideas(from constructionists and intuitionists) but it is fine if you think in a classical way. $\endgroup$
    – Rafael
    Jun 27 at 16:04

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.