My Math Forum Help! Cantor's Diagonal Argument

 Applied Math Applied Math Forum

 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:
 Originally Posted by mjcguest 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?
The diagonal argument does hold. You've generated a non-terminating real number that isn't a Natural. To generate a Natural the sequence along the diagonal would have to be finite.

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:
 Originally Posted by mjcguest Are you saying that a natural number must be finite in length?
Exactly.

Quote:
 Originally Posted by mjcguest Would the sequence of numbers 123123123... that repeats infinitely not represent a natural number?
Not a natural number.

Quote:
 Originally Posted by mjcguest Surely in a set of infinite size, some of the numbers could be infinitely long (or is that what I'm misunderstanding?).
Even a finite set can contain infinitely long objects, but the set of natural numbers is an example of an infinitely large set which contains only finite numbers.

 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:
 Originally Posted by CRGreathouse Not a natural number.
But sure is an infinteger, remember?

 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 10-adics, where ...123123123 is a number, but I thought that would be a bit much.

 Tags argument, cantor, diagonal

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Camille91 Real Analysis 0 January 17th, 2012 03:11 PM netzweltler Applied Math 191 November 7th, 2010 01:39 PM Reckhard Abstract Algebra 11 July 31st, 2010 12:05 PM ch00blet Applied Math 3 January 12th, 2010 11:50 AM Barbarel Number Theory 2 April 10th, 2009 02:59 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top