THE PARADOXES OF SET THEORY
Phillip E. Johnson
Department of Mathematics
Charlotte, NC 28223-0001
Georg Cantor created and largely developed set theory in approximately the latter quarter of the nineteenth century. Hardly had his work been completed before paradoxes began to appear. The first of the modern paradoxes was published by the Italian mathematician Cesare Burali-Forti (Burali-Forti, 1897, pp. 157-164) in the same year in which Cantor's last set-theoretical paper was published, 1897. The Burali-Forti paradox was apparently discovered earlier by Cantor himself (Fraenkel, 1930, p. 261).
A paradox markedly similar to the Burali-Forti paradox is the Cantor paradox of 1899 (published posthumously in 1932) concerned with cardinal numbers (Fraenkel, 1930, p. 261). The Burali-Forti paradox was concerned with ordinal numbers. Since more readers are familiar with cardinal numbers than with ordinal numbers, the Cantor paradox will be stated. Consider the cardinal number of the set of all sets. Clearly this is the greatest possible cardinal number. But by a standard theorem of intuitive set theory, the set of all subsets of a set has a greater cardinal number then the set itself. Therefore, the cardinal number of the set of all subsets of the set of all sets is greater than the greatest possible cardinal number, an obvious contradiction.
Whereas the Burali-Forti and Cantor paradoxes involve results of set theory, Bertrand Russell discovered in 1902 a paradox based on just the concept of set itself. The result was also discovered independently by Ernst Zermelo (Fraenkel and Bar-Hillel, 1958, p. 6). The paradox comes about by considering the set of all sets which have the property of not being members of themselves. For example, the set of all men is not a man, whereas the set of all sets is a set.
Suppose the set of all sets which are members of themselves is denoted by M , and the set of all sets which are not members of themselves is denoted by N. Does N belong to M? If N is a member of itself, then N is a member of M and not of N, and N is not a member of itself. Contrariwise, if N is not a member of itself, then N is a member of N and not of M, and N is a member of itself. Since either case leads to a contradiction, a paradox is apparent.
There are many popularized forms of the Russell paradox appearing in the literature. One of the best known of these forms was given by Russell in 1919 (Eves and Newsom, 1958, p. 283). A certain village barber shaves everyone in the village who does not shave himself. The question is, does the barber shave himself? If he shaves himself, then he should not according to the given principle; if he does not shave himself, then he should according to the principle.
Quite a number of other paradoxes arose in the early years following Burali-Forti's result. Some of these modern paradoxes, falling more or less within the context of set theory, can be seen to be related to several ancient paradoxes of logic. For example the Cretan philosopher Epimenides (sixth century B.C.) is supposed to have made the statement, "Cretans are always liars." This statement, if true, makes the speaker a liar for telling the truth. Paul quoted the statement in Epistle to Titus 1, 12, as by a Cretian prophet. The Epimenides paradox, known also as "the liar," appears in stark form in the statement attributed to Eubulides (fourth century B.C.): "This statement I am now making is false." The quoted statement can neither be true nor false without entailing a contradiction. (Kleene, 1952, p.39)
Another of the semantical (as opposed to logical or mathematical paradoxes) is the Richard paradox of 1905, significant since it is a sort of caricature of Cantor's well-known diagonal method (Richard, 1905, pp. 541-543). A simplification of Richard's paradox is due to G. G. Berry in 1906. Consider the expression, "the least natural number not namable in fewer than twenty-two syllables." This expression names in twenty-one syllables a natural number which by definition cannot be named in fewer than twenty-two syllables (Kleene, 1952, p. 39). Various modifications exist.
K. Grelling and L. Nelson called attention in 1908 to a paradox which they regarded as only a variant of Russell's paradox. The Grelling paradox can be stated quite simply. Among English adjectives there are some which have the property that they denote, such as "short," "polysyllabic," and "English." Let adjectives which have this property be called autological and all others be called heterological. In the latter class would be such adjectives as "long," "monosyllabic," "blue," and "hot." Paradoxically, the adjective "heterological" is heterological if and only if it is autological. (Fraenkel and Bar-Hillel, 1958, p. 10)
One of the more interesting paradoxes appeared in 1924 and was due to two distinguished Polish mathematicians, S. Banach and A. Tarski. Banach's and Tarski's work extended the implications of a paradoxical theorem due to the German mathematician Felix Hausforff. A popularized version of the paradox follows (Kasner and Newman, 1940, pp. 201-207).
Imagine two spheres in three-dimensional space, one very large (like the sun, say) and the other very small (like a pea). Denote the large sphere by S and the small sphere by P. The entire solid spheres of both S and P are being referred to, not just the surfaces of the two spherical objects. The theorem of Banach and Tarski holds that the following operations can theoretically be carried out:
Divide S into a great many small parts. Each part is to be separate and distinct and the totality of the parts is to be finite in number. Designate these parts by s1, s2, s3, ... ,sn . Together these small parts will make up the entire sphere S. Similarly P may be divided into an equal number of mutually exclusive parts, p1, p2, p3, ... ,pn, which together make up P. The proposition goes on to say that if S and P have been cut up in a suitable manner, so that the little portion s1 of S is congruent to the little portion p1 of P, s2 congruent to p2, s3 congruent to p3, up to sn congruent to pn, this process will exhaust not only all the little portions of P, but all the tiny portions of S as well. In other words, S and P may both be divided into a finite number of disjoint parts so that every single part of one is congruent to a unique part of the other, and so that after each small portion of P has been matched with a small portion of S, no portion of S will be left over. The paradox here lies not in the simple one-to-one correspondence between the elements of the two sets, but in the fact that each element is matched with one which is completely congruent to it.
The paradoxes cited, and others, have been an important stimulus to the study of questions in the foundations of mathematics. Semantical paradoxes such as the barber paradox can be dispensed with by noting that the village barber just could not do what the principle says. But such an explanation does not apply to some of the other paradoxes; in terms of logic as it was known in the nineteenth century, such paradoxical results are inexplicable.
Considerable work has been done by various groups and individuals aimed at eliminating the paradoxes from set theory. Probably the single most important contribution toward this end has been the axiomatizing of set theory, notably the axiomatizations known as the Zermelo-Fraenkel and von Neumann-Bernays-Goedel theories. The paradoxes have contributed importantly in bringing about contributions to the foundations. Cantor's initial stimulus of set theory was valuable both in itself and as a means for generating further discussion and research into the whole area of the foundations of mathematics.
Notes on Sources
This paper on the paradoxes of set theory is a reprint of an article appearing in the fall 1997 issue of Centroid, a publication of the North Carolina Council of Teachers of Mathematics (Kathy Ivey, Editor, Mathematics Dept., Western Carolina University, Cullowhee, NC 28723). The article is adapted from the author's A History of Set Theory (Prindle Weber & Schmidt, Boston, 1972).
The first of the modern paradoxes may be found in Cesare Burali-forti's 1897 article, "Una questione sui numeri transfiniti," in Rendiconti del Circolo Mathemaico di Parermo II. Abraham Adolf Fraenkel's "Georg Cantor," published in 1930 in Jahresbericht der Deutschen mathematiker Vereinigung 39, contains evidence that Cantor himself was aware of the Burali-forti paradox and also gave a markedly similar paradox concerning cardinal rather than ordinal numbers. A. A. Fraenkel's and Yehoshua Bar-Hillel's Foundations of Set Theory (1958, Amsterdam: North-Holland Publishing Company) gives an account of the paradox known as the Russell paradox, also discovered by Ernst Zermelo. The famous popularization of the Russell paradox may be found in the very readable account in An Introduction to the Foundations and Fundamental Concepts of Mathematics by Howard Eves and Carroll V. Newsom (1958, New York: Rinehard & Company, Inc.). The Grelling paradox, regarded as a variant of the Russell paradox, is discussed in the Fraenkel and Bar-Hillel book mentioned above. Some of the logical paradoxes are given in Stephen Cole Kleene's Introduction to Metamathematics (1952, New York: D. Van Nostrand Company, Inc.). The semantical Richard paradox is found in Jules Richard's 1905 article, "Les principes des mathematiques et le probleme des ensembles," in Revue Generale des Sciences Pures et Appliquees 16. The last paradox discussed in the paper, the Banach-Tarski paradox, is found in a highly readable popularization in Mathematics and the Imagination, written by Edward Kasner and James Newman (1940, New York: Simon and Schuster).
Burali-Forti, Cesare (1897). Una questione sui numeri transfiniti. Rendiconti
Matematico di Parermo II.
Eves, Howard and Newsom, Carroll V. (1958). An Introduction to the Foundations and Fundamental Concepts of Mathematics. New York: Rinehart & Company, Inc.
Fraenkel, Abraham Adolf (1930). Georg Cantor. Jahresbericht der Deutschen Mathematiker Vereinigung, 39.
Fraenkel, A. A. and Bar-Hillel, Yehoshua (1958). Foundations of Set Theory. Amsterdam: North-Holland Publishing Company.
Kasner, Edward and Newman, James (1940). Mathematics and the Imagination. New York: Simon and Schuster.
Kleene, Stephen Cole (1952). Introduction to Metamathematics. New York: D. Van Nostrand Company, Inc.
Richard, Jules (1905). Les principes des mathematiques et le probleme des ensembles. Revue Generale des Sciences Pures et Appliques 16.
Return to Archives
Return to Mathematical Connections Main Page