Cantor's diagonal proof?
Discussion
Is this actually a proof, or more a paradox?
It states there are more decimals 0>1 than real numbers.
Cantor said
1 Write all the real numbers one below the other.
2 Next to them write all the decimals,one below the other,in any order. Each decimal can be represented by an infinite string of digits, and there are infinitely many of them.
So far so good, the two columns have a 1:1 correlation which shows that although they are infinite, they are equal.
Now for the fun bit.
3 Go down the list of decimals, and for the first one, write down the first digit +1. For the second one, write down the second digit +1 next to the digit you just wrote, and so on all the way down the list.
Cantor claims:
The number you end up with Cannot Be On The List, because it differs from every number on the list by at least one digit, so there are more decimals 0>1 than reals. qed
But I think this can't be correct, because if it were so, then you haven't written all the decimals!
Obviously it is not possible to write down All the numbers or decimals in practice, it's all about 1:1 correlation, but people far cleverer than me consider Cantor's diagonal proof valid.
It states there are more decimals 0>1 than real numbers.
Cantor said
1 Write all the real numbers one below the other.
2 Next to them write all the decimals,one below the other,in any order. Each decimal can be represented by an infinite string of digits, and there are infinitely many of them.
So far so good, the two columns have a 1:1 correlation which shows that although they are infinite, they are equal.
Now for the fun bit.
3 Go down the list of decimals, and for the first one, write down the first digit +1. For the second one, write down the second digit +1 next to the digit you just wrote, and so on all the way down the list.
Cantor claims:
The number you end up with Cannot Be On The List, because it differs from every number on the list by at least one digit, so there are more decimals 0>1 than reals. qed
But I think this can't be correct, because if it were so, then you haven't written all the decimals!
Obviously it is not possible to write down All the numbers or decimals in practice, it's all about 1:1 correlation, but people far cleverer than me consider Cantor's diagonal proof valid.
Edited by Super Sonic on Friday 19th January 19:36
Super Sonic said:
Is this actually a proof, or more a paradox?
It states there are more decimals 0>1 than real numbers.
Cantor said
1 Write all the real numbers one below the other.
2 Next to them write all the decimals,one below the other,in any order. Each decimal can be represented by an infinite string of digits, and there are infinitely many of them.
So far so good, the two columns have a 1:1 correlation which shows that although they are infinite, they are equal.
Now for the fun bit.
3 Go down the list of decimals, and for the first one, write down the first digit +1. For the second one, write down the second digit +1 next to the digit you just wrote, and so on all the way down the list.
Cantor claims:
The number you end up with Cannot Be On The List, because it differs from every number on the list by at least one digit, so there are more decimals 0>1 than reals. qed
But I think this can't be correct, because if it were so, then you haven't written all the decimals!
Obviously it is not possible to write down All the numbers or decimals in practice, it's all about 1:1 correlation, but people far cleverer than me consider Cantor's diagonal proof valid.
No, it's not a paradox. It assumes to begin with that the real numbers are countably infinite, and thus so are the decimals between zero and one.It states there are more decimals 0>1 than real numbers.
Cantor said
1 Write all the real numbers one below the other.
2 Next to them write all the decimals,one below the other,in any order. Each decimal can be represented by an infinite string of digits, and there are infinitely many of them.
So far so good, the two columns have a 1:1 correlation which shows that although they are infinite, they are equal.
Now for the fun bit.
3 Go down the list of decimals, and for the first one, write down the first digit +1. For the second one, write down the second digit +1 next to the digit you just wrote, and so on all the way down the list.
Cantor claims:
The number you end up with Cannot Be On The List, because it differs from every number on the list by at least one digit, so there are more decimals 0>1 than reals. qed
But I think this can't be correct, because if it were so, then you haven't written all the decimals!
Obviously it is not possible to write down All the numbers or decimals in practice, it's all about 1:1 correlation, but people far cleverer than me consider Cantor's diagonal proof valid.
Edited by Super Sonic on Friday 19th January 19:36
Because the assumption leads to a paradoxical contradiction, then the assumption must be wrong. The assumption being that you could write an infinite list of the reals (this is the "countable" bit).
Once you have the reals between (0, 1), then there's a straightforward way to generate every real number, tan(πx - π/2). Because of the nature of the reals, every single real number has a unique input that generates it, so that's a bijection. Despite being stretched infinitely thin, it's still a continuum.
Formally:
∀ x ∈ ℝ ∃ y ∈ (0,1) : tan(πy - π/2) = x
Edited by Solocle on Monday 22 January 10:30
If I understand your description correctly, a much simpler case would be to start with the 3-digit decimals:
0.000
0.001
0.002
0.003
0.004
Etc
0.999
If we take the first digit of the first number, this is 0, so adding 1 gives us 1. The second digit of the second number is also 0, so we get 1 again. The third digit of the third number is 2, so adding 1 gives us 3.
This gives 0.113 which differs from the first three numbers by at least one, but it doesn't differ from every number in the list, so the logic of that statement is incorrect.
My head hurts when considering "countable infinites" so I might have missed a subtlety in my simplified version.
It sound like it's akin to "I have 2 coins totalling 70p and one of them isn't a 20p, what have I got?" - a 50p (which isn't a 20) and a 20p
0.000
0.001
0.002
0.003
0.004
Etc
0.999
If we take the first digit of the first number, this is 0, so adding 1 gives us 1. The second digit of the second number is also 0, so we get 1 again. The third digit of the third number is 2, so adding 1 gives us 3.
This gives 0.113 which differs from the first three numbers by at least one, but it doesn't differ from every number in the list, so the logic of that statement is incorrect.
My head hurts when considering "countable infinites" so I might have missed a subtlety in my simplified version.
It sound like it's akin to "I have 2 coins totalling 70p and one of them isn't a 20p, what have I got?" - a 50p (which isn't a 20) and a 20p
weeredmetro said:
If I understand your description correctly, a much simpler case would be to start with the 3-digit decimals:
0.000
0.001
0.002
0.003
0.004
Etc
0.999
If we take the first digit of the first number, this is 0, so adding 1 gives us 1. The second digit of the second number is also 0, so we get 1 again. The third digit of the third number is 2, so adding 1 gives us 3.
This gives 0.113 which differs from the first three numbers by at least one, but it doesn't differ from every number in the list, so the logic of that statement is incorrect.
My head hurts when considering "countable infinites" so I might have missed a subtlety in my simplified version.
It sound like it's akin to "I have 2 coins totalling 70p and one of them isn't a 20p, what have I got?" - a 50p (which isn't a 20) and a 20p
It doesn't differ from every number on the list because you've not taken a digit from every number on the list and made it different.0.000
0.001
0.002
0.003
0.004
Etc
0.999
If we take the first digit of the first number, this is 0, so adding 1 gives us 1. The second digit of the second number is also 0, so we get 1 again. The third digit of the third number is 2, so adding 1 gives us 3.
This gives 0.113 which differs from the first three numbers by at least one, but it doesn't differ from every number in the list, so the logic of that statement is incorrect.
My head hurts when considering "countable infinites" so I might have missed a subtlety in my simplified version.
It sound like it's akin to "I have 2 coins totalling 70p and one of them isn't a 20p, what have I got?" - a 50p (which isn't a 20) and a 20p
If you'd done the procedure correctly you'd end up with 0.1131111....1, which obviously is not on the list. But it's also not a three digit decimal.
However, the thing about the reals is the result is guaranteed to be a real number too, and because you have a countably infinite number of decimal places... The real numbers are closed under the operation of changing its digits in this manner. Whereas this doesn't apply to the rational numbers - the decimal could quite easily be an irrational number (and in fact, would be by necessity if you had a list of all rationals).
The point about countability is you can write out a list. But equally with the decimal you can write out the Nth digit. Thus there's a 1:1 mapping through the natural numbers. A 1st element, a 2nd element, and so on.
You could assume that's the only sort of infinity. But the diagonal argument kills that assumption. You cannot have a list of all the real numbers.
Gassing Station | Science! | Top of Page | What's New | My Stuff