Editing Naive Set Theory (book) (section)

== Relation to other axiom systems for set theory ==

Note that axioms 1.-9. are equivalent to the axiom system of ZFC-Foundation (that is [[ZFC]] without the Foundation axiom), since as noted above, Halmos' axiom (schema) of substitution is equivalent to the axiom schema of replacement, in the presence of the other axioms. 

Additionally, axioms 1.-8. are nearly exactly those of [[Zermelo set theory]] ZC; the only difference being that the set existence assumption is replaced in ZC by the existence of the empty set, and the existence of singletons is stated outright for ZC, rather than proved, as above. Additionally, the infinite set that is asserted to exist by the axiom of infinity is not the one that Zermelo originally postulated,<sup>[[#Notes|[a] ]]</sup> but Halmos' version is sometimes silently substituted for it in treatments of Zermelo set theory.

That the axiom (schema) of substitution is stated last and so late in the book is testament to how much elementary set theory—and indeed mathematics more generally—can be [[Axiom schema of replacement#Applications|done without it]]. As a very simple example of what is ''is'' needed for, the von Neumann ordinal <math>\omega+\omega</math> (that is, the second limit ordinal) cannot be proved to be a set using only axioms 1.-8., even though sets with well-orderings with this order type can be constructed from these axioms. For instance <math>\omega\times \{1\} \cup \omega\times \{2\}</math>, with an ordering placing all elements of the first copy of <math>\omega</math> less than the second. Working with von Neumann ordinals in place of generic well-orderings has technical advantages, not least the fact every well-ordering is order isomorphic to a ''unique'' von Neumann ordinal.

As noted above, the book omits the [[Axiom of Foundation]] (also known as the Axiom of Regularity).  Halmos repeatedly dances around the issue of whether or not a set can contain itself.
*p. 1: "a set may also be an element of some ''other'' set" (emphasis added)
*p. 3: "is <math>A\in A</math> ever true?  It is certainly not true of any reasonable set that anyone has ever seen."
*p. 6: "<math>B\in B</math> ... unlikely, but not obviously impossible"
But Halmos does let us prove that there are certain sets that cannot contain themselves.
*p. 44: Halmos lets us prove that <math>\omega\not\in \omega</math>.  For if <math>\omega\in \omega</math>, then <math>\omega \setminus \{\omega\}</math> would still be a successor set, because <math>\omega\not= \emptyset</math> and <math>\omega</math> is not the successor of any natural number.  But <math>\omega</math> is not a subset of <math>\omega \setminus\{\omega\}</math>, contradicting the definition of <math>\omega</math> as a subset of every successor set.
*p. 47: Halmos proves the lemma that "no natural number is a subset of any of its elements."  This lets us prove that no natural number can contain itself.  For if <math>n \in n</math>, where <math>n</math> is a natural number, then <math>n \subset n\in n</math>, which contradicts the lemma.
*p. 75: "An ''ordinal number'' is defined as a well ordered set <math>\alpha</math> such that <math>s(\xi) = \xi</math> for all <math>\xi</math> in <math>\alpha</math>; here <math>s(\xi)</math> is, as before, the initial segment <math>\{\eta\in \alpha:</math> <math>\eta < \xi</math>}."  The well ordering is defined as follows: if <math>\xi</math> and <math>\eta</math> are elements of an ordinal number <math>\alpha</math>, then <math>\xi< \eta</math> means <math>\xi \in \eta</math> (pp. 75-76).  By his choice of the symbol <math>< </math> instead of <math>\leq </math>, Halmos implies that the well ordering <math>< </math> is strict (pp. 55-56).  This definition of <math>< </math> makes it impossible to have <math>\xi \in \xi</math>, where <math>\xi</math> is an element of an ordinal number.  That's because <math>\xi\in \xi</math> means <math>\xi < \xi</math>, which implies <math>\xi \not=\xi</math> (because < is strict), which is impossible.
*p. 75: the above definition of an ordinal number also makes it impossible to have <math>\alpha\in \alpha</math>, where <math>\alpha</math> is an ordinal number.  That's because <math>\alpha\in \alpha</math> implies <math>\alpha= s(\alpha)</math>.  This gives us <math>\alpha\in \alpha= s(\alpha) = \{\eta\in \alpha:\eta < \alpha\}</math>, which implies <math>\alpha < \alpha</math>, which implies <math>\alpha\not= \alpha</math> (because <math>< </math> is strict), which is impossible.