Section B.19 The Zermelo-Fraenkel Axioms of Set Theory
In the first part of this appendix, we put number systems on a firm foundation, but in the process, we used an intuitive understanding of sets. Not surprisingly, this approach is fraught with danger. As was first discovered more than 100 years ago, there are major conceptual hurdles in formulating consistent systems of axioms for set theory. And it is very easy to make statements that sound “obvious” but are not.
Here is one very famous example. Let \(X\) and \(Y\) be sets and consider the following two statements:
There exists an injection \(f:X\rightarrow Y\text{.}\)
There exists a surjection \(g:Y\rightarrow X\text{.}\)
If \(X\) and \(Y\) are finite sets, these statements are equivalent, and it is perhaps natural to surmise that the same is true when \(X\) and \(Y\) are infinite. But that is not the case.
Here is the system of axioms popularly known as ZFC, which is an abbreviation for Zermelo-Fraenkel plus the Axiom of Choice. In this system, the notion of set and the membership operator \(\in\) are undefined. However, if \(A\) and \(B\) are sets, then exactly one of the following statements is true: (i) \(A\in B\) is true; (ii) \(A\in B\) is false. When \(A\in B\) is false, we write \(A\notin B\text{.}\) Also, there is an equivalence relation \(=\) defined on sets.
Axiom B.52. Zermelo-Fraenkel Axioms with Axiom of Choice.
- Axiom of extensionality
Two sets are equal if and only if they have the same elements.
- Axiom of empty set
There is a set \(\emptyset\) with no elements.
- Axiom of pairing
If \(x\) and \(y\) are sets, then there exists a set containing \(x\) and \(y\) as its only elements, which we denote by \(\{x,y\}\text{.}\) Note: If \(x=y\text{,}\) then we write only \(\{x\}\text{.}\)
- Axiom of union
For any set \(x\text{,}\) there is a set \(y\) such that the elements of \(y\) are precisely the elements of the elements of \(x\text{.}\)
- Axiom of infinity
There exists a set \(x\) such that \(\emptyset\in x\) and whenever \(y\in x\text{,}\) so is \(\{y ,\{y\}\}\text{.}\)
- Axiom of power set
Every set has a power set. That is, for any set \(x\text{,}\) there exists a set \(y\text{,}\) such that the elements of \(y\) are precisely the subsets of \(x\text{.}\)
- Axiom of regularity
Every non-empty set \(x\) contains some element \(y\) such that \(x\) and \(y\) are disjoint sets.
- Axiom of separation (or subset axiom)
Given any set and any proposition \(P(x)\text{,}\) there is a subset of the original set containing precisely those elements \(x\) for which \(P(x)\) holds.
- Axiom of replacement
Given any set and any mapping, formally defined as a proposition \(P(x,y)\) where \(P(x,y_1)\) and \(P(x,y_2)\) implies \(y_1 = y_2\text{,}\) there is a set containing precisely the images of the original set’s elements.
- Axiom of choice
Given any set of mutually exclusive non-empty sets, there exists at least one set that contains exactly one element in common with each of the non-empty sets.
A good source of additional (free) information on set theory is the collection of Wikipedia articles. Do a web search and look up the following topics and people:
Zermelo-Fraenkel set theory.
Axiom of Choice.
Peano postulates.
Georg Cantor, Augustus De Morgan, George Boole, Bertrand Russell and Kurt Gödel.
