set-theoretic paradoxes a collection of paradoxes that reveal difficulties in certain central notions of set theory. The best-known of these are Russell’s paradox, Burali-Forti’s paradox, and Cantor’s paradox. Russell’s paradox, discovered in 1901 by Bertrand Russell, is the simplest (and so most problematic) of the set-theoretic paradoxes. Using it, we can derive a contradiction directly from Cantor’s unrestricted comprehension schema. This schema asserts that for any formula P(x) containing x as a free variable, there is a set {x _ P(x)} whose members are exactly those objects that satisfy P(x). To derive the contradiction, take P(x) to be the formula x 1 x, and let z be the set {x _ x 2 x} whose existence is guaranteed by the comprehension schema. Thus z is the set whose members are exactly those objects that are not members of themselves. We now ask whether z is, itself, a member of z. If the answer is yes, then we can conclude that z must satisfy the criterion of membership in z, i.e., z must not be a member of z. But if the answer is no, then since z is not a member of itself, it satisfies the criterion for membership in z, and so z is a member of z. All modern axiomatizations of set theory avoid Russell’s paradox by restricting the principles that assert the existence of sets. The simplest restriction replaces unrestricted comprehension with the separation schema. Separation asserts that, given any set A and formula P(x), there is a set {x 1 A _ P(x)}, whose members are exactly those members of A that satisfy P(x). If we now take P(x) to be the formula x 2 x, then separation guarantees the existence of a set zA % {x 1 A _ x 2 x}. We can then use Russell’s reasoning to prove the result that zA cannot be a member of the original set A. (If it were a member of A, then we could prove that it is a member of itself if and only if it is not a member of itself. Hence it is not a member of A.) But this result is not problematic, and so the paradox is avoided. The Burali-Forte paradox and Cantor’s paradox are sometimes known as paradoxes of size, since they show that some collections are too large to be considered sets. The Burali-Forte paradox, discovered by Cesare Burali-Forte, is concerned with the set of all ordinal numbers. In Cantor’s set theory, an ordinal number can be assigned to any well-ordered set. (A set is wellordered if every subset of the set has a least element.) But Cantor’s set theory also guarantees the existence of the set of all ordinals, again due to the unrestricted comprehension schema. This set of ordinals is well-ordered, and so can be associated with an ordinal number. But it can be shown that the associated ordinal is greater than any ordinal in the set, hence greater than any ordinal number.
Cantor’s paradox involves the cardinality of the set of all sets. Cardinality is another notion of size used in set theory: a set A is said to have greater cardinality than a set B if and only if B can be mapped one-to-one onto a subset of A but A cannot be so mapped onto B or any of its subsets. One of Cantor’s fundamental results was that the set of all subsets of a set A (known as the power set of A) has greater cardinality than the set A. Applying this result to the set V of all sets, we can conclude that the power set of V has greater cardinality than V. But every set in the power set of V is also in V (since V contains all sets), and so the power set of V cannot have greater cardinality than V. We thus have a contradiction.
Like Russell’s paradox, both of these paradoxes result from the unrestricted comprehension schema, and are avoided by replacing it with weaker set-existence principles. Various principles stronger than the separation schema are needed to get a reasonable set theory, and many alternative axiomatizations have been proposed. But the lesson of these paradoxes is that no setexistence principle can entail the existence of the Russell set, the set of all ordinals, or the set of all sets, on pain of contradiction.
See also SEMANTIC PARADOXES , SET THE- OR. J.Et.