Logic and Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2024 https://www.jamesrmeyer.com

For a discussion regarding some aspects of this paper, see The Diagonal Proof.

Cantor’s Original 1891 Diagonal proof
Über eine elemtare Frage de Mannigfaltigkeitslehre
(On an elementary question of set theory)
• English Translation •

 

The following is an English translation of the main part of Cantor’s original 1891 proof. (Footnote: Georg Cantor, “Über eine elemtare Frage de Mannigfaltigkeitslehre”, 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. Note that there is an English translation of the Grundlagen that is referred to as “Grundlagen einer allgemeinen Mannigfaltigkeitslehre” in Cantor’s text.

 

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

 

Note that the term “cardinality” for infinite sets was not in current usage at the time Cantor wrote this paper; he uses the term “Mächtigkeit”, which can have corresponding English meanings such as ‘thickness’, ‘width’, ‘mightiness’, ‘potency’, etc. I have used the term “magnitude” as a suitable translation.

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), (Footnote: Translator’s note, see an online English translation of that article at On a Property of the Set of all Real Algebraic Numbers.) 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 magnitude 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 magnitude 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.2 … a1.v …)

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

Eu = (au.1 au.2 … au.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.

 

Note: The above is the part of Cantor’s paper which is relevant to what we now call Diagonal proofs. The second part which follows below is often referred to as Cantor’s Power set proof, but in fact it is only a proof of a specific case, and is not a general proof that there cannot be a one-to-one correspondence of a set and its Power set, see the Power Set Proof.

 

This proof appears remarkable not only because of its great simplicity, but especially because the principles used in it can easily be extended to the general proposition that the magnitudes of well-defined sets have no maximum or, to the same effect, that for every given set L another set M can be generated which is greater than L.

 

For example, let L be a linear continuum, for example the set of all real number quantities z that are ≧ 0 and ≦ 1.

 

By M we understand the set of all well-defined functions ƒ(x), which only assume the two values ​​0 or 1, while x runs through all real values, which are ≧ 0 and ≦ 1.

 

That M does not have a smaller magnitude than L follows from the fact that subsets of M can be defined which have the same magnitude as L, e.g. B is the subset which comprises all functions of x, which have the value 1 for a single value x0 of x, the value 0 for all other values ​​of x.

 

However, M also does not have the same magnitude as L, since otherwise the set M could be brought into a well-defined relationship to a variable z, and M can be in the form of a unique function of the two variables x and z

φ(xz)

such that for each occurrence of z, there is a corresponding element ƒ(x) = φ(xz) of M and vice versa, for every element ƒ(x) of M from φ(xz) there is a single corresponding occurrence of z. But this leads to a contradiction. Because given that g(x) is the unique function on x which only takes the values ​​0 or 1 and is different from φ(xx) for each value of x, then on the one hand g(x) is an element of M, on the other hand, g(x) cannot result from φ(xz) by any specific instance of z = z0, because φ(z0z0) is different from g(z0).

 

Thus, if the magnitude of M is neither less than or equal to that of L, it follows that it is greater than the magnitude of L. (See Crelles Journal vol. 84, p. 242). (Footnote: Georg Cantor, “Ein Beitrag zur Mannigfaltigkeitslehre”, Journal für die reine und angewandte Mathematik (Crelle’s Journal), Vol. 84, p.242-258, 1878.
Translator’s note, see an online English translation of that article at A Contribution to the Theory of Sets.)

 

I have already shown in the “Grundlagen einer allgemeinen Mannigfaltigkeitslehre” (Leipzig 1883; Math. Ann. Vol. 21) that the magnitudes have no maximum; it was also proven there that the set of all magnitudes, if we think of the latter according to the order of size, constitutes a well-ordered set, so that in fact there is a next larger set for every magnitude, and indeed for each one of a continuously increasing number of magnitudes there is also a next larger magnitude.

 

The “Magnitudes” represent the unique and essential generalization of the finite “Cardinal numbers”, they are nothing else than the actual-infinitely-large Cardinal numbers, and they have the same reality and certainty as those; it is only the logical relationships between them, and the “number theory” associated with them, that are somewhat different from those in the finite domain.

 

The further development of this field is the task of the future.

 


 

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.

 


 

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at Go Get Funding: Logic and Language where there are full details.

 

 

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Derogatory comments.
Long-winded comments.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.


Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.


Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

 

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2024
https://www.jamesrmeyer.com