The Diagonal Argument

[sigurdV]

For some reason I got suspicious and wanted to check Cantors proof that theres more real numbers than natural numbers,

but I didnt find it on Wiki. Maybe you can help?

His idea is:

(1) Making a list of decimal numbersen

(2) Asuming that the list contains all decimal numbers (and natural numbers)

(3) Then he constructs a decimal not in the list

(4) But why doesnt he simply just put it first in the obviously unfinished list?

 

Why claim theres more decimals than naturals? You can make a similar argument the other way surely?

So I wanted to see how he argued...but as I said i didnt find his argument.

 

Perhaps I need to add that Im NOT set out to destroy the theory of infinite cardinals,I simply am considering the concept of infinite sets. Thinking of the difference Aristotle made between potentiality and actuality...Maybe it applies here?

Edited June 4, 2013 by sigurdV

[phision]

watch this: http://www.youtube.com/watch?v=FiMigmLwwTM

[sigurdV]

watch this: http://www.youtube.com/watch?v=FiMigmLwwTM

The first few sentences scared me away B)

[phision]

c'est la infini

such is, infinity!

[phillip1882]

cantor's diagonal proof goes like the following.

imagine we have the following chart.

 1    2    3    4    5   
1 0    0.1  0.2  0.3  0.4...
2 0.01 0.02 0.03 0.04 0.05...
3 0.001 ...
4 0.0001 ...
5 .
6 .
 .

now i construct a number not on the chart. take the left most digit of the first number on the diagonal. 0. then add to that the second digit of the second number on the diagonal. which in this case is also 0; add the third digit of the third diagonal, and so on.

then manipulate each individual digit. in this case i'll add 1. this number will not be on the chart. so 1.111111... will not be on the chart.

its fairly easy to prove this. even if the chart goes to infinity, 1.111... cannot be on the chart because if it was, so would infinitely many other numbers. that is; almost all numbers would be equally at infinity.

[phillip1882]

here's a fun one.

let's do another chart.

this chart i'm going to do in binary.

let's start with a transcendental number.

start off with 01. copy, change 0 to 1 and vice versa, append.

0110. repeat.

01101001100101101001011001101001...

let 0.01101001100101101001011001101001... be our 0,0. we know that all rational numbers, that is all numbers that repeat in some fashion are countably infinite. so; for 0,1 we take the first rational number, and xor with our transcendental number. for 0,2, we use our second rational number and xor with our transcendental number. and so on.

for 1,0 we start off with another transcendental number.

start of with 01 again. let 0 -> 01 and 1->0.

0.010010100100101001010....

for 1,1 - 1,n; again manipulate trans2 with each rational number.

for 1,2, xor trans1 with trans2. do as above.

for 1,3 come up with yet another transcendental number. and so on.

question: will every irrational number be represented in such a chart?

Edited June 6, 2013 by phillip1882

[JMJones0424]

Sigurd, the point is that the diagonal argument shows that a table of all real numbers cannot be constructed. If I make the following generic table:

0.d₁₁d₁₂d₁₃d₁₄...d_1x...

0.d₂₁d₂₂d₂₃d₂₄...d_2x...

0.d₃₁d₃₂d₃₃d₃₄...d_3x...

0.d₄₁d₄₂d₄₃d₄₄...d_4x...

0.d_n1d_n2d_n3d_n4...d_nx...

...

 

If this table could be shown to contain all possible decimals, since we know all integers are countably infinite, then all real numbers would be countably infinite. However, I can make a decimal guaranteed to not be on that list by taking a diagonal and adding 1 to each digit. Because the new number is guaranteed to not match at least one digit of every number on the table above, it is not included in the table, therefore decimals are not countably infinite, therefore real numbers are not countably infinite.

 

EDIT: This is notably different from the integers, because if we write 1,2,3,4,5...n... that lists encompasses all integers. n+1 is in that list of integers, but 0.d₁₁₊₁d₂₂₊₁d₃₃₊₁d₄₄₊₁...d_nx+1 is not included in the top list. If you add it to the list, and take a diagonal +1 again, then you've come up with yet another number that isn't on the list.

Edited June 6, 2013 by JMJones0424

[phision]

another video

[sigurdV]

Hi!

My point...(very hard to understand) is that the cantorian argument is that C cant be in the list AND...

THAT MEANS that either C does not exist or... the list does not contain all real numbers!

Since the list is supposed to contain ALL real numbers then C (as cantor defines it) MUST be in the list PROVIDED there really is a real number C. But if C is in the list there must be a natural number n wich is associated with C by the bijection . What decimal has C as the n:th decimal? Remember that at this moment in the proof you are not allowed to claim that C is NOT in the list! Surely the value of the decimal n differs from the value of the decimal n and therefor C has no value for its decimal n and is NOT a finished real number. THERE IS NO REAL NUMBER C! You cannot then USE C to prove it is missing in the list. So the list can contain all real numbers after all. (QED)

[JMJones0424]

...THAT MEANS that either C does not exist or[/size]... the list does not contain all real numbers!...

 

Indeed. The list does not contain all real numbers. Cantor's diagonal argument shows that it can't. Therefore, real numbers aren't countably infinite. Cantor makes no assertion that all real numbers must be in the list. The argument is that if all real numbers where countably infinite, then they'd be listable. The diagonal argument shows that they can't be listed. It's a proof by contradiction.

[sigurdV]

Indeed. The list does not contain all real numbers. Cantor's diagonal argument shows that it can't. Therefore, real numbers aren't countably infinite. Cantor makes no assertion that all real numbers must be in the list. The argument is that if all real numbers where countably infinite, then they'd be listable. The diagonal argument shows that they can't be listed. It's a proof by contradiction.

(If you can find a quote on Cantors proof it would be nice... I didnt.)

 

(1) Cantor starts by assuming a bijektion, f , between the set of Natural numbers, N , and the set of Real Numbers , R.

That is equivalent to assume that ALL and any Real number can be found as a value f(n)

of some Natural number n. And that is equivalent to an infinite list,L, of the pairs <n,f(n)>.

The list L contains therefore all and any Real number.

(According to the assumption.)

 

(2) After arranging this situation Cantor aims to produce a real number C not in the list.

Thereby producing the contradiction that there is a real number C that ought to be in the list but is not!

Now please point out any mistakes I may have made so far.

Edited July 5, 2013 by sigurdV

[JMJones0424]

I don't notice anything incorrect so far, but that's not really saying much.

 

I tried tracking down Cantor's original writings, and through the wikipedia article on him I think I may have found it. I don't know German though, and as it's in PDF format, I can't easily cheat and use google translate.

 

In Journal für die reine und angewandte Mathematik volume 77, published in 1874: Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. (About a property of the totality of all real algebraic numbers.)

 

And then in the same journal, volume 84, published 1878: Ein Beitrag zur Mannigfaltigkeitslehre. (A contribution to the theory of manifolds.)

 

Also, according to the notes at the bottom of wikipedia's page on Cantor, this PDF file contains almost everything Cantor wrote (84.5 MB PDF): Gesammelte Abhandlungen mathematischen und philosophischen inhalts

[sigurdV]

Thank you!

I always tend to forget some details: Its easier for the argument to restrict the set R to the numbers between 0 and 1. Also using binary numbers is a good strategy.

 

3 Cantor now defines a real number C by selecting the n:th decimal from the number F(n)

and forms C by changing each such decimal: 0 to 1 and 1 to 0.

4 Since ALL numbers are supposed to be in the list then C must be in the list but for every number n the real number C differs in its n:th decimal from the n:th decimal of f(n), so C is not in the list after all!

5 A contradiction has arisen and the original assumption that the list contains all real numbers must be abandoned.

 

I think this is a fair description of Cantors Diagonal Proof... is there any dispute on that point?

[JMJones0424]

I am desperately grasping for air, but yes, I think that's a fair description of the argument.

[sigurdV]

I am desperately grasping for air, but yes, I think that's a fair description of the argument.

Thank you for your patience! Now all preparatory work is done...

The problem is that in order to be defined in all decimal places C need to be in the list

and contribute with one of its decimals to the number C. The problem is in point three:

(3) Cantor now defines a real number C by selecting the n:th decimal from the number F(n)

and forms C by changing each such decimal: 0 to 1 and 1 to 0.

Cantor must select one decimal each from the list containing ALL Real Numbers (according to the assumption) ...

So one decimal must come from C as placed in the list but this decimal must be altered (according to the definition)!

There is now a contradiction because C must contain a decimal,x, different from x itself.

C does not exist. (QED)

 

The definition contradicts the assumption: They cannot both be true sentences.

This fact is already known but poorly understood. Bertrand Russel invoked "The Vicious Circle Principle".

And Poincare coined the concept "Predicative Definition"!

The idea is defining some general rule forbidding the procedure involved in the definition.

But Logic already forbids the use of false premisses in a deduction.

 

Post Scriptum:

I suppose you will claim that the derivation is a "Proof by Contradiction"?

But this cannot be so since in the deductive order the existence of C is assumed

before the existence of the contradiction IMPLIED by the existence of C.

Edited July 6, 2013 by sigurdV