1
$\begingroup$

Cantor's diagonal argument works because it is based on a certain way of representing numbers. Is it obvious that it is not possible to represent real numbers in a different way, that would make it possible to count them?

Edit 1: Let me try to be clearer. When we read Cantor's argument, we can see that he represents a real number as an infinite sequence of binary digits. Using this representation, he shows that real numbers are uncountable. An intuitive counter argument could be that maybe there is another type (perhaps incredibly strange) way of representation that would make it possible to count the real numbers. A kind of trick, like the typical one used to show the countability of rational numbers. One could thus be tempted to think that when representing real numbers as infinite sequences of binary digits, it is those representations that are uncountable, but that some other representation could be countable. It seems to me that this can be summed up like this: Is a proof of the countability of a set dependent on the representation its members in the proof?

$\endgroup$
  • 7
    $\begingroup$ Yes, it is obvious. $\endgroup$ – Gerry Myerson Apr 14 '15 at 9:27
  • 2
    $\begingroup$ It is obvious because once you prove that $\Bbb{R}$ is uncountable, then you cannot count $\Bbb{R}$. $\endgroup$ – Crostul Apr 14 '15 at 9:28
  • $\begingroup$ @GerryMyerson Why? $\endgroup$ – Jostein Trondal Apr 14 '15 at 9:34
  • 1
    $\begingroup$ The number of decimals with trailing 0s is countable. So double counting the trailing 0s and the trailing 9s will only increase the set countably. The rest of the decimals, indeed, even just the decimals with no 0s or 9s at all, will be uncountable. $\endgroup$ – fleablood Feb 28 '16 at 7:07
  • 1
    $\begingroup$ Does the uncountability of a set depend upon its representation? If it is indeed a true representation then .... of course not! What a silly question. $\endgroup$ – fleablood Feb 28 '16 at 7:33
0
$\begingroup$

Cantor himself did not give an argument with decimal or binary representations of the reals, but a topological style argument: assuming the reals can be enumerated as $(r_n), n \in \omega$ he picks smaller and smaller nested closed intervals, the $n$-th missing $r_n$ for each $n$. He previously showed his nested intervals theorem for complete metric spaces and so he knows there is a point in the intersection of the intervals which cannot be any of the $r_n$ and we have a contradiction. So a topological argument, not one based on decimal expansions but on completeness of the reals (which is by construction of the set of reals, Cantor did that construction in an earlier paper: Dedekind used order completeness, Cantor metric completeness and Cauchy sequences to construct an isomorphic copy of the "real numbers" $\Bbb R$).

$\endgroup$
5
$\begingroup$

You are making the common mistake to confuse between a number and its decimal representation.

An easy way to see that $\Bbb R$ is uncountable, regardless to how we can or cannot represent real numbers, is to see there is an injection from $\mathcal P(\Bbb N)$ into $\Bbb R$, defined by $\displaystyle A\mapsto\sum_{n\in A}\frac1{3^{n+1}}$.

This function depends only on the fact that this sum is a convergent sum (as it is bounded by a convergent geometric sequence), and the fact that $\mathcal P(\Bbb N)$ is uncountable depends only on its property of being the power set of $\Bbb N$.

$\endgroup$
  • $\begingroup$ Just a footnote (for the author of the question), proving that the power set of a set cannot be equipotent to the set itself is also done using Cantor's argument. $\endgroup$ – 5xum Apr 14 '15 at 12:17
  • 1
    $\begingroup$ Yes, but it is a different way and a more generalized argument. It does not depend on the real numbers having such and such property. It only depends on sets being definable by a formula with parameters. $\endgroup$ – Asaf Karagila Apr 14 '15 at 13:34
4
$\begingroup$

You obviously do not yet fully understand Cantor's argument and its implications.

Where you are correct: Cantor's argument indeed relies on the fact that there exists a decimal representation of numbers.

Where you are wrong: It is not true, as you are implying, that Cantor's argument only works if we represent numbers in a particular way.

Cantor's argument proves that there does not exist any bijective function from $(0,1)$ to $\mathbb N$.

This statement, in itself, does not "see" the representation of numbers, so changing the representation cannot effect the truth value of the statement.

For example, say I give you the statement "there are $10$ cows in the world", and you show me a herd of $11$ cows. Then, you say "let $S_H$ be the set of all cows in this herd, and let $S_A$ be the set of all cows in the world. Then $|S_H| = 11$, and because $S_H\subseteq S_A$, we know that $|S_H|\leq |S_A|$, therefore, the set of all cows contains at least $11$ cows, and your statement is wrong."

Thus, you prove to me that my statement is incorrect. Can I now say

Well, yes, but that's just because you represented your herds of cows with sets. Maybe, there is another representation of cows in which there actually are only $10$ cows in the world.

No, of course I cannot say that. Your sets were only a tool to prove a point, and they prove the fact that there are more than $10$ cows in the world, but the fact remains true even if you use some other tool.

$\endgroup$
  • 1
    $\begingroup$ You obviously do not yet fully understand the OPs concern ... :-) $\endgroup$ – coproc Apr 14 '15 at 9:43
  • $\begingroup$ @coproc I have extended my answer, now I am waiting for the OP to explain if I have adressed his concerns... $\endgroup$ – 5xum Apr 14 '15 at 9:46
  • 1
    $\begingroup$ Well, I was a little disturbed by your "strong" intro ... and at the same time I am also uncomfortable with the number representation as digits, since such a represenation is not unique. $\endgroup$ – coproc Apr 14 '15 at 10:00
  • 1
    $\begingroup$ @coproc Well, the representation is unique if you add a simple constraint that there is no endless tails of nines (i.e. that $0.2399999... = 0.24$). And anyway, the fact that there may be other representations of numbers does not change the validity of Cantor's argument, and thus, cannot change the fact that $\mathbb R$ is uncountable. $\endgroup$ – 5xum Apr 14 '15 at 12:16
  • 1
    $\begingroup$ Cantor's original argument did not rely on decimal representations at all. See my answer for what he did do. I read the original papers and his biography... $\endgroup$ – Henno Brandsma Jun 12 at 22:17
1
$\begingroup$

Independent of Cantor's diagonal we know all cauchy sequences (and every decimal expansion is a limit of a cauchy sequence) converge to a real number. And we know that for every real number we can find a decimal expansion converging to it. And, other than trailing nines and trailing zeros, each decimal expansions are unique.

So we know that the real numbers and the set of decimal expansions are the same.

NOW we can talk about Cantor's doagonal. Any finite set $F $ (such as the set of 10 digits), then $F^\mathbb N $ is uncountable by Cantor's diagonal. (Equivalency of trailing 9 and trailing 0 is a minor detail easily resolved.) A 1-1 corespondence between decimal expansions and the set $A =\{0...9\}^\mathbb N $/trailing 0 equiv trailing 9 is obvious.

$A \iff $ {decimal expansions} = $\mathbb R $.

So Cantor's argument is good no matter what format we do or do not represent the reals with.

$\endgroup$
1
$\begingroup$

It would not matter if we used a different representation. The reason for this is that the existence of a decimal expansion is a property of real numbers. A property of real numbers is that if I take a number $x \in [0, 1)$, then I can construct a sequence of integers that does such-and-such. The argument doesn't work because we choose to look at such-and-such representation of real numbers, but because the real numbers have a property that we can do the operations we propose. For example, the argument would have failed to establish the uncountability of $\mathbb{Q}$ because $\mathbb{Q}$ is not complete, and soo even if we constructed a "number" whose first digit was not $0, 9,$ or the first digit of the first number in the list, whose second digit was not $0, 9,$ or the second digit of the second number on the list, and so on, we would be incorrect because we cannot promise that we have constructed a rational number (in fact, there would be cases where you hadn't, as you could in fact list every rational number). But $\mathbb{R}$ is complete, so we know the Cauchy sequence that is $\left( \sum_{k = 1}^{N} a_{k} 10^{-k} \right)_{N \in \mathbb{N}}$ converges, where $a_{k} \in \{1, \ldots, 8 \}$, and moreover we know it converges to a number different from any on the list.

Now imagine a similar question: "Sure, the fundamental theorem of arithmetic says that every positive integer can be written uniquely as a product of positive primes, but what if we didn't factor them? Would such-and-such argument still hold?" The answer here is yes, because no matter how you express a natural number, you can still go back and factor it. This is because we never said that "a natural number is one that can be written uniquely as a product of prime numbers", but because rather it is a property of natural numbers that they can be written as a product of primes. Likewise, given any sequence of real numbers, no matter how you write them, we can still say, "Okay, so these are all real numbers, and so we can do this deal here and find a sequence of digits for each real number, perform the right operations on the right digits, and get a sequence that we can relate to a convergent series that converges to a real number not on our list." It's well and good to find a new way to write a real number, but it is still a real number, and you cannot re-write it so it lacks the properties of real numbers.

$\endgroup$
-3
$\begingroup$

To prove $\mathbb{R}$ is uncountable, we assume that it isn't (i.e. that it is countable). We then make a list of all the real numbers, and state that this list is complete. However we can construct a new real from not the $1^{st}$ digit of list item $1$ (e.g. if the $1^{st}$ digit of item $1$ is $4$, pick any digit other than $4$ (and arguably not $0$ either)), and keep the rest the same ($2^{nd}$ digit from $2$, $3^{rd}$ digit from $3$, etc..), not the $2^{nd}$ from list item $2$ and the rest the same, and so on. This number is not in the list, and so $\mathbb{R}$ is uncountable.

This is Cantor's Diagonal argument.

As it is impossible to count $\mathbb{R}$, there is no way we can re-invent numbers in such a way as to make this possible.

$\endgroup$
  • $\begingroup$ Yes, this is Cantors argument. Which is based on a certain representation (with digits and so on). $\endgroup$ – Jostein Trondal Apr 14 '15 at 9:37
  • 1
    $\begingroup$ Let's say the list of numbers is 0, 0. 99.. (9 periodic), 0.09, 0.009, 0.0009, etc. with the bold digits chosen to be different. Now lets take 1 instead of 0 and 0 instead of all 9s, then we get the new number 1.00... which is equal to the second number (0.99..). So the argument is not that simple. $\endgroup$ – coproc Apr 14 '15 at 9:40
  • $\begingroup$ Hm, your argument does still not address the fact that a number's representation may not be unique. $\endgroup$ – coproc Apr 14 '15 at 10:01
  • 1
    $\begingroup$ Um, did you read the OP? $\endgroup$ – fleablood Feb 28 '16 at 6:07

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.