Set of all sets

From Wikipedia, the free encyclopedia

In set theory as usually formulated, referring to the set of all sets typically leads to a paradox. The reason for this is the form of Zermelo's axiom of separation: for any formula \varphi(x) and set A, the set \{x \in A \mid \varphi(x)\} which contains exactly those elements x of A that satisfy \varphi exists. If the universal set V existed, then we could recover Russell's paradox by considering \{x \in V\mid x\not\in x\}. More generally, for any set A we can prove that \{x \in A\mid x\not\in x\} is not an element of A.

A second issue is that the power set of the set of all sets would be a subset of the set of all sets, providing that both exist. This conflicts with Cantor's theorem that power set of any set (whether infinite or not) always has strictly higher cardinality than the set itself.

It is natural to want to speak of "all sets" in the usual set theory ZFC, particularly because most versions of this theory do allow us to use quantifiers over all sets (not just quantifiers restricted to particular sets). This is handled by allowing carefully circumscribed mention of V and similar large collections as proper classes. In theories with proper classes the statement V \in V is not true because proper classes cannot be elements.

There are set theories known to be consistent (if the usual set theory is consistent) in which the universal set V does exist (and V \in V is true). In these theories, Zermelo's axiom of separation does not hold in general, and the axiom of comprehension of naive set theory is restricted in a different way. Examples of such theories are the various versions of New Foundations which are known to be consistent and systems of positive set theory.

Contents

[edit] Universal set

More broadly, a universal set in set theory, is a set which contains all objects, including itself.[1] The most widely-studied set theory with a universal set is Willard Van Orman Quine’s New Foundations, but Alonzo Church and Arnold Oberschelp also published work on such set theories. Church speculated that his theory might be extended in a manner consistent with Quine’s,[2] but this is not possible for Oberschelp’s, since in it the singleton function is provably a set,[3] which leads immediately to paradox in New Foundations.[4]

Zermelo–Fraenkel set theory and related set theories, which are based on the idea of the cumulative hierarchy, do not allow for the existence of a universal set.

[edit] See also

[edit] References

  1. ^ Forster 1995 p. 1.
  2. ^ Church 1974 p. 308, but see also Forster 1995 p. 136 or 2001 p. 17.
  3. ^ Oberschelp 1973 p. 40.
  4. ^ Holmes 1998 p. 110.

[edit] Bibliography

  • Alonzo Church (1974). “Set Theory with a Universal Set,” Proceedings of the Tarski Symposium. Proceedings of Symposia in Pure Mathematics XXV, ed. L. Henkin, American Mathematical Society, pp. 297-308.
  • T. E. Forster (1995). Set Theory with a Universal Set: Exploring an Untyped Universe (Oxford Logic Guides 31). Oxford University Press. ISBN 0-19-851477-8. 
  • Arnold Oberschelp (1973). “Set Theory over Classes,” Dissertationes Mathematicae 106.
  • Willard Van Orman Quine (1937) “New Foundations for Mathematical Logic,” American Mathematical Monthly 44, pp. 70-80.
\lnot(p\land\lnot p)  This logic-related article is a stub. You can help by expanding it.