Search code examples
mathparadoxset-theory

Russell's Paradox


Let X be the set of all sets that do not contain themselves. Is X a member of X?


Solution

  • In ZFC, either the axiom of foundation [as mentioned] or the axiom (scheme) of comprehension will prohibit this. The first, for obvious reasons; the second, since it basically says that for given z and first-order property P, you can construct { xz : P(x) }, but to generate the Russell set, you would need z = V (the class of all sets), which is not a set (i.e. cannot be generated from any of the given axioms).

    In New Foundations (NF), "xx" is not a stratified formula, and so again we cannot define the Russell set. Somewhat amusingly, however, V is a set in NF.

    In von Neumann--Bernays--Gödel set theory (NBG), the class R = { x : x is a set and xx } is definable. We then ask whether RR; if so, then also RR, giving a contradiction. Thus we must have RR. But there is no contradiction here, since for any given class A, AR implies either AA or A is a proper class. Since RR, we must simply have that R is a proper class.

    Of course, the class R = { x : xx }, without the restriction, is simply not definable in NBG.

    Also of note is that the above procedure is formally constructable as a proof in NBG, whereas in ZFC one has to resort to meta-reasoning.