• 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.

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

# Cantor’s Original 1891 Diagonal proof

The following 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)) This is the basis for the Diagonal proof and for the Power Set Theorem. The original German text of Cantor’s proof is also included below.

English translation by James R Meyer, copyright 2018 www.jamesrmeyer.com

On an Elementary Question on Set Theory

In the paper entitled On a property of a set of all real algebraic numbers (Journal Math. Bd. 77, S. 258), there appeared, probably for the first time, a proof of the proposition that there is an infinite set of elements, which cannot be put into a one-one correspondence with the set of all finite whole numbers 1, 2, 3, …, v, …, or as I frequently state, the infinite set of elements does not have the cardinality of the number series 1, 2, 3, …, v, …, .  From the proposition proved in §2 there follows another, that the set of all the real numbers in an arbitrary interval (a, b) cannot be arranged in the series:

w1w2, … , wv,  …

However, there is a proof of this proposition that is much simpler, and which does not depend on a consideration of the irrational numbers. We let m and n be two different characters, and consider a set M of elements:

E = (x1x2, … , xv,  … )

where each element E is defined by infinitely many coordinates x1x2, … , xv,  … and where each of the coordinates is either m or w. Let M be the set of all such elements E. For example, we might have the following three elements of M:

E1(mmmm, … )

E2 = (wwww, … )

Eu = (mwmw, … )

I now assert that such a set M does not have the cardinality of the series 1, 2, 3, …, v, …, . This follows from 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.

The proof is given by assuming that there are:

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, … that can be 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, …)

of M. 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 by the definition of bv is impossible.

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

E1, E2, …, Ev, …

otherwise we would have a 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 Cantor's proof, which is the part that is relevant to what we now call Diagonal proofs and for the Power Set 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.

The following text of the original is not included in the above translation

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.

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