I can find many resources regarding Cantor's proof of the uncountability of the continuum. But was he the first to prove that $\mathfrak{c} = | \mathfrak{P} (\mathbf{N})|$? Which paper?


1 Answer 1


I believe the credit mainly goes to Bertrand Russell and Émile Borel.

José Ferreirós [2] writes (see below) that Bertrand Russell [4] (1903) was largely responsible for rephrasing Cantor's 1892 diagonalization result in terms of the collection of all subsets of a set, and then emphasizing the importance of this rephrasing. However, Russell was not the only person who was communicating Cantor's 1892 results in this manner. Émile Borel, in his influential 1898 book [1], includes Cantor's 1874 proof for the uncountability of any interval (pp. 14-15) and Cantor's 1892 diagonalization proof that given any set $E$ the set of all functions from $E$ into the two element set $\{0, \, 1\}$ has cardinality greater than the cardinality of $E$ (pp. 107-108), and Borel explicitly makes the connection to the cardinality of collections of subsets of a set (pp. 109-110, translated excerpt below). Also, in an 1898 conference Charles Sanders Peirce [3] (top of p. 159) said:

$\ldots$ this collection shall consist of all finite multitudes [= positive integers] together with all possible collections of those multitudes, together with all possible collections of collections of those multitudes, together with all possible collections of collections of collections of those multitudes, and so on ad infinitum.

[1] Émile Félix Édouard Justin Borel, Leçons sur la Théorie des Fonctions [Lessons on the Theory of Functions], Collection de Monographies sur la Théorie des Fonctions (Borel's Series) #1, Gauthier-Villars, 1898, x + 136 pages.

[2] José Ferreirós, Labyrinth of Thought. A History of Set Theory and Its Role in Modern Mathematics, Science Networks / Historical Studies #23, Birkhäuser Verlag, 1999, xxii + 440 pages.

[3] Charles Sanders Peirce, Lecture Three: The Logic of Relatives, pp. 146-164 in Reasoning and the Logic of Things. The Cambridge Conferences Lectures of 1898, edited by Kenneth Laine Ketner, Harvard University Press, 1992, xiv + 297 pages.

[4] Bertrand Arthur William Russell, The Principles of Mathematics. Volume I, Cambridge University Press, 1903, xxx + 534 pages. [Note: A second volume was never published.]

(from p. 306 of Ferreirós [2]) It has to be noted that it was Russell, not Cantor in his published work, who focused on the Cantor Theorem as a central result of great importance. He seems to have been the first mathematician who presented it as showing that the set of all subsets of $S$ has always a greater cardinality than $S$ itself [Russell (1903), §§ 346-347]. Thus, it was Russell who formulated it for the first time as a purely set-theoretical result. (In Cantor's version it showed that, given a set $S,$ a certain set of functions has greater cardinality, and functions were not taken to be sets.) In the process, Russell was the first to emphasize something like the Power Set Axiom. All of this was in itself an important contribution, for until then the theorem lay rather forgotten in the first annual report of the DMV and its significance had not been clearly grasped. Moreover, the Cantor Theorem led Russell to the discovery of his paradox. Thus Russell's early reformulations of previous work were important in the process of extensionalization of set theory, although he was never partisan of a purely extensional conception of classes (see Russell (1903), §§ 66-79), and he gradually became more and more a Fregean on this account.


(from pp. 109-110 of Borel [1], translated) It also seems difficult for us to introduce such functions for consideration and, in general, any class of functions that forms a set of power greater than that of the continuum, because one can use a function in calculus only if it is defined by means of countably many conditions. This is the case with continuous functions and also with functions that are discontinuous at only countably many values of the variable. Such functions can, in fact, be defined by means of countably many conditions and, if one wishes to be more precise, by means of countably many whole numbers $({ }^1)$ [footnote: These conditions are not arbitrary, by the way; we will return to this point in Note III.]

The same applies to sets of points. One can see that each function $f(x),$ equal to $0$ or $1$ for every value of the variable, partitions the reals into two classes, and therefore defines two sets of points: the set of points at which the function has the value $0$ and the set of points at which the function has the value $1.$ Thus, the set $F$ of all such functions is identical to the set of all possible sets (with the reals as elements). Therefore, the set $F$ has a power greater than that of the continuum, and hence its general element (that is, an arbitrary set of reals) cannot be defined except by means of a set of conditions that has the power of the continuum. This is what makes reasoning about arbitrary sets so difficult and sometimes impossible. This is also what often makes such reasoning pointless in the present state of science, since it does not seem as if a set defined by uncountably many conditions can be easily introduced into a train of reasoning. On the other hand, we have seen (p. 50) that the collection of perfect sets has the power of the continuum. It is easy to see that the same applies to the collection of sets we have called measurable; it is this aspect [means: being definable by countably many conditions] that allows us to reason with more facility about these particular classes of sets and to discover their properties.

In summary, there is the need to distinguish, both in the case of sets of points and in the case of discontinuous functions, two large classes: the sets and functions which cannot be defined by countably many conditions and those which can be so defined. It seems that only the latter class can be profitably investigated at present.

Note: Regarding Borel's claim "the same applies to the collection of sets we have called measurable", Borel is talking about the collection of Borel sets. Because Borel did not give a mathematically precise definition for his collection of (Borel) measurable sets, Borel's claim is something that he probably felt was intuitively evident. The claimed result is true, but because the construction process which Borel incompletely described (elsewhere) actually involves uncountably many steps (as shown by Lebesgue in 1905, who also gave a rigorous proof of the claim), the situation is not as intuitively evident as I suspect Borel may have thought it to be.

  • $\begingroup$ Thanks. What about more direct proofs that $ \mathfrak{c} = | \mathcal{P} (\mathbf{N}) |$, like the one on Wikipedia (considering binary sequences, and Dedekind cuts), or did this come much later in more modern textbooks? The papers you cited involve more general considerations about cardinalities of power sets. $\endgroup$ Commented Jul 15, 2017 at 6:08
  • 1
    $\begingroup$ @Maxis Jaisi: I think the big step was the consideration of subsets of a set as an object worthy of identification. Once this idea was explicitly singled out, the various proofs you're talking about were probably just "fill-in details" stuff that most any of the leading (and even many not so leading) mathematicians could have done. The place to look would be in the dozens of analysis texts that appeared in the first decade of the 1900s, such as those by Baire, Tannery, Goursat, Whittaker, André-Fouët, Humbert, Burkhardt, Dini, Hobson, Bromwich, Czuber, Pierpont, etc. $\endgroup$ Commented Jul 17, 2017 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.