Can someone explain Cantor's diagonal argument?

Question

The idea as I understand it is, in binary as an example, you take the opposite of the first number in the first line, then the opposite in the second number of the second line, etc.  

The idea is that this will create a new number that is not in the the set of numbers.  But why?

Like if I had

​

0 1 0   
1 1 1  
0 0 0   
1 0 1

The first three rows would equal the fourth row, and if the set is infinite, at some point as you go up  ever possible combination of numbers would exist in that set.  Why does this method produce a new number not in the set?

Answer 1

> The first three rows would equal the fourth row, and if the set is infinite, at some point as you go up ever possible combination of numbers would exist in that set.

This doesn't follow, and the point of the diagonal argument is to show it. The argument says that, no matter what function you give me from the naturals to the set of infinite binary strings (i.e. how you list them), it is not a surjection -- that is, there is *some* string which isn't on your list. The proof is constructive, it gives you the string explicitly.

>  Why does this method produce a new number not in the set?

Because you've *defined* it to differ from every element in the set. Any element in the set is located at some position n, but your number differs from the one at position n at the n'th digit, and so they can't be equal. This is true for *every* string at *every* n.

Answer 2

You make it sound like an infinite set of binary sequences must contain every binary sequence, simply by virtue of being infinite. If so, then can you say specifically where the sequence (1,1,0,0,0,0,0,...) appears in the following infinite list?

1. (1,0,0,0,0,0,0,...)
2. (0,1,0,0,0,0,0,...)
3. (0,0,1,0,0,0,0,...)
4. (0,0,0,1,0,0,0,...)
5. (0,0,0,0,1,0,0,...)

...

Answer 3

> ever possible combination of numbers would exist in that se

Every possible *finite* combination of numbers will fit.  But you cannot fit every infinite combination of numbers.  The key to the argument is that the list of numbers can be lined up 1:1 with the place of a digit in the infinite representation of a number (between zero and 1).  When you use only finite binary numbers you do indeed get the opposite result!  Leaving off the decimal(binary?) point here is a pretty key oversight.

Answer 4

You took the *opposite* of a digit from the first number. That means your new number is not the same as your first number, since you are changing one of the digits.

You took the *opposite* of a digit from the second number. That means your new number is not the same as your second number, since you are changing one of the digits.

Doing this again, we ensure our new number does not match our third number.

Doing this again, we ensure our new number does not match our fourth number.

ect.

This diagonal method will produce a number that does not match any of the numbers from our list.

Answer 5

The method works for finite strings as well, but you need the number of rows to be the same as the length of the rows. In your example, this would mean you either need rows of length 4, or only three rows.

The reason the diagonal argument works is that you have a *diagonal*, which a rectangle doesn't quite have, in this setting :-)

Answer 6

In your example, each row is only three characters long. But in Cantor's actual argument, each row is infinitely long.

So Cantor's argument doesn't "stop" with creating a string that differs from each of the first three rows. When applying Cantor's argument, you're building an infinite string, and you also look at the fourth row as well as the first three, and you construct your string to be different from the fourth row (by having its fourth character be different from the fourth character of the fourth row).

TL;DR Cantor's argument is about infinite strings, not strings of length 3, so don't assume that your example captures what's important about Cantor's argument.

Answer 7

The new number is different in the first position relative to first listed  number. Therefore, it can't be the same as the first listed  number. Etc

Answer 8

The point is to make an element out of an infinite list that couldn't possibly exist in the list. (Edit: if you could, you would contradict the method you used to construct the list.)

Answer 9

This is an easy to google question and you didn't even bother engaging with the people who were kind enough to engage with your post. We have no idea if we helped you or not, we have no idea if you really understood or even cared what was the flaw in your argument.  


Anyway, in your example: You only can make 3 choices: first, second, and third digit. But there are 8 possible combinations of 3 digit binary numbers. So you don't have enough choices to make a new number.

If you have infinitely many choices, you can pick the first digit to be different than the first number, the second digit different than the second number, etc. You now have enough choices to make your new number different from every number in your list by at least one digit. This is the key difference in behavior between the infinite and the finite.

Infinity is weird - you can take the natural numbers (0, 1, 2, 3, 4, etc) and map them to the even natural numbers in a 1 to 1 fashion (0 ↔ 0, 1↔2, 2↔4, 3↔6, 4↔8, etc). But if you have a finite set of numbers, you can't do the same.

Answer 10

Cantor's diagonal argument is most clear in proving that for any set X with at least 2 elements, the set of functions N -> X is uncountable. Formally, suppose it were countable, so that you could enumerate all such functions {f\_1, f\_2, f\_3, .... }. For each n \\in N, choose some number f(n) such that f(n) != f\_n(n). Then f is a function N -> X which cannot be any of the f\_i, by construction, so the set of functions N->X is uncountable.   


In your example, you would need strings of length 4 at least so for example:  


0 0 0 1  
0 0 1 1  
0 0 1 0  
0 1 0 1  


Then you could choose a new string such as 1 1 0 0 (using the algorithm of always flipping the ith digit) and get a genuinely new element.