My Math Forum  

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

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 1st, 2010, 02:25 AM   #1
Senior Member
 
Joined: Aug 2010
From: Germany

Posts: 132
Thanks: 1

Cantorīs diagonal argument

To illustrate Cantorīs diagonal arument, we can also treat a restricted amount of numbers, e.g. the ten-thousandths between 0 an 1. Since we are treating a restricted amount of numbers we will restrict our sequence to 4 numbers.
To illustrate it:

z1 = 0.a11 a12 a13 a14
z2 = 0.a21 a22 a23 a24
z3 = 0.a31 a32 a33 a34
z4 = 0.a41 a42 a43 a44

x = 0.x1 x2 x3 x4

If aii = 5, then xi = 4, otherwise xi = 5.

using real values:

z1 = 0.2327
z2 = 0.5249
z3 = 0.6670
z4 = 0.8221

x = 0.5555

Now we can say there is a new number x. But we can also see, that this number is only new, because we were restricted to list just 4 numbers, and not all the ten-thousandths between 0 and 1 (0.0000, 0.0001 ... 0.9999). No matter which 4 numbers we choose, there will always be a new number x. If we are going to the limits now and treat an infinite amount of numbers between 0 and 1, the principle doesnīt change. We are always restricted to a finite sequence of numbers, even if the sequence is approaching infinity. And if we get a "new" number, then bound to the fact, that we are not able to list an infinite sequence of numbers.
So, this diagonal argument doesnīt prove, that there is more real numbers than natural numbers. But this argument is basic to the set theory .
netzweltler is offline  
 
August 1st, 2010, 07:36 AM   #2
Senior Member
 
Joined: Apr 2010

Posts: 451
Thanks: 1

Re: Cantorīs diagonal argument

If we could find some theorems ,axioms ,definitions which we could explicitly mention and base our arguments ,then Cantor's construction could be more convincing .

But then again to say that Cantor's construction is wrong we should have laws and principals upon which we could base our arguments
outsos is offline  
August 1st, 2010, 10:18 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Cantorīs diagonal argument

Quote:
Originally Posted by netzweltler
If we are going to the limits now and treat an infinite amount of numbers between 0 and 1, the principle doesnīt change. We are always restricted to a finite sequence of numbers, even if the sequence is approaching infinity. And if we get a "new" number, then bound to the fact, that we are not able to list an infinite sequence of numbers.
So, this diagonal argument doesnīt prove, that there is more real numbers than natural numbers. But this argument is basic to the set theory .
That's a misunderstanding of the theorem. You get an infinitely long list, which you can describe mathematically -- you don't need to actually write each member on paper if you can say where they will go. But no matter what infinite list you give, Cantor's argument will give you a real number not on the list. This shows that, whatever list you start with, it wasn't complete. Because it could have been *any* list, this shows that *no* such list can have all the reals on it. Deep stuff!

Quote:
Originally Posted by outsos
If we could find some theorems ,axioms ,definitions which we could explicitly mention and base our arguments ,then Cantor's construction could be more convincing .
Done.

http://us.metamath.org/mpeuni/canth2.html

The axioms needed in this formalism are
Propositional calculus: ax-1 ax-2 ax-3 ax-mp
Predicate calculus: ax-5 ax-6 ax-7 ax-gen ax-8 ax-9 ax-10 ax-11 ax-12 ax-13 ax-14 ax-17
ZF: ax-ext ax-rep ax-un ax-pow ax-reg

Notice that the axiom of infinity ("the set Z of integers exists") isn't even needed!
CRGreathouse is offline  
August 1st, 2010, 03:31 PM   #4
Senior Member
 
Joined: Aug 2010
From: Germany

Posts: 132
Thanks: 1

Re: Cantorīs diagonal argument

Quote:
But no matter what infinite list you give, Cantor's argument will give you a real number not on the list.
Feel free to enhance the list by another number. Thus we are no longer treating the ten-thousandths but the hundred-thousandths.

z1 = 0.a11 a12 a13 a14 a15
z2 = 0.a21 a22 a23 a24 a25
z3 = 0.a31 a32 a33 a34 a35
z4 = 0.a41 a42 a43 a44 a45
z5 = 0.a51 a52 a53 a54 a55

The principle is still the same:

The resulting number x is only new, because we were restricted to list just 5 numbers, and not all the hundred-thousandths between 0 and 1 (0.00000, 0.00001 ... 0.99999).


Feel free to enhance the list by another number. Thus we are no longer treating the hundred-thousandths but the millionths.

z1 = 0.a11 a12 a13 a14 a15 a16
z2 = 0.a21 a22 a23 a24 a25 a26
z3 = 0.a31 a32 a33 a34 a35 a36
z4 = 0.a41 a42 a43 a44 a45 a46
z5 = 0.a51 a52 a53 a54 a55 a56
z6 = 0.a61 a62 a63 a64 a65 a66

The principle is still the same:

The resulting number x is only new, because we were restricted to list just 6 numbers, and not all the millionths between 0 and 1 (0.000000, 0.000001 ... 0.999999).

Where do you want me to stop? At which stage do you think the principle changes? You can see, if you go on, the list is approaching infinity as well as the digits.
netzweltler is offline  
August 1st, 2010, 04:32 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Cantorīs diagonal argument

Quote:
Originally Posted by netzweltler
Where do you want me to stop? At which stage do you think the principle changes? You can see, if you go on, the list is approaching infinity as well as the digits.
I think what you're saying is: "Cantor proves that the real numbers aren't finite, because his construction creates a real number not on any finite list." But the construction works with infinite lists as well. Don't give 4-member lists or 5-member lists, give a list with countably many members.
CRGreathouse is offline  
August 1st, 2010, 04:51 PM   #6
Senior Member
 
Joined: Aug 2010
From: Germany

Posts: 132
Thanks: 1

Re: Cantorīs diagonal argument

Quote:
Originally Posted by CRGreathouse
Don't give 4-member lists or 5-member lists, give a list with countably many members.
I canīt give more than a 4-member list when I am treating ten-thousandths or a 5-member list when I am treating hundred-thousandths. It would no longer be diagonal.
netzweltler is offline  
August 1st, 2010, 07:10 PM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Cantorīs diagonal argument

Quote:
Originally Posted by netzweltler
I canīt give more than a 4-member list when I am treating ten-thousandths or a 5-member list when I am treating hundred-thousandths. It would no longer be diagonal.
I don't know what you're saying, but the argument is designed for lists of infinite length, not of finite length as in your examples.
CRGreathouse is offline  
August 2nd, 2010, 01:21 AM   #8
Senior Member
 
Joined: Aug 2010
From: Germany

Posts: 132
Thanks: 1

Re: Cantorīs diagonal argument

Quote:
Originally Posted by CRGreathouse
I don't know what you're saying, but the argument is designed for lists of infinite length, not of finite length as in your examples.
Thatīs what Iīm pointing to. You can create a list as big as you want it, and the principle doesnīt change. Take into account, in order to apply the diagonal argument, the more digits the numbers have the more members you will get in the list. This is also valid for an imaginary list of infinite length.
netzweltler is offline  
August 2nd, 2010, 06:10 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Cantorīs diagonal argument

Look, let's just make this simple (since I don't understand your philosophical objection). Do you think that Cantor's theorem is wrong? Then you should be able to make a list with all real numbers on it. Then we can apply Cantor's diagonalization to it and see what new number is produced.

It's easy to list all the rational numbers, and you can even list all algebraic numbers if you like. But the proof shows that you can't list all real numbers (and hence can't even list the transcendentals).
CRGreathouse is offline  
August 2nd, 2010, 06:24 AM   #10
Math Team
 
Joined: Apr 2010

Posts: 2,778
Thanks: 361

Re: Cantorīs diagonal argument

You can list all natural numbers: 0, 1, 2, 3 and so on. You will not forget any number between the first and the last one you have mentioned.
You can't list all real numbers. If you would start (from 0) and would say a number larger than 0, for example , than one will say: you have forgotten

This is not formal though.. it is to represent the idea.

Hoempa
Hoempa is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
argument, cantorīs, 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 08:22 AM
Diagonal Camille91 Real Analysis 0 January 17th, 2012 04:11 PM
Cantor's diagonal argument - "disproof" Reckhard Abstract Algebra 11 July 31st, 2010 01: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 03:59 PM





Copyright © 2017 My Math Forum. All rights reserved.