This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility   Close this tip.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.
 

Cantor’s Original 1891 Diagonal proof

This is an English translation of the main part of Cantor’s original 1891 proof, (Footnote: Georg Cantor, ‘Über eine elemtare Frage de Mannigfaltigketslehre’, Jahresberich der Deutsch. Math. Vereing. Bd. I, S. pp 75-78 (1891). See below for the original German text.) which is the basis for Diagonal proofs, and for the Power Set Theorem.

 

The proof proceeds as follows:

 

First of all, Cantor assumes that there is an infinite set of elements (which he calls M) where each element is defined by an infinite sequence of values, which can be either m or w, so that for example, we might have:

 

E1(mmmm, … )

E2 = (wwww, … )

Eu = (mwmw, … )

 

Cantor makes the following proposition:

 

If E1, E2, …, Ev is any infinite series of elements of the set M, then there always exists an element E0 of M, which cannot be the same element as any element Ev.

 

Cantor goes on to state the proof of this proposition:

 

Suppose we have:

 

E1 = (a1.1 a1.2a1.v …)

E2 = (a2.1 a2.2a2.v …)

Eu = (au.1 au.2au.v …)

 

where each au.v is either m or w.

 

Then there is a series b1, b2, …, bn, … defined so that bv is also equal to m or w but is different from av.v. That is, if av.v m, then bv = w.

 

Consider the element

E0 = (b1, b2, b3, …)

 

One sees straight away, that the equation

E0 = Eu

cannot be satisfied by any positive integer u, otherwise for that value of u and for all values of v, we would have:

bv = au.v

and so we would in particular have:

bu = au.u

which through the definition of bv is impossible.

 

From this proposition it follows immediately that the entirety of all elements of M cannot be put into a sequence such as:

E1, E2, …, Ev, …

otherwise we would have the contradiction, that an element E0 would be both an element of M, but also not an element of M.

 

This concludes the principal part of the proof.

 

 

Footnotes:

 

 

Cantor’s 1891 proof in the original German

 

Über eine elementare Frage der Mannigfaltigkeitslehre

In dem Aufsätze, betitelt: Über eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen (Journ. Math. Bd. 77, S. 258), findet sich wohl zum ersten Male ein Beweis für den Satz, daß es unendliche Mannigfaltigkeiten gibt, die sich nicht gegenseitig eindeutig auf die Gesamtheit aller endlichen ganzen Zahlen 1, 2, 3,…, ν,… beziehen lassen, oder, wie ich mich auszudrücken pflege, die nicht die Mächtigkeit der Zahlenreihe 1, 2, 3,…, ν,… haben. Aus dem in § 2 Bewiesenen folgt nämlich ohne weiteres, daß beispielsweise die Gesamtheit aller reellen Zahlen eines beliebigen Intervalles (α…β) sich nicht in der Reihenform

 

ω1, ω2, …, ων, …

 

darstellen läßt.

 

Es läßt sich aber von jenem Satze ein viel einfacherer Beweis liefern, der unabhängig von der Betrachtung der Irrationalzahlen ist.

Sind nämlich m und w irgend zwei einander ausschließende Charaktere, so betrachten wir einen Inbegriff M von Elementen

 

E = ( x1, x2, xν, … ),

 

welche von unendlich vielen Koordinaten x1, x2, xν, … abhängen, wo jede dieser Koordinaten entweder m oder w ist. M sei die Gesamtheit aller Elemente E.

Zu den Elementen von M gehören beispielsweise die folgenden drei:

 

EI = ( m, m, m, m,… ),

EII = ( w, w, w, w, … ),

EIII = ( m, w, m, w, … ).

 

Ich behaupte nun, daß eine solche Mannigfaltigkeit M nicht die Mächtigkeit der Reihe 1, 2,…,ν ,… hat.

Dies geht aus folgendem Satze hervor:

“Ist E1 ,E2,…,Eν,… irgendeine einfach unendliche Reihe von Elementen der Mannigfaltigkeit M, so gibt es stets ein Element E0 von M, welches mit keinem Eν übereinstimmt.”

Zum Beweise sei

 

E1 = ( a1,1, a1,2, …, a1,ν, … )

E2 = ( a2,1, a2,2, …, a2,ν, … )

Eμ = ( aμ,1, aμ,2, …, aμ,ν, … )

 

Hier sind die aμ,ν in bestimmter Weise m oder w. Es werde nun eine Reihe b1, b2, bν, … so definiert, daß bν auch nur gleich m oder w und von aμ,ν verschieden sei.

Ist also aμ,ν = m, so ist bν = w, und ist aμ,ν = w, so ist bν = m.

Betrachten wir alsdann das Element

E0 = ( b1, b2, b3, … ),

 

von M, so sieht man ohne weiteres, daß die Gleichung

 

E0 = Eμ

 

für keinen positiven ganzzahligen Wert von μ erfüllt sein kann, da sonst für das betreffende μ und für alle ganzzahligen Werte vonν

 

bν = aμ,ν ,

 

also auch im besondem

 

bμ = aμ,μ ,

 

wäre, was durch die Definition von bν ausgeschlossen ist. Aus diesem Satze folgt unmittelbar, daß die Gesamtheit aller Elemente von M sich nicht in die Reihenform: E1, E2, …, Eν, … bringen läßt, da wir sonst vor dem Widerspruch stehen würden, daß ein Ding E0 sowohl Element von M, wie auch nicht Element von M wäre.

 

Dieser Beweis erscheint nicht nur wegen seiner großen Einfachheit, sondern namentlich auch aus dem Grunde bemerkenswert, weil das darin befolgte Prinzip sich ohne weiteres auf den allgemeinen Satz ausdehnen läßt, daß die Mächtigkeiten wohldefinierter Mannigfaltigkeiten kein Maximum haben oder, was dasselbe ist, daß jeder gegebenen Mannigfaltigkeit L eine andere M an die Seite gestellt werden kann, welche von stärkerer Mächtigkeit ist als L.

 

Sei beispielsweise L ein Linearkontinuum, etwa der Inbegriff aller reellen Zahlgrößen z, die ≧ 0 und ≦ 1 sind.

 

Man verstehe unter M den Inbegriff aller eindeutigen Funktionen ƒ(x), welche nur die beiden Werte 0 oder 1 annehmen, während x alle reellen Werte, die ≧ 0 und ≦ 1 sind, durchläuft.

 

Daß M keine kleinere Mächtigkeit hat als L, folgt daraus, daß sich Teilmengen von M angeben lassen, welche dieselbe Mächtigkeit haben wie L, z. B. die Teilmenge, welche aus allen Funktionen von x bestellt, die für einen einzigen Wert x0 von x den Wert 1, für alle ändern Werte von x den Wert 0 haben.

 

Es hat aber auch M nicht gleiche Mächtigkeit mit L, da sich sonst die Mannigfaltigkeit M in gegenseitig eindeutige Beziehung zu der Veränderlichen z bringen ließe, und es könnte M in der Form einer eindeutigen Funktion der beiden Veränderlichen x und z

 

φ( x, z )

 

gedacht werden, so daß durch jede Spezialisierung von z ein Element ƒ(x) = φ( x, z ) von M erhalten wird und auch umgekehrt jedes Element ƒ(x) von M aus φ(x, z) durch eine einzige bestimmte Spezialisierung von z hervorgeht. Dies führt aber zu einem Widerspruch. Denn versteht man unter g (x) diejenige eindeutige Funktion von x, welche nur die Werte 0 oder 1 annimmt und für jeden Wert von x von φ(x, x) verschieden ist, so ist einerseits g (x) ein Element von M, andererseits kann g (x) durch keine Spezialisierung z = z0 aus φ(x,z) hervorgehen, weil φ(z0, z0) von g (z0) verschieden ist.

 

Ist somit die Mächtigkeit von M weder kleiner noch gleich derjenigen von L, so folgt, daß sie größer ist als die Mächtigkeit von L. (Vgl. Crelles Journal Bd. 84, S. 242) .

 

Ich habe bereits in den “Grundlagen einer allgemeinen Mannigfaltigkeitslehre” (Leipzig 1883; Math. Ann. Bd. 21) durch ganz andere Hilfsmittel gezeigt, daß die Mächtigkeiten kein Maximum haben; dort wurde sogar bewiesen, daß der Inbegriff aller Mächtigkeiten, wenn wir letztere ihrer Größe nach geordnet denken, eine “wohlgeordnete Menge” bildet, so daß es in der Natur zu jeder Mächtigkeit eine nächst größere gibt, aber auch auf jede ohne Ende steigende Menge von Mächtigkeiten eine nächst größere folgt.

 

Die “Mächtigkeiten” repräsentieren die einzige und notwendige Verallgemeinerung der endlichen “Kardinalzahlen”, sie sind nichts anderes als die aktual-unendlich-großen Kardinalzahlen, und es kommt ihnen dieselbe Realität und Bestimmtheit zu wie jenen; nur daß die gesetzmäßigen Beziehungen unter ihnen, die auf sie bezügliche “Zahlentheorie” zum Teil eine andersartige ,ist als im Gebiete des Endlichen.

 

Die weitere Erschließung dieses Feldes ist Aufgabe der Zukunft.

 

 

 

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.

 

If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.

 

 

Please wait for comments to load …  

 

The Lighter Side

 

NEWS

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

There’s something about Gödel by Francesco Berto

There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.

 

 

Easy Footnotes

I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).

 

 

O’Connor’s “computer checked” proof

I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.

 

 

New page on Chaitin’s Constant

There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.

 

Previous Blog Posts  

 

13 May 2015 Good Math, Bad Math?

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem

 

– a page with general links:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.


Note: for some browsers JavaScript must be enabled for this to operate correctly.

 

Comments

 

Comments on this site are welcome, please see the comment section.

 

Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.

 

If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.

 

Feedback about site design would also be appreciated so that I can improve the site.

 


Copyright © James R Meyer 2012 - 2017  
www.jamesrmeyer.com