My Math Forum  

Go Back   My Math Forum > College Math Forum > Topology

Topology Topology Math Forum


Thanks Tree11Thanks
Reply
 
LinkBack Thread Tools Display Modes
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".
zylo is offline  
 
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.
skipjack is offline  
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 View Post
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.
v8archie is offline  
March 11th, 2016, 06:20 PM   #4
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
Originally Posted by skipjack View Post
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.
zylo is offline  
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.
v8archie is offline  
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?
Country Boy is offline  
March 15th, 2016, 10:27 AM   #7
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
Originally Posted by zylo View Post
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.

Cantor's diagonal argument doesn't lead to a contradiction.
zylo is offline  
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.
v8archie is offline  
March 15th, 2016, 11:03 AM   #9
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 861
Thanks: 68

Quote:
Originally Posted by v8archie View Post
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.
zylo is offline  
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.
v8archie is offline  
Reply

  My Math Forum > College Math Forum > Topology

Tags
argument, cantor, diagonal, infinity, number



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cantor's Diagonal Argument zylo Math 22 January 26th, 2016 09:05 PM
Help! Cantor's Diagonal Argument mjcguest Applied Math 9 July 25th, 2013 07:22 AM
Cantorīs diagonal argument netzweltler Applied Math 191 November 7th, 2010 02:39 PM
Cantor's diagonal argument - "disproof" Reckhard Abstract Algebra 11 July 31st, 2010 12:05 PM
Cantor diagonal functions Barbarel Number Theory 2 April 10th, 2009 02:59 PM





Copyright © 2017 My Math Forum. All rights reserved.