My Math Forum Cantorīs diagonal argument

 Applied Math Applied Math Forum

 August 1st, 2010, 01: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 .
 August 1st, 2010, 06:36 AM #2 Senior Member   Joined: Apr 2010 Posts: 453 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
August 1st, 2010, 09:18 AM   #3
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: 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!

August 1st, 2010, 02: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.

August 1st, 2010, 03:32 PM   #5
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: 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.

August 1st, 2010, 03: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.

August 1st, 2010, 06:10 PM   #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: 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.

August 2nd, 2010, 12: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.

 August 2nd, 2010, 05:10 AM #9 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: 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).
 August 2nd, 2010, 05:24 AM #10 Math Team   Joined: Apr 2010 Posts: 2,780 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 $10^{-99}$, than one will say: you have forgotten $10^{-100}$ This is not formal though.. it is to represent the idea. Hoempa

 Tags argument, cantorīs, diagonal

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mjcguest Applied Math 9 July 25th, 2013 07:22 AM Camille91 Real Analysis 0 January 17th, 2012 03:11 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
The text passage is a discussion on Cantor's diagonal argument, a proof technique used in set theory to show that the real numbers are uncountable. The passage includes a step-by-step illustration of the argument using a finite list of numbers and then extends the concept to an infinite list.
no_question

the passage does not contain a specific mathematical question or problem to solve. it is a discussion and explanation of a mathematical concept, but it does not ask the reader to perform a calculation or solve a problem.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
My Math Forum Cantorīs diagonal argument

 Applied Math Applied Math Forum

 August 1st, 2010, 01: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 .
 August 1st, 2010, 06:36 AM #2 Senior Member   Joined: Apr 2010 Posts: 453 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
August 1st, 2010, 09:18 AM   #3
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: 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!

August 1st, 2010, 02: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.

August 1st, 2010, 03:32 PM   #5
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: 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.

August 1st, 2010, 03: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.

August 1st, 2010, 06:10 PM   #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: 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.

August 2nd, 2010, 12: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.

 August 2nd, 2010, 05:10 AM #9 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: 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).
 August 2nd, 2010, 05:24 AM #10 Math Team   Joined: Apr 2010 Posts: 2,780 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 $10^{-99}$, than one will say: you have forgotten $10^{-100}$ This is not formal though.. it is to represent the idea. Hoempa

 Tags argument, cantorīs, diagonal

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mjcguest Applied Math 9 July 25th, 2013 07:22 AM Camille91 Real Analysis 0 January 17th, 2012 03:11 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
user
The text passage is a discussion on Cantor's diagonal argument, a proof technique used in set theory to show that the real numbers are uncountable. The passage includes a step-by-step illustration of the argument using a finite list of numbers and then extends the concept to an infinite list.

TYPE: NO_QUESTION

The passage does not contain a specific mathematical question or problem to solve. It is a discussion and explanation of a mathematical concept, but it does not ask the reader to perform a calculation or solve a problem.