Editing Naive set theory (section)

== Paradoxes in early set theory ==
{{main|Paradox}}
The unrestricted formation principle of sets referred to as the [[Axiom schema of specification#Unrestricted comprehension|axiom schema of unrestricted comprehension]],

{{block indent|If {{math|''P''}} is a property, then there exists a set {{math|''Y'' {{=}} {''x'' : ''P''(''x'')}<nowiki/>}},{{sfn|Jech|2002|p=4}}}}

is the source of several early appearing paradoxes:
*{{math|{{var|Y}} {{=}} {{mset|{{var|x}} | {{var|x}} is an ordinal}}}} led, in the year 1897, to the [[Burali-Forti paradox]], the first published [[antinomy]].
*{{math|{{var|Y}} {{=}} {{mset|{{var|x}} | {{var|x}} is a cardinal}}}} produced [[Cantor's paradox]] in 1897.<ref name=Letter_to_Hilbert/>
*{{math|{{var|Y}} {{=}} {{mset|{{var|x}} | {{mset}} {{=}} {{mset}}}}}} yielded '''Cantor's second antinomy''' in the year 1899.<ref name=Letters_to_Dedekind/> Here the property {{mvar|P}} is true for all {{mvar|x}}, whatever {{mvar|x}} may be, so {{mvar|Y}} would be a [[universal set]], containing everything.
*{{math|{{var|Y}} {{=}} {{mset|{{var|x}} | {{var|x}} ∉ {{var|x}}}}}}, i.e. the set of all sets that do not contain themselves as elements, gave [[Russell's paradox]] in 1902.

If the axiom schema of unrestricted comprehension is weakened to the [[axiom schema of specification]] or '''axiom schema of separation''',

{{block indent|If {{mvar|P}} is a property, then for any set {{mvar|X}} there exists a set {{math|{{var|Y}} {{=}} {{mset|{{var|x}} ∈ {{var|X}} : {{var|P}}({{var|x}})}}}},{{sfn|Jech|2002|p=4}}}}

then all the above paradoxes disappear.{{sfn|Jech|2002|p=4}} There is a corollary. With the axiom schema of separation as an axiom of the theory, it follows, as a theorem of the theory:

{{block indent|The set of all sets does not exist.}}

Or, more spectacularly (Halmos' phrasing{{sfn|Halmos|1974|loc=Chapter 2}}): There is no [[Domain of discourse|universe]]. ''Proof'': Suppose that it exists and call it {{mvar|U}}. Now apply the axiom schema of separation with {{math|{{var|X}} {{=}} {{var|U}}}} and for {{math|{{var|P}}({{var|x}})}} use {{math|{{var|x}} ∉ {{var|x}}}}. This leads to Russell's paradox again. Hence {{mvar|U}} cannot exist in this theory.{{sfn|Jech|2002|p=4}}

Related to the above constructions is formation of the set

*{{math|{{var|Y}} {{=}} {{mset|{{var|x}} | ({{var|x}} ∈ {{var|x}}) → {{mset}} ≠ {{mset}}}}}},

where the statement following the implication certainly is false. It follows, from the definition of {{mvar|Y}}, using the usual inference rules (and some afterthought when reading the proof in the linked article below) both that {{math|{{var|Y}} ∈ {{var|Y}} → {{mset}} ≠ {{mset}}}} and {{math|{{var|Y}} ∈ {{var|Y}}}} holds, hence {{math|{{mset}} ≠ {{mset}}}}. This is [[Curry's paradox#Naive set theory|Curry's paradox]].

It is (perhaps surprisingly) not the possibility of {{math|{{var|x}} ∈ {{var|x}}}} that is problematic. It is again the axiom schema of unrestricted comprehension allowing {{math|({{var|x}} ∈ {{var|x}}) → {{mset}} ≠ {{mset}}}} for {{math|{{var|P}}({{var|x}})}}. With the axiom schema of specification instead of unrestricted comprehension, the conclusion {{math|{{var|Y}} ∈ {{var|Y}}}} does not hold and hence {{math|{{mset}} ≠ {{mset}}}} is not a logical consequence.

Nonetheless, the possibility of {{math|{{var|x}} ∈ {{var|x}}}} is often removed explicitly{{sfn|Halmos|1974|loc=See discussion around Russell's paradox}} or, e.g. in ZFC, implicitly,{{sfn|Jech|2002|loc=Section 1.6}} by demanding the [[axiom of regularity]] to hold.{{sfn|Jech|2002|loc=Section 1.6}} One consequence of it is

{{block indent|There is no set {{mvar|X}} for which {{math|{{mvar|X}} ∈ {{var|X}}}},}}

or, in other words, no set is an element of itself.{{sfn|Jech|2002|p=61}}

The axiom schema of separation is simply too weak (while unrestricted comprehension is a very strong axiom&mdash;too strong for set theory) to develop set theory with its usual operations and constructions outlined above.{{sfn|Jech|2002|p=4}} The axiom of regularity is of a restrictive nature as well. Therefore, one is led to the formulation of other axioms to guarantee the existence of enough sets to form a set theory. Some of these have been described informally above and many others are possible. Not all conceivable axioms can be combined freely into consistent theories. For example, the [[axiom of choice]] of ZFC is incompatible with the conceivable "every set of reals is [[Lebesgue measurable]]". The former implies the latter is false.