From Wikipedia, the free encyclopedia

This article contains a discussion of paradoxes of set theory.

Contents 1 Basics 2 Paradoxes of enumeration 2.1 Je le vois, mais je ne crois pas 3 Early paradoxes: the set of all sets 3.1 The restless barber 3.2 Is "non-selfdescribing" non-selfdescribing? 4 Paradoxes by change of language 4.1 König's paradox 4.2 Richard's paradox 4.3 Uncountably many real numbers 4.4 Berry's paradox 5 Paradox of Löwenheim and Skolem 6 Paradox of Banach and Tarski 7 Paradoxes of the Tristram Shandy type 7.1 The diary of Tristram Shandy 7.2 The Ross-Littlewood paradox 8 Paradoxes of order 9 Paradox of the binary tree 10 See also 11 Notes 12 Literature and links

The set theory founded by Georg Cantor is based upon the assumption of the actual (complete) existence of infinite sets. As this assumption cannot be proved from first principles it has been introduced into axiomatic set theory by the axiom of infinity. The smallest infinite set is the set of all natural numbers N. Every infinite set which can be enumerated by natural numbers is the same size as N, and is said to be countable. Examples of infinite but countable sets are the natural numbers, the even numbers, the prime numbers, and also all the rational numbers, i.e., the fractions. These sets have in common the cardinal number |N| = (pronounced aleph-nought), which is a number greater than every natural number.

Besides the cardinality, which describes the number of elements in a set, the order of elements within the set is also a subject of set theory. The axiom of choice guarantees that every set can be well-ordered: Every subset which contains at least one element has a first element with respect to the order. The order of a set is described by an ordinal number which does not belong to the set. For instance, 3 is the ordinal number of the set {0, 1, 2} = 3; and ω is the ordinal number of the set of all natural numbers. Neglecting the order, we are left with the cardinal number |N| = |ω| = .

By forming all combinations of the elements of a set S, we obtain the power set P(S). Georg Cantor proved that the power set is always larger than the set, i.e., |P(S)| > |S|. A special case of Cantor's theorem proves that the set of all real numbers R cannot be enumerated by natural numbers. R is uncountable: |R| > |N|.

Even before set theory was introduced the notion of cardinality had become controversial. It had been discussed by Galileo Galilei and Bernard Bolzano, among others. Are there as many natural numbers as squares of natural numbers when measured by the method of enumeration?

• The answer is yes because every natural number can be squared.
• The answer is no because every square is a natural number but there are natural numbers, like 2, which are not squares of natural numbers.

Georg Cantor explained this by the difference between "reality" and "number". Both sets have the same cardinality, but one has more "reality" than the other.

"I see it but I can't believe it", Cantor wrote to Richard Dedekind, after proving that all the points of a square can be enumerated – not by the natural numbers, but in an extended sense by the points on one side of the square. By building on Cantor's idea in a natural way we see that the whole universe contains no more points than a grain of dust.

In 1897 the Italian mathematician Cesare Burali-Forti discovered that there is no set containing all ordinal numbers. As every ordinal number is defined by a set of smaller ordinal numbers, the well-ordered set of all ordinal numbers should define an ordinal number Ω which does not belong to the set. On the other hand, Ω must belong to the set of all ordinal numbers. Therefore, the set of all ordinal numbers cannot exist.

Neither can the set U of all unordered sets exist. It would contain its power set P(U); so, according to Cantor's theorem, U would have greater cardinal number than U.

By the end of the 19th century Cantor was aware of the non-existence of the set of all cardinal numbers and the set of all ordinal numbers. In letters to David Hilbert and Richard Dedekind he wrote about inconsistent sets, the elements of which cannot be thought of as being all together, and he used this result to prove that every consistent set has a cardinal number.

After all this, the version of the "set of all sets" paradox conceived by Bertrand Russell in 1903 led to a serious crisis in set theory. Russell recognized that the statement x = x is true fo every set, and thus the set of all sets is defined by {x | x = x}. In 1906 he constructed several paradox sets, the most famous of which is the set of all sets which do not contain themselves. Russell himself explained this abstract idea by means of some very concrete pictures. The barber who shaves all men who don't shave themselves has to shave himself only if he does not shave himself. A catalogue which records all catalogues which do not record themselves must record itself if and only if it does not record itself. ^[1]

A similar structure can be observed in the paradox by Kurt Grelling and Leonard Nelson (1908). Words like "short" or "old" describe themselves, because "short" is a short word and "old" is an old word. These words are called self-describing. Words like "long" and "new" do not describe themselves, because "long" is a short word and "new" is an old word. So the set of all adjectives is split into two subsets, the self-describing adjectives and the non-selfdescribing adjectives . The adjective "non-selfdescribing", however, does not belong to either set, because, if it's non-selfdescribing, then it is self-describing, and if it's self-describing then it is non-selfdescribing.^[2]

In 1905, the Hungarian mathematician Julius König published a paradox based on the fact that there are only countably many finite definitions. If we imagine the real numbers as a well-ordered set, those real numbers which cannot be finitely defined form a subset of that well-ordered set which certainly contains real numbers. Hence in this well-order there should be a first not finitely definable real number, following after all finitely definable real numbers. This is impossible, because this real number has just been finitely defined by the last sentence. The assumption that the real numbers can be well-ordered leads to a contradiction.

In the same year the French mathematician Jules Richard used a variant of Cantor's diagonal method to define a non-definable number. Consider the set A of all finite agglomerations of words. The set E of all finite definitions of real numbers is a subset of A. As A is countable, so is E. Let p be the nth decimal of the nth real number defined by the set E; we form a number N having zero for the integral part and p + 1 for the nth decimal if p is not equal either to 8 or 9, and unity if p is equal to 8 or 9. This number N is not defined by the set E because it differs from any finitely defined real number, namely from the nth number by the nth digit. But N has been defined by a finite number of words in this paragraph. It should therefore be in the set E. That is a contradiction.

Cantor's diagonal proof is the most famous proof of the existence of uncountably many real numbers. The diagonal number, as a finitely definable number belongs to a countable set of real numbers. Therefore, Cantor's proof proves the existence of uncountably many real numbers by producing a real number belonging to a countable set.

A related paradox conceived by G.G. Berry was reported in the Principia Mathematica. It uses the least integer not nameable in fewer than nineteen syllables; in English, this is 111,777. But "the least integer not nameable in fewer than nineteen syllables" is itself a name consisting of eighteen syllables; hence the least integer not nameable in fewer than nineteen syllables can be named in eighteen syllables, which is a contradiction.^[3]

Based upon work of the German mathematician Leopold Löwenheim (1915) the Norwegian logician Thoralf Skolem showed in 1922 that every consistent theory of first order predicate calculus, like set theory, has an at most countable model. The most important theorem of set theory proves that there are uncountable sets.^[4]

In 1924 the Polish mathematicians Stefan Banach and Alfred Tarski used the axiom of choice to prove that a solid sphere can be dissected into a few (at least six) parts which can be reunited to form two solid spheres, each of which is identical with the original sphere. In this way an arbitrarily large volume can be created. The actual construction, however, is not possible. An earlier version of this paradox had been described by the German mathematician Felix Hausdorff. ^[5]

Every non-empty finite set of positive even numbers contains numbers surpassing the cardinal number of the set. The set of smallest possible positive even numbers with n elements, namely {2, 4, 6, ..., 2n} has the cardinal number |{2, 4, 6, ..., 2n}| = n. At least half of all numbers are larger than n. The set of all positive even numbers is the union of all finite sets. Nevertheless the cardinal number is |{2, 4, 6, ...}| = |N| larger than any number of the set. Similar arguing is valid for the set of all prime numbers or the set of all natural numbers divisible by 10¹⁰⁰.

Tristram Shandy, the hero of a novel by Laurence Sterne, writes his autobiography so conscientiously that it takes him one year to lay down the events of one day. If he is mortal he can never terminate; but if he lived forever then no part of his diary would remain unwritten, for to each day of his life a year devoted to that day's description would correspond.

An increased version of this type of paradox shifts the infinitely remote finish to a finite time. Fill a huge reservoir with balls enumerated by numbers 1 to 10 and take off ball number 1. Then add the balls enumerated by numbers 11 to 20 and take off number 2. Continue to add balls enumerated by numbers 10n - 9 to 10n and to remove ball number n for all natural numbers n = 3, 4, 5, .... Let the first transaction last half an hour, let the second transaction last quarter an hour, and so on, such that all transactions are finished after one hour. Obviously the set of balls in the reservoir increases without bound. Nevertheless, after one hour the reservoir is empty because for every ball the time of removal is known.

The paradox is further increased by the significance of the removal sequence. If the balls are not removed in the sequence 1, 2, 3, ... but in the sequence 1, 11, 21, ... after one hour infinitely many balls populate the reservoir, although the same amount of material as before has been moved. [1]

In 1904 Ernst Zermelo proved by means of the axiom of choice (which was introduced for this reason) that every set can be well-ordered. In 1963 Paul J. Cohen showed that such a well-ordering cannot really be constructed for the set of real numbers.

In the natural order by size the irrational numbers fill the gaps between the rational numbers. There are no two irrational numbers without a rational between them, and there are no two rational numbers without an irrational between them. The set of rational numbers is countable, the set of irrational numbers is uncountable. Hence the set of the gaps in the rational numbers has a greater cardinal than the set of rational numbers itself.

A binary tree consists of nodes which are connected by edges. A continuous sequence of nodes guided by edges from the root node to a node at the last level of the tree is called a path. So each path is a sequence of bits representing a number. The figure shows a tree with two levels, the paths of which represent the numbers 0.00, 0.01, 0.10, and 0.11. Every finite binary tree with n > 0 levels contains less paths than nodes. Up to level n there are 2ⁿ paths and 2ⁿ⁺¹ - 1 nodes.

The union of all finite trees is identical with the infinite binary tree - with respect to the countable set of nodes. The infinite binary tree contains all infinite sequences of binary numerals and, therefore, represents all real numbers of the interval between 0 and 1. The set of nodes of any level is countable. This implies that any possible cross section of the infinite tree contains at most countably many paths while, according to Cantor's theorem, the infinite binary tree contains more paths than nodes and more paths than all finite trees together.

As each node generates only one more separated path, there must be more separated paths than generators of separated paths

• Proof of impossibility
• Balls and vase

1. ^ See Russell's paradox, and also the barber's paradox.
2. ^ See Grelling-Nelson paradox.
3. ^ See the article about Berry's paradox.
4. ^ See the associated article Skolem's paradox.
5. ^ See Banach–Tarski paradox and Hausdorff paradox.

• G. Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, E. Zermelo (Ed.), Olms, Hildesheim 1966.
• H. Meschkowski, W. Nilson: Georg Cantor - Briefe, Springer, Berlin 1991.
• A. Fraenkel: Einleitung in die Mengenlehre, Springer, Berlin 1923.
• A. A. Fraenkel, A. Levy: Abstract Set Theory, North Holland, Amsterdam 1976.
• F. Hausdorff: Grundzüge der Mengenlehre, Chelsea, New York 1965.
• B. Russell: The principles of mathematics I, Cambridge 1903.
• B. Russell: On some difficulties in the theory of transfinite numbers and order types, Proc. London Math. Soc. (2) 4 (1906) 29-53.
• P. J. Cohen: Set Theory and the Continuum Hypothesis, Benjamin, New York 1966.
• W. Mückenheim: Die Mathematik des Unendlichen, Shaker, Aachen 2006.
• S. Wagon: The Banach-Tarski-Paradox, Cambridge University Press, Cambridge 1985.
• A. N. Whitehead, B. Russell: Principia Mathematica I, Cambridge Univ. Press, Cambridge 1910, p. 64. [2]
• E. Zermelo: Neuer Beweis für die Möglichkeit einer Wohlordnung, Math. Ann. 65 (1908) p. 107-128. *[3]
• Paradoxe de Richard (in French)
• Paradoxe de Berry (in French)
• Richards Paradox