My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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
mjcguest is offline  
 
July 25th, 2013, 02:38 AM   #2
Senior Member
 
Joined: Jun 2013
From: London, England

Posts: 1,312
Thanks: 115

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.
Pero is offline  
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!
mjcguest is offline  
July 25th, 2013, 03:54 AM   #4
Senior Member
 
Joined: Jun 2013
From: London, England

Posts: 1,312
Thanks: 115

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.
Pero is offline  
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!
mjcguest is offline  
July 25th, 2013, 04:36 AM   #6
Senior Member
 
Joined: Jun 2013
From: London, England

Posts: 1,312
Thanks: 115

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.
Pero is offline  
July 25th, 2013, 05:20 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 932

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.
CRGreathouse is offline  
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.
mjcguest is offline  
July 25th, 2013, 07:04 AM   #9
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is offline  
July 25th, 2013, 07:22 AM   #10
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 932

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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 04:11 PM
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
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.