
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
July 25th, 2013, 01:01 AM  #1 
Newbie Joined: Jul 2013 Posts: 4 Thanks: 0  Help! Cantor's Diagonal Argument
I thought I understood it... but I'm missing something fundamental, because (according to my logic) I can use Cantor's diagonal argument to find a natural number that's not in the set of natural numbers! So for clarity... that statement is clearly wrong, but I can't see where I've gone wrong! Any help appreciated. Here's the "logic": 1) For the purpose of presentation, I will write the natural numbers backwards, so that an infinite (maybe a bad choice of word!) number of leading zero's can be assumed without me running out of screen. i.e. The number "123" will be written "321000000...", the number "35367" as "7635300000...." 2) So I now make my list of all natural numbers. It doesn't need to be wellordered as I don't believe this is a prerequisite for the diagonal argument. So my list will look something like N1 = [color=#FF0000]1[/color]2362746294800000... N2 = 4[color=#FF0000]2[/color]894234890234270... N3 = 72[color=#FF0000]0[/color]48472000000000... ... Using the diagonal argument, I can now identify a real number that is not in the list of real numbers N0 = 231... and so on (i.e. 2 is not N1's first, 3 is not N2's second and so on) There's a flaw, and it might have something to do with writing the numbers backwards (but I'm struggling to see why to be honest); help!! Thanks Matt 
July 25th, 2013, 02:38 AM  #2 
Senior Member Joined: Jun 2013 From: London, England Posts: 1,316 Thanks: 116  Re: Help! Cantor's Diagonal Argument
I can't see how you are generating a Natural number here. You are generating an infinite sequence of digits: that doesn't represent a missing Natural.

July 25th, 2013, 03:18 AM  #3 
Newbie Joined: Jul 2013 Posts: 4 Thanks: 0  Re: Help! Cantor's Diagonal Argument
Hi Pero  thanks for the quick response. Appreciated. I guess that's where I'm struggling to understand it. On the face of it (to me at least) putting a "0." in front of each of the N1, N2 numbers returns this pretty much back to Cantor's original demonstration of the diagonal argument. Removing the "0." (as above) leaves a series of natural numbers  an infinite sequence of them, but each line will contain a single natural number (albeit reversed). I can't see why the diagonal argument then fails to hold? In Cantor's argument, the method of generation of the real numbers isn't specified, so I don't think the generation of the naturals would need to be in order to draw a comparison. Like I said... confused! 
July 25th, 2013, 03:54 AM  #4  
Senior Member Joined: Jun 2013 From: London, England Posts: 1,316 Thanks: 116  Re: Help! Cantor's Diagonal Argument Quote:
I'm not entirely sure what your argument is precisely, but you seem to be saying, That n = 147591... is a Natural. But, if the sequence of digits goes on forever, then it's an infinite sequence, not a Natural number.  
July 25th, 2013, 04:27 AM  #5 
Newbie Joined: Jul 2013 Posts: 4 Thanks: 0  Re: Help! Cantor's Diagonal Argument
I think the penny is starting to drop... but I'm not quite there yet! Bear with me for one more question. Have I missed something fundamental about natural numbers? Are you saying that a natural number must be finite in length? Surely in a set of infinite size, some of the numbers could be infinitely long (or is that what I'm misunderstanding?). Would the sequence of numbers 123123123... that repeats infinitely not represent a natural number? Penny almost dropped I think! 
July 25th, 2013, 04:36 AM  #6 
Senior Member Joined: Jun 2013 From: London, England Posts: 1,316 Thanks: 116  Re: Help! Cantor's Diagonal Argument
Yes, that is your mistake. 123123... is not a natural number. For a start, what power of 10 would the first 1 be? Note that a Natural number of the form 123123 = 1*(100,000) + 2*(10,000) + 3*(1000) + 1*(100) + 2*(10) + 3 You have touched on a paradox of sorts, which is that: The set of Natural numbers is infinite, but no individual Natural number is infinite. Understanding this is at the heart of the concept of infinity, and indeed at the heart of rigorous mathematics. In any case, all Natural numbers are of finite length. 
July 25th, 2013, 05:20 AM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Help! Cantor's Diagonal Argument Quote:
Quote:
Quote:
 
July 25th, 2013, 05:50 AM  #8 
Newbie Joined: Jul 2013 Posts: 4 Thanks: 0  Re: Help! Cantor's Diagonal Argument
Bingo! Thanks everyone  penny has now dropped.

July 25th, 2013, 07:04 AM  #9  
Math Team Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory  Re: Help! Cantor's Diagonal Argument Quote:
 
July 25th, 2013, 07:22 AM  #10 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Help! Cantor's Diagonal Argument
I considered explaining the 10adics, where ...123123123 is a number, but I thought that would be a bit much.


Tags 
argument, cantor, diagonal 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Diagonal  Camille91  Real Analysis  0  January 17th, 2012 03:11 PM 
Cantorīs diagonal argument  netzweltler  Applied Math  191  November 7th, 2010 01: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 11:50 AM 
Cantor diagonal functions  Barbarel  Number Theory  2  April 10th, 2009 02:59 PM 