- #1

- 118

- 12

It does this by, essentially, proof by contradiction: We start with the assumption that the set of all real numbers is countable, we list all these numbers (which should be possible if they are countable), and we proceed to construct a number that's not in the set. Thus our original assumption that we listed all the numbers was proven incorrect, and thus the premise that the set of real numbers is countable is incorrect.

But thinking about the argument, I can't help but get the feeling that it's circular: It assumes what it's trying to prove.

What do I mean by this?

If we start with the assumption that the set of all real numbers is countable, that means that we can assume that we can create a bijection between this set and the set of natural numbers. In other words, that we can "remap" all the numbers to the natural numbers (which would essentially be their position in the list), and this shouldn't make a difference. If the set is countable, then it shouldn't really matter how we represent the values, as long as they are unique (ie. it's a true bijection.)

Thus we can represent every number in the set with consecutive natural numbers. We can do it eg. in base-2, starting with the least-significant digit first, like:

0: 000000...

1: 100000...

2: 010000...

3: 110000...

4: 001000...

5: 101000...

and so on and so forth. But now if we construct a new number by taking the first digit of the first number and inverting it, the second digit of the second number and inverting it and so on, we get a new number like:

X: 111111...

which indeed is not in our set... because it's not a number at all. A base-2 number with an infinite amount of 1-digits is just infinity, which isn't a number (natural or real) by definition. Thus the diagonal argument didn't actually create a new number that's not in the set, because it merely created infinity, an invalid "number".

"But", you might argue, "the argument is about proving that the real numbers between 0 and 1 are uncountable!" That doesn't really make a difference because we can simply make those be binary values between 0.0 and 1.0:

0: 1.000000...

1: 0.000000...

2: 0.100000...

3: 0.010000...

4: 0.110000...

5: 0.001000...

and now the diagonal argument constructs the number:

X: 0.111111...

which is just 1.0, which already exists in our original set! The diagonal argument failed to create a new number that's not in the set.

"But", you may once again argue, "you can't represent irrational numbers like pi or square root of 2 like that because they have an infinite representation and they can't be mapped to a natural number because... oh..."

Which is precisely where the circularity of the argument arises: It already assumes that there are numbers that cannot be enumerated like this... and proceeds to prove that there are numbers that cannot be enumerated like this.