In this post we plan to discuss the Zermelo Fraenkel axioms of set theory (a term which we will abbreviate as ZF). These axioms are used by most mathematicians as the pillars on which theorems and lemmas are build. Although the axioms are named after the mathematicians Zermelo and Fraenkel, contributions from Skolem too helped in evolving the consensus on what the basic axioms ought to be. A detailed history of the evolution of these axioms and of set theory in general may be found here.
We will take a naive approach towards the basic underlying principles of logic used to illustrate the axioms. Our overall goal is to give an essential idea, and not describe a rigorous formal system. Note that in ZF terms always denote sets. There is no consensus on the exact wordings and the sequence of the axioms. We are following the treatment given in this book.
1. Axiom of extensionality: If and have the same elements then .
It is easy to prove using the underlying logic that equal sets have the same elements: Suppose . If then by substitution . So all elements of are in . Similarly all elements of are in . Hence both and have the same elements. The above axiom is the converse. Therefore we can conclude that iff and have the same elements. This also leads to the following theorem:
Proof: Suppose that . Now for since it follows that (this is not a misprint) so . By substitution we have . Similarly we have . Conversely if and then clearly and so .
2. Axiom of the empty set: A set having no elements exists.
This axiom may be thought of as redundant in certain versions of ZF, where it may be deduced from other axioms. By a little piece of vacuous reasoning it follows that the empty set is a subset of every set.
3. Axiom of pairing: For every and , the pair set exists.
We can prove the following theorem with the aid of this axiom:
Theorem: For every , the set exists.
Proof: Substituting for in the above axiom yields a set which by the axiom of extensionality equals .
It is also now clear that if then or . For if and then and as is a singleton so . But then and so following which .
4. Axiom of union: The elements of are the elements of the elements of .
Hence the elements of are not and . Instead they are the elements of and . In other words is the familiar set .
5. Axiom of power set: The elements of are precisely the subsets of .
We do not define other set functions, like intersection and Cartesian product since their existence follows from the next axiom.
6. Axiom of separation: If is a formula and is a set then the set exists.
It is now an easy matter to define intersection of the sets in as where , provided . To define the Cartesian product note that we define the ordered pair as and then . We cannot however define complement because of the following theorem. It says that there is no universe (a set which has everything).
Theorem: There is no set such that .
Proof: Suppose that there exists such a set . Now, by the axiom of separation we have the set . Now either we have or . In case then by definition of we have . In case then again by definition of we have . Both cases lead to contradictions.
In naive set theory where any definable collection (such as ) was understood as a set there is no way to clear the anomaly which follows from the above proof. One of the reasons for the abandonment of naive set theory in favor of ZF was in fact this paradox. In ZF the set does not make sense as the axiom of separation specifically asks for a set from which to pick the element from. As we don’t have a universal set in ZF so the paradox is entirely sidestepped. The fact that there is no universal set in ZF has appeared intuitively undesirable to some, and there exist set theories which include a universal set.
It is interesting to note that although the paradox is attributed to Russell, it was Zermelo who had originally discovered it. Unfortunately he didn’t publish this idea and Russell independently discovered the paradox a year later and published it.
7. Axiom of infinity There is a set such that:
(ii) If then .
This axiom guarantees the existence of an infinite set. It is present to ensure that ZF is powerful enough to contain the collection of all numbers (a concept which we do not wish to make precise at this juncture). Once we have an infinite set we can also make precise the idea of a smallest infinite set as given by this axiom. This is illustrated by the following theorem:
Theorem: Let be the set provided by the above axiom. Let be the set of subsets of that satisfy properties (i) and (ii) above. Let . Then:
(c) If any set satisfies properties (i) and (ii) of the axiom of infinity then .
Proof: (a) The set satisfies (i) and (ii) exists by the axiom of separation and equals .
(b) The intersection is well defined if which it is as .
(c) Note that satisfies (i) and (ii) of the axiom of infinity and is in so by definition of intersection . If we suppose then such that following which . This contradicts .
We may define as the set of whole numbers and show that the members of this set match our intuitive understanding of the members of . However such a discussion is presently out of our scope.
We have used the notion of the empty set in the statement of the axiom of infinity. The axiom of infinity can be rephrased so as not to actually assume that the empty set exists. We could have stated (i) as no . Then the axiom of infinity a priori only asserts the existence of a set meeting this description, without actually asserting that it contains anything. Once we had got the set we could have used the axiom of separation to define a set . Hence in this formulation the axiom of the empty set would have ceased to be an axiom and would have become a theorem of ZF. However, only a superficial difference exists in these two versions of ZF and we find no significant advantage in choosing one over the other.
8. Axiom of replacement: Informally this axiom states that ranges of functions restricted to sets exists. More formally, if is a formula such that then for every set there is a set such that . The formula can now used to define the function governed by the relation as per the usual definition.
This axiom was not part of Zermelo’s original axioms and was added later, since it was found to aid immensely in establishing certain intuitively supported results in set theory. It is rarely used directly though, (one example is here), and within set theory its use is primarily in proving that certain large sets (such as those which are uncountable) theoretically exist in ZF.
9. Axiom of Regularity: This axiom states that every non empty set contains an element such that .
This axiom disallows a set being a member of itself because of the following result:
Theorem: For all , .
Proof: By way of contradiction assume . By the theorem proved in the discussion on the axiom of pairing the set exists. By the axiom of regularity there is an element such that . Since is a singleton so and so . This is a contradiction as by our hypothesis .
Just like the previous axiom it is also a not obvious why this axiom must be true a priory. It is arguably the least useful ingredient of ZF, since most results in the branches of mathematics based on set theory hold even in the absence of regularity. However within mathematics we hardly ever encounter sets which contain themselves as a member, and this axiom is essential in outlawing such behavior.
That ends the list of the Zermelo Fraenkel axioms. One more axiom, probably the most famous of all, called the axiom of choice is usually added to ZF, and the resulting list of axioms is then referred to as ZFC.