My Math Forum Cantor's Diagonal Argument. Infinity is Not a Number

 Topology Topology Math Forum

 March 10th, 2016, 09:57 PM #1 Senior Member   Joined: Mar 2015 From: New Jersey Posts: 861 Thanks: 68 Cantor's Diagonal Argument. Infinity is Not a Number CANTOR'S DIAGONAL ARGUMENT: The set of all infinite binary sequences is uncountable. Let T be the set of all infinite binary sequences. Assume T is countable. Then all its elements can be enumerated: 1 0 0 1 1 0............... 0 0 1 0 1 1............... 0 1 0 1 0 0.............. ............................ Let s be the binary sequence consisting of the complemented underlined digits: s = 0 1 1................... s is different from every member of the list and s belongs to T. Contradiction. Therefore T isn't countable. _________________________________________________ The argument is false: In Cantor's argument, every digit of s corresponds to the member of the list from which s differs. This requires that the length of s equals the "length" of an "infinite binary sequence" and equals the number of members in the list. Suppose instead of "infinity" you formulated Cantors Diagonal Argument with "N": Let T be the set of all N-place binary sequences. List them. Construct s. You will never arrive at a contradiction. Cantor's argument works because of the ambiguity of infinity. There is no number infinity. You can't treat infinity as if it were a finite number. Last edited by skipjack; April 4th, 2016 at 11:30 AM. Reason: change "s is countable" to "T isn't countable".
 March 11th, 2016, 09:49 AM #2 Global Moderator   Joined: Dec 2006 Posts: 16,370 Thanks: 1172 In the first half of your post, "infinite" means "non-terminating", so it isn't treated as though it meant "finite" (by definition, a finite sequence terminates). The word "infinity" isn't used. Also, the conclusion should be "T isn't countable", not "s is countable". (I've amended that for you.) Last edited by skipjack; March 12th, 2016 at 03:10 AM.
March 11th, 2016, 10:39 AM   #3
Math Team

Joined: Dec 2013
From: Colombia

Posts: 6,394
Thanks: 2101

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by zylo In Cantor's argument, every digit of s corresponds to the member of the list from which s differs.
No. We simply ensure that the $k$th digit of $s$ differs from the $k$th digit of the $k$th sequence in the list. The list can be any length. If it were finite, we'd just end $s$ in any way we felt like. All we require is that the infinite sequences have sufficient digits, which they do because the digits are countable as is the list.

Last edited by skipjack; March 12th, 2016 at 03:11 AM.

March 11th, 2016, 06:20 PM   #4
Senior Member

Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
 Originally Posted by skipjack Also, the conclusion should be "T isn't countable", not "s is countable".
Thanks.
Also, I am discussing Cantor's Diagonal argument using his language.

Cantor's Diagonal Argument only works if the enumeration is wider than it is long.*
For a finite number of rows, it is obvious.
For an infinite number of rows, you have to prove it.

1 0 1 0 0 1 .....
0 1 0 0 1 0 .....
1 0 0 1 0 0 .....
s = 0 0 1 ....... is not in the list

1 0 1
0 1 0
1 0 0
1 1 1
0 0 1
. . . .
s = 0 0 1 is in the list

1 0 1 .........
0 1 0 .........
1 0 0 .........
................
................
s = 0 0 1........ is not in the list if the list is wider than it is long- which you have to prove.

*Ref:
https://en.wikipedia.org/wiki/Cantor...gonal_argument

Last edited by skipjack; March 12th, 2016 at 03:12 AM.

 March 11th, 2016, 06:43 PM #5 Math Team   Joined: Dec 2013 From: Colombia Posts: 6,394 Thanks: 2101 Math Focus: Mainly analysis and algebra There's nothing to prove, the width and length are both countably infinite, so there are guaranteed to be sufficient numbers in the sequence.
 March 12th, 2016, 10:19 AM #6 Math Team   Joined: Jan 2015 From: Alabama Posts: 2,247 Thanks: 559 Cantor wrote in German, not English, so you are certainly NOT "using his language." What translation are you getting this from?
March 15th, 2016, 10:27 AM   #7
Senior Member

Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
 Originally Posted by zylo Cantor's Diagonal Argument only works if the enumeration is wider than it is long.
Not so.

1) 0 1 0 0 1 1 0..............
.) 1 1 0 1 0 0 1..............
n) 0 0 1 0 1 0 1..............

n+1) 1 0 0 1 0 0 1..............

No matter what n is, Cantors sequence n+1 is in the list.

 March 15th, 2016, 10:35 AM #8 Math Team   Joined: Dec 2013 From: Colombia Posts: 6,394 Thanks: 2101 Math Focus: Mainly analysis and algebra What is the (n+1)th digit of that last sequence? Besides, the proof never requires us to assume that the list is complete. It just shows that whatever list you have, there is sequence that is not on it.
March 15th, 2016, 11:03 AM   #9
Senior Member

Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
 Originally Posted by v8archie a) What is the (n+1)th digit of that last sequence? b) Whatever list you have, there is a sequence that is not on it.
a) The n+1st digit doesn't matter, Whatever it is, Cantor's sequence is in the list but different than the ones which precede it.

b) For the general case of a countable list, who says it can't be the n+1st element, it's only different than the ones which precede it. The list is still countable.

 March 15th, 2016, 02:31 PM #10 Math Team   Joined: Dec 2013 From: Colombia Posts: 6,394 Thanks: 2101 Math Focus: Mainly analysis and algebra b) If the sequence wasn't on the list, Cantor is proved right. a) If it was on the list in (n+1)st place, the (n+1)st digits differ from the (n+1)st digits of the sequence generated by the diagonal argument, and that sequence isn't on the list - and Cantor is proved right. It's really quite simple, if you stop trying to tie yourself in knots proving it to be false and just accept what is stated. If you have a list of infinite sequences, we can take the diagonal sequence which shares a digits with every sequence in the list. We then change every digit of that diagonal sequence, guaranteeing that it has at least one digit different from every sequence in the list. It is thus different from every sequence in the list and therefore is not in the list. Theorem proved. There's nothing you can do to make it be in the list. If you decide to add it to the list, you have a different list. The theorem still applies. The diagonal will be different, but it can still be used to generate a sequence that is not in your new list. 1) For any list of infinite sequences, there is an infinite sequence that is not on the list. 2) Thus no list of infinite sequences is a complete list of infinite sequences. 3) Therefore any complete set of infinite sequences cannot be formed into a list. Job done. Thanks from topsquark Last edited by skipjack; March 15th, 2016 at 04:25 PM.

 Tags argument, cantor, diagonal, infinity, number

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zylo Math 22 January 26th, 2016 09:05 PM mjcguest Applied Math 9 July 25th, 2013 07:22 AM netzweltler Applied Math 191 November 7th, 2010 02:39 PM Reckhard Abstract Algebra 11 July 31st, 2010 12:05 PM Barbarel Number Theory 2 April 10th, 2009 02:59 PM

 Contact - Home - Forums - Top