My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Reply
 
LinkBack Thread Tools Display Modes
January 13th, 2016, 02:47 PM   #1
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 834
Thanks: 67

Cantor's Diagonal Argument

https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Let T be the set of all infinite sequences of binary digits.
Each such sequence represents a positive integer or 0.*

T is countable.

*1010 = 1x2^0 + 0x2^1 + 1x2^2 + 0x2^3 = 5

Every real number can be represented by an infinite binary sequence.
The real numbers are countable.

Last edited by skipjack; January 13th, 2016 at 03:17 PM.
zylo is offline  
 
January 13th, 2016, 03:24 PM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 16,226
Thanks: 1150

Quote:
Originally Posted by zylo View Post
Every real number can be represented by an infinite binary sequence.
That doesn't imply that all such sequences can be used simultaneously in a diagonalization argument.
skipjack is offline  
January 13th, 2016, 04:20 PM   #3
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 834
Thanks: 67

Every sequence of zeros and ones represents a positive integer or 0.

Then the set T of all infinite sequences of zeros and ones is countable in the sense that the set of all the integers is countable.

Cantor maintains T is not countable.

It's possible that 3 appears way, way, down the line. But it's there.

What are we talking about?
1) T={s1,s2,..}={{1001...},{01110...}.....}, T is the set of all sets of infinite sequences. (T is not the set of infinite sequences.) Countable
or
2) T={1001...,0110,....}, sequentially without the commas. (T is the set of all infinite sequences.) How do you create this set? How do you know you have created the set if you can't distinguish between infinite member sets?

I presume the former. The latter is never-never land, and you can pretty much say anything you like about it. Alright I'll think about it: List infinite sets of zeros and ones in sequence. Then create one set which contains all these sequences. So you are talking about an infinite arrangement of infinite sequences. But what does that have to do with countability of binary or decimal numbers? By what rule are you selecting infinite series from this infinite series to count?

You are just playing word games with symbols.

Ref https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Last edited by skipjack; January 13th, 2016 at 08:39 PM.
zylo is offline  
January 13th, 2016, 08:44 PM   #4
Global Moderator
 
Joined: Dec 2006

Posts: 16,226
Thanks: 1150

Are you discussing these things with yourself? You seem to be answering your own questions.
skipjack is offline  
January 13th, 2016, 10:08 PM   #5
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 834
Thanks: 67

"In his 1891 article*, Cantor considered the set T of all infinite sequences of binary digits (i.e. consisting only of zeros and ones). He begins with a constructive proof of the following theorem:

If s1, s2, … , sn, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no sn in the enumeration.
To prove this, given an enumeration of arbitrary members from T, like e.g.

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)"

------------------------------------------
But that's ridiculous. You don't count a set with an infinite number of elements by selecting sub-sets of infinite elements and counting the number of such sub-sets. Of course the set will be uncountable because that's not how you count.

No matter what the sequence of '0's and '1's is, you count the set sequentially.
S=0,1,0,1,1, ....
N=1,2,3,4,5,......
That's countable.

* https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

EDIT: Furthermore, how are the digits arranged? You can't even define the set of all binary sequences because you can't even start to write it down.
Is it {0,1,0,0...} or {1,1,0.1....},.. No matter how many digits you add these are different sets. Or is the assumption that no matter how you start, any arbitrary sequence, such as the second one, will be found somewhere in the sequence?

Last edited by zylo; January 13th, 2016 at 10:34 PM.
zylo is offline  
January 13th, 2016, 10:26 PM   #6
Global Moderator
 
Joined: Dec 2006

Posts: 16,226
Thanks: 1150

Is it mathematically correct? You can call it ridiculous if you wish, and it might not do what you would do, but it's correct.
skipjack is offline  
January 14th, 2016, 05:31 AM   #7
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,357
Thanks: 2086

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by zylo View Post
No matter what the sequence of '0's and '1's is, you count the set sequentially.
S=0,1,0,1,1, ....
N=1,2,3,4,5,......
That's countable.
Quite clearly, Cantor is not talking about counting the elements of the sequences. He is counting (or rather, failing to count) the sequences themselves.

Quote:
Furthermore, how are the digits arranged? You can't even define the set of all binary sequences because you can't even start to write it down.
You can start to create your list just by picking a sequence that is not already in it and adding it to the end. It doesn't matter how the digits are arranged.

The proof uses the assumption that we can complete the list to produce a contradiction.
v8archie is offline  
January 14th, 2016, 09:36 AM   #8
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 834
Thanks: 67

To count the elements in the set T of all binary numbers arrange them in a column in any order and start counting diagonally:

1,0,0,1,0,0,.......
0,1,0,0,1,0......
1,0,1,0,1,0......
1,1,0,1,1,0......
.....................

1, 0,0, 1,1,0, 1,0,0,1, ......
1, 2,3, 4,5,6, .................

This is the same argument used to count the rationals. If it doesn't work here, it doesn't work there.

Cantor's argument that T is uncountable is wrong.

https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Last edited by skipjack; January 14th, 2016 at 01:20 PM.
zylo is offline  
January 14th, 2016, 09:43 AM   #9
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,357
Thanks: 2086

Math Focus: Mainly analysis and algebra
You are just clutching at straws. You have no understanding of what you are doing.

In this case, you have no idea whether you will have every sequence. And indeed, Cantor's argument shows that you won't because the list you require can't be constructed.
v8archie is offline  
January 14th, 2016, 10:28 AM   #10
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 834
Thanks: 67

Quote:
Originally Posted by v8archie View Post
You are just clutching at straws. You have no understanding of what you are doing.

In this case, you have no idea whether you will have every sequence. And indeed, Cantor's argument shows that you won't because the list you require can't be constructed.
It's the same diagonal counting scheme used to show the rationals are countable.

If the list can't be constructed then T can't be constructed. If you can't construct a list of all binary numbers, how can you construct the set of all binary numbers?
zylo is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
argument, cantor, cantors, diagonal



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help! Cantor's Diagonal Argument mjcguest Applied Math 9 July 25th, 2013 07:22 AM
Cantors 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
Counting the reals: Cantor's Diagonal Proof ch00blet Applied Math 3 January 12th, 2010 12:50 PM
Cantor diagonal functions Barbarel Number Theory 2 April 10th, 2009 02:59 PM





Copyright © 2017 My Math Forum. All rights reserved.