Stony Brook University     MAT 336     History of Mathematics

On an elementary question in set theory

Georg Cantor

[Jahresbericht der Deutsch. Math. Vereing. 1 75-78 (1890-91)]

In the article entitled: On a property of the set of all real algebraic numbers (Journ. Math. 77 258) there was presented for the first time a proof that there are infinite sets which cannot be put into one-one correspondence with the set of all finite whole numbers $1, 2, 3, \dots , \nu , \dots$ or, as I put it, do not have the cardinality of the number sequence $1, 2, 3, \dots , \nu , \dots$. From what is proved in §2 there follows in fact something further, that for example the set of all real numbers in an arbitrary interval $(\alpha\dots\beta)$ may not be represented as a sequence

$$\omega_1, \omega_2, \dots, \omega_{\nu}, \dots .$$

Each of these propositions can be given a much more simple proof, which is independent of considerations about the irrational numbers.

Specifically, let $m$ and $w$ be two different symbols, and let us consider the set $M$ of elements

$$E = (x_1, x_2, \dots, x_{\nu}, \dots ),$$

which depend on infinitely many coordinates $x_1, x_2, \dots, x_{\nu}, \dots$, where each of these coordinates is either $m$ or $w$. Let $M$ be the set of all such elements $E$.

Among the elemets of $M$ we find for example the following three:

$$E^I = (m, m, m, m, \dots),$$

$$E^{II} = (w, w, w, w, \dots),$$

$$E^{III} = (m, w, m, w, \dots).$$

I now state that such a set $M$ does not have the cardinality of the sequence $1, 2, 3, \dots , \nu , \dots$.

This is a consequence of the following proposition:

``Let $E_1, E_2, \dots, E_{\nu}, \dots$ be any infinite sequence of elements of the set $M$; then there is an element $E_0$ of $M$ which does not coincide with any $E_{\nu}$.''

For the proof let

$$E_1 = (a_{11}, a_{12}, \dots , a_{1\nu}, \dots),$$

$$E_2 = (a_{21}, a_{22}, \dots , a_{2\nu}, \dots),$$

$$\dots$$

$$E_{\mu} = (a_{\mu 1}, a_{\mu 2}, \dots , a_{\mu\nu}, \dots),$$

$$\dots$$

Here each $a_{\mu\nu}$ is set to be $m$ or $w$. We will now define a sequence $b_1, b_2, \dots, b_{\nu}, \dots$ in such a way that $b_{\nu}$ is also only $m$ or $w$ and is different from $a_{\nu\nu}$.

So if $a_{\nu\nu} = m$ then $b_{\nu} = w$, and if $a_{\nu\nu} = w$ then $b_{\nu} = m$.

Let us now consider the element

$$E_0 = (b_1, b_2, b_3, \dots )$$

of $M$; we immediately see that the equation

$$E_0 = E_{\mu}$$

cannot be satisfied for any integer value of $\mu$, because for that particular $\mu$ and for all integer values of $\nu$ we would have

$$b_{\nu} = a_{\mu,\nu},$$

and in particular

$$b_{\mu} = a_{\mu,\mu},$$

which is excluded by the definition of $b_{\mu}$. From this proposition it follws immediately that the set of all the elements of $M$ cannot be placed in a sequence: $E_1, E_2, \dots, E_{\nu}, \dots$, since we would be faced with the contradiction that the object $E_0$ would be both an element of $M$ and not an element of $M$.

This proof is remarkable not only because of its great simplicity, but also because the principle it contains leads immediately to the general proposition that the cardinalities of well defined sets have no maximum; or, equivalently, that for any given set $L$ we can find another set $M$ of larger cardinality than $L$.

For example, let $L$ be an interval, say the set of all real numbers which are $\ge 0$ and $\le 1$.

Then let $M$ be the set of all functions $f(x)$ which only take on the two values $0$ and $1$, while $x$ runs through all the real values $\ge 0$ and $\le 1$.

That $M$ does not have a smaller cardinality than $L$ follows from the fact that $M$ has subsets which are of the same cardinality as $L$, for example the subset consisting of the functions of $x$ which give $1$ just for a single value $x_0$, and $0$ for all other values of $x$.

But $M$ cannot have the same cardinality as $L$, because if it did then the elements of $M$ could be put in one-one correspondence with the variable $z$, and $M$ could be thought of as a function of the two variables $x$ and $z$

$$\varphi(x,z)$$

so that each choice of $z$ would give the element $f(x) = \varphi(x,z)$ of $M$ and vice-versa each element $f(x)$ of $M$ would correspond to $\varphi(x,z)$ for some choice of $z$. But this leads to a contradiction. Because then let us consider the function $g(x)$ which only takes on the values $0$ and $1$, and which for each $x$ is different from $\varphi(x,x)$; then on the one hand $g(x)$ is an element of $M$, and on the other hand $g(x)$ cannot be $\varphi(x,z)$ for any choice $z = z_0$, because $\varphi(z_0,z_0)$ is different from $g(z_0)$.

Since the cardinality of $M$ is neither smaller than or the same as that of $L$, it must be larger than the cardinality of $L$. (see Crelles Journal 84 242).

I have already, in ``Foundations of a general theory of sets'' (Leipzig 1883; Math. Ann. Vol. 21) shown, by completely different techniques, that the cardinalities have no maximum; there it is also proved that the set of all cardinalities, when we think of them as ordered by their size, forms a ``well-ordered set'' so that in nature for every cardinality there is a next larger, but also every infinite set of cardinalities is followed by a next larger.

The ``cardinalities'' represent the single and remarkable generalization of the finite ``cardinal numbers;'' they are nothing else but the actual-infinitely-large cardinal numbers, and they inherit the same reality and definiteness as those do; only the relations between them form a different ``number theory'' from the finite one.

The further completion of this field is a job for the future.

Translator's note:

• This is a rough translation. I have tried to keep the flavor of the original, but I used ``set'' for Cantor's Mannigfaltigkeit (``manifold''), Gesamtheit (``totality''), Inbegriff (``clutch'') and Menge, now standard for ``set,'' which appears twice, in the last two paragraphs. It is interesting that the notations $(a,b)$ and $[a,b]$ for open and closed intervals were not available to Cantor, nor was the possibility of writing $f$ without $(x)$.
• Zermelo, the editor of the collected works where this article was located, remarks: That the set of all cardinalities is a well-ordered system (even if not a ``set'') is in no way ``proven'' in the referenced work; Cantor does not yet have the proof that every set can be well-ordered and therefore that every cardinality is an Aleph.

Anthony Phillips