View source for Naive Set Theory (book)

{{Short description|1960 mathematics textbook by Paul Halmos}}{{Infobox book
| image             = NaiveSetTheory.jpg
| author            = [[Paul Halmos]]
| pub_date          = 1960
| caption           = First edition
}}

{{Italic title}}
:''See also [[Naive set theory]] for the mathematical topic.''
'''''Naive Set Theory''''' is a [[mathematics]] textbook by [[Paul Halmos]] providing an undergraduate introduction to [[set theory]].<ref>Review of ''Naive Set Theory'' by H. Mirkil (April 1961), ''[[American Mathematical Monthly]]'' 68 (4): 392, {{doi|10.2307/2311615}}.</ref> Originally published by ''Van Nostrand'' in 1960,<ref name="Rieger"/> it was reprinted in the [[Springer-Verlag]] [[Undergraduate Texts in Mathematics]] series in 1974.<ref>{{cite book | last1 = Halmos | first1 = Paul | title=Naive set theory|year=1974 | series=Undergraduate Texts in Mathematics | publisher=Springer-Verlag |isbn = 978-0-387-90092-6 | doi=10.1007/978-1-4757-1645-0 | mr=0453532}}</ref>

While the title states that the set theory presented is 'naive', which is usually taken to mean without formal [[axiom]]s, the book does introduce a system of axioms equivalent to that of [[Zermelo–Fraenkel set theory|ZFC set theory]] except the [[Axiom of foundation]].  It also gives correct and rigorous definitions for many basic concepts.<ref name="Rieger">Review of ''Naive Set Theory'', L. Rieger, {{MR|0114756}}.</ref><ref>Review of ''Naive Set Theory'', Alfons Borgers (July 1969), ''[[Journal of Symbolic Logic]]'' 34 (2): 308, {{doi|10.2307/2271138}}.</ref>   Where it differs from a "true" [[axiomatic set theory]] book is its character: there are no discussions of axiomatic minutiae, and there is next to nothing about advanced topics such as [[large cardinal]]s or [[forcing_(mathematics)|forcing]]. Instead, it tries to be intelligible to someone who has never thought about set theory before.

Halmos later stated that it was the fastest book he wrote, taking about six months, and that the book "wrote itself".<ref>{{citation | title=Paul Halmos: celebrating 50 years of mathematics | editor1-first=John H.|editor1-last=Ewing | editor2-first=Frederick W.|editor2-last=Gehring | publisher=[[Springer-Verlag]] | year=1991 | isbn=0-387-97509-8 |at=Interview of Halmos with Donald J. Albers, p.&nbsp;16|url=https://books.google.com/books?id=Xnv5fXu1vFoC&pg=PA16}}.</ref>

==Axioms used in the book==

The statements of the axioms given below are as they appear in the book, with section references, and with explanatory commentary on each one. The "principal primitive (undefined) concept of ''belonging''" (that is, [[Element (mathematics)#Notation and terminology|set membership]]) is the starting point, where "<math>x</math> belongs to <math>A</math>" is written in the usual notation as <math>x\in A</math>. Here <math>x</math> and <math>A</math> are both sets, with the notational distinction of upper/lower case a purely stylistic choice. The axioms govern the properties of this relation between sets.

1. '''[[Axiom of extensionality|Axiom of Extension]]''' (Section 1): two sets are equal if and only if they have the same [[Element (mathematics)|elements]].

This guarantees that the membership and (logical) [[First-order logic#Equality and its axioms|equality]] relations interact appropriately.

2. '''[[Axiom schema of specification|Axiom of Specification]]''' (Section 2): To every set <math>A</math> and every condition <math>S(x)</math> there corresponds a set <math>B</math> whose elements are precisely those elements of <math>A</math> for which <math>S(x)</math> holds.

This is more properly an [[axiom schema]] (that is, each condition <math>S(x)</math> gives rise to an axiom). "Condition" here means a "sentence" in which the variable <math>x</math> (ranging over all sets) is a [[Free variables and bound variables|free variable]]. "Sentences" are defined as being built up from smaller sentences using [[First-order logic|first order logical]] operations ([[Logical conjunction|and]], [[Logical disjunction|or]], [[Negation|not]]), including [[Quantifier (logic)|quantifiers]] ("[[Existential quantification|there exists]]", "[[Universal quantification|for all]]"), and with [[atomic formula|atomic]] (i.e. basic starting) sentences <math>x\in A</math> and <math>A=B</math>.

This schema is used in 4.-7. below to cut down the set that is stated to exist to the set containing precisely the intended elements, rather than some larger set with extraneous elements. For example, the  axiom of pairing applied to the sets <math>A</math> and <math>B</math> only guarantees there is ''some'' set <math>X</math> such that <math>A\in X</math> and <math>B\in X</math>. Specification can be used to then construct the set <math>\{A,B\}</math> with ''just'' those elements.

3. '''Set existence''' (Section 3): There exists a set.

Not specified as an named axiom, but instead stated to be "officially assumed". This assumption is not necessary once the axiom of infinity is adopted later, which also specifies the existence of a set (with a certain property). The existence of any set at all is used to show the [[empty set]] exists using the axiom of specification.

4. '''[[Axiom of pairing]]''' (Section 3): For any two sets there exists a set that they both belong to.

This is used to show that the [[Singleton (mathematics)|singleton]] <math>\{A\}</math> containing a given set <math>A</math> exists.

5. '''[[Axiom of union|Axiom of unions]]''' (Section 4): For every collection of sets there exists a set that contains all the elements that belong to at least one set of the given collection.

In Section 1 Halmos writes that "to avoid terminological monotony, we shall sometimes say ''collection'' instead of set." Hence this axiom is equivalent to the usual form of the axiom of unions (given the axiom of specification, as noted above).

From the axioms so far Halmos gives a construction of [[Intersection (set theory)|intersections of sets]], and the usual [[Algebra of sets|Boolean operations on sets]] are described and their properties proved.

6. '''[[Axiom of power set|Axiom of powers]]''' (Section 5): For each set there exists a collection of sets that contains among its elements all the subsets of the given set.

Again (noting that "collection" means "set") using the axiom (schema) of specification we can cut down to get the [[power set]] <math>P(A)</math> of a set <math>A</math>, whose elements are precisely the subsets of <math>A</math>. The axioms so far are used to construct the [[cartesian product]] of sets.

7. '''[[Axiom of infinity]]''' (Section 11): There exists a set containing 0 and containing the successor of each of its elements.

The set <math>0 := \emptyset</math>. The ''successor'' of a set <math>x</math> is defined to be the set <math>x^+:=x \cup \{x\}</math>. For example: <math>\{a,b\}^+ = \{a,b,\{a,b\}\}</math>. This axiom ensures the existence of a set containing <math>0</math> and hence <math>\{0\}</math>, and hence <math>\{0,\{0\}\}</math> and so on. This implies that there is a set containing all the elements of the first infinite [[Ordinal number#Von Neumann definition of ordinals|von Neumann ordinal]] <math>\omega</math>. And another application of the axiom (schema) of specification means <math>\omega</math> itself is a set.

8. '''[[Axiom of choice]]''' (Section 15): The Cartesian product of a non-empty family of non-empty sets is non-empty.

This is one of many [[axiom of choice#Equivalents|equivalents to the axiom of choice]]. Note here that "family" is defined to be a function <math>f\colon I\to X</math>, with the intuitive idea that the sets of the family are the sets <math>f(i)</math> for <math>i</math> ranging over the set <math>I</math>, and in usual notation this axiom says that there is at least one element in <math>\prod_{i\in I} f(i)</math>, as long as <math>f(i)\neq \emptyset</math> for all <math>i\in I \neq \emptyset</math>.

9. '''Axiom of substitution''' (Section 19): If <math>S(a,b)</math> is a sentence such that for each <math>a</math> in a set <math>A</math> the set <math>\{b : S(a,b)\}</math> can be formed, then there exists a function <math>F</math> with domain <math>A</math> such that <math>F(a) = \{b : S(a,b)\}</math> for each <math>a</math> in <math>A</math>.

A function <math>F\colon A\to X</math> is defined to be a [[Relation (mathematics)#Properties of relations|functional relation]] (i.e. a certain subset of <math>A\times X</math>), not as a certain type of set of [[Ordered pair#Kuratowski's definition|ordered pairs]], as in ZFC, for instance.

This 'axiom' is essentially the [[Axiom_schema of replacement#Collection|axiom schema of collection]], which, given the other axioms, is equivalent to the [[axiom schema of replacement]]. It is the collection schema rather than replacement, because 1) <math>S(a,b)</math> is a [[Class (set theory)#Classes in formal set theories|class]] ''relation'' instead of a class function and 2) the function <math>F</math> is not specified to have [[codomain]] precisely the set <math>\{F(a) : a\in A\}</math>, but merely some set <math>X\supseteq \{F(a) : a\in A\}</math>.

This axiom is used in the book to a) construct [[Limit ordinal|limit]] [[Ordinal number#Von Neumann definition of ordinals|von Neumann ordinals]] after the first infinite ordinal <math>\omega</math>, and b) prove that every [[Well-order|well-ordered set]] is [[order isomorphic]] to a unique von Neumann ordinal.

== 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.

==Errata==
*p. 4, line 18: “Cain and Abel” should be “Seth, Cain and Abel”.
*p. 30, line 10: "<math>x</math> onto <math>y</math>" should be "<math>x</math> into <math>y</math>".
*p, 66, line 16: "Consider, for example, the set <math>E</math> of all those pairs <math>(a,b)</math> for which <math>(1,1) \leq (a,b)</math>; the set <math>E</math> has <math>(1,1)</math> for its least element.": the statement is not true, since <math>(2,2) \leq (1,1)</math>. In fact <math>(2\times 2+1)\times 2^1 = 10 \leq (2\times 1+1)\times 2^2 = 12</math>.
*p. 73, line 19: "for each <math>z</math> in <math>X</math>" should be "for each <math>a</math> in <math>X</math>".
*p. 75, line 3: "if and only if <math>x \in F(n)</math>" should be "if and only if <math>x = \{b: S(n, b)\}</math>".
*p, 100, line 11: "then <math>\mathrm{card}\ X \sim \mathrm{card}\ Y</math>" should be "then <math>\mathrm{card}\ X = \mathrm{card}\ Y</math>".

==See also==
*[[List of important publications in mathematics]]

==Notes==

<div style="font-size:89%">
: <small>[a]</small> - In fact given the rest of the axioms, neither of the original Zermelo axiom of infinity, nor Halmos' axiom of infinity, can be proven from the other,<ref>{{cite journal |last1=Drabbe |first1=Jean |title=Les axiomes de l'infini dans la théorie des ensembles sans axiome de substitution |journal=Comptes Rendus de l'Académie des Sciences de Paris |date=20 January 1969 |volume=268 |pages=137–138 |url=https://gallica.bnf.fr/ark:/12148/bpt6k480296q/f140.item |access-date=8 September 2024}}</ref> even if one adds in the axiom of foundation. That is, one cannot construct the infinite set Halmos' axiom asserts exists, from the infinite set Zermelo's original axioms assert exists, and vice versa. The axiom schema of Replacement, on the other hand, ''does'' allow the construction of either of these infinite sets from the other.
</div>

==Bibliography==
*[[Paul Halmos|Halmos, Paul]], ''Naive Set Theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. {{isbn|0-387-90092-6}} (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. {{isbn|978-1-61427-131-4}} (Paperback edition); [https://books.google.com/books?hl=en&lr=&id=bWu9DgAAQBAJ 2017 Dover reprint] {{isbn|9780486814872}}; {{doi|10.1007/978-1-4757-1645-0}}.

==References==
{{reflist}}


[[Category:1960 non-fiction books]]
[[Category:Mathematics textbooks]]
[[Category:Springer Science+Business Media books]]
[[Category:Set theory]]