I just learned this from a veritasium video, and I have no background in math btw. That being said, I didn’t find the proof very convincing (I think it may be simplified for the purpose of education). But from what I know, the counterexample I can give is to map the natural integers with themselves like this, add down the diagonal to produce a new number, and derive a contradiction:
1 —> 8298492…
2 —> 7592010…
3 —> 6823023…
etc…
New number 963… doesn’t fit in the left side set by definition.
Comments
The mistake in your argument is that no integer has an infinite number of (non-zero) digits to the left of the decimal point, whereas the reals do have an infinite number of digits to the right of the decimal point, allowing for the argument to work. For instance, the number you have just devised, 963…, isn’t an integer, making your argument fail.
You just need to prove there exists a one-to-one mapping for it to be a countable infinity. So I can counter your argument with a mapping: 1 -> 1, 2->2, etc.
Because every integer is finite. You can find an arbitrarily long integer, but there are no infinitely long ones. So you can’t use the same argument because decimal expansions are actually infinite.
It sounds like you get it. You create a mapping of natural numbers to real numbers and claim that you have included all the real numbers, but then you do the diagonal thing and change each digit so that you have a number that isn’t on the list, thus showing a contradiction.
I find it very convincing and it’s very close how it’s done in academia, but maybe you missed a pretty important point:
The proof is about the real numbers between 0 and 1 being more than the natural numbers. (not the natural numbers mapping onto themselves, that’s trivial). The proof goes like this:
– Suppose there were only countably many real numbers between 0 and 1.
– If there are, put them on a list, write the first one first, then the second and so on. (this is the part where you need some handwaving to make it work in pop science)
– Let’s build a new number: For the number in the nth spot, change the nth digit by one.
– Then you have a number which is different to every number on the list (because the nth digit is different than the nth number)
– So the number is not on the list.
– So the supposition that every real number between 0 and 1 can be put on a list is wrong
– i.e. there are more real numbers between 0 and 1 than there are natural numbers (in particular, uncountably many).
With natural number you don’t always have a digit “more on the right” to change. For example what do you do when you get to 1? That is why the diagonalization argument doesn’t work for natural number.
Also remember that to prove that you can’t do something, you have to prove that any possible way of doing that something doesn’t work. Could you make a mapping from the naturals into themselves for which a reasoning akin to the cantor diagonalization argument shows that it is not surjective? Of course. But what about the mapping n goes into n? You can’t use the diagonalization argument here because in a sense you don’t have enough digits on the right.
Was the video about infinity and how it drove one guy to Insanity?
When trying to equate infinite sizes (in terms of cardinality/number of elements) your goal is to find a function that can map each element of the first set to a unique element in the second set, and also covers all the elements in the second set
For example, if you want to prove that the whole numbers and the even whole numbers the same cardinality you could use f(n)=2n
In Cantor’s diagonal argument you assume (hoping to reach a contradiction) that this function exists. You can now map every natural number to a unique number between 0 and 1, and if that function works like we assumed, you reach every real number between 0 and 1 without missing any of them
The argument then goes that you can go in a diagonal and pick a digit from each number, and then change it. This means that the new number (which is 0.something) isn’t equal to any of the numbers you got from the function. But you were supposed to already have all of them, meaning you got a contradiction, which then means the assumption that the sizes are equal is false