The Zermelo Fraenkel axioms

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 a and b have the same elements then a=b.

It is easy to prove using the underlying logic that equal sets have the same elements: Suppose x=y. If t\in x then by substitution t\in y. So all elements of x are in y. Similarly all elements of y are in x. Hence both x and y have the same elements. The above axiom is the converse. Therefore we can conclude that a=b iff a and b have the same elements. This also leads to the following theorem:

Theorem: a=b\iff (a\subset b\land b\subset a).
Proof: Suppose that a=b. Now for x\in a since it follows that x\in a (this is not a misprint) so a\subset a. By substitution we have a\subset b. Similarly we have b\subset a. Conversely if a\subset b and b\subset a then clearly \forall x, x\in a\iff x\in b and so a=b.\Box

2. Axiom of the empty set: A set \emptyset 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 x and y, the pair set \{x,y\} exists.

We can prove the following theorem with the aid of this axiom:

Theorem: For every x, the set \{x\} exists.

Proof: Substituting x for y in the above axiom yields a set which by the axiom of extensionality equals \{x\}.\Box

It is also now clear that if y\subset\{x\} then y=\emptyset or y=\{x\}. For if y\ne \emptyset and t\in y then t\in \{x\} and as \{x\} is a singleton so t=x. But then x\in y and so \{x\}\subset y following which y=\{x\}.

4. Axiom of union: The elements of \cup X are the elements of the elements of X.

Hence the elements of \cup \{x,y\} are not x and y. Instead they are the elements of x and y. In other words \cup\{x,y\} is the familiar set x\cup y.

5. Axiom of power set: The elements of \mathcal{P}(X) are precisely the subsets of X.

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 \psi(x) is a formula and X is a set then the set \{x\in X: \psi(x)\} exists.

It is now an easy matter to define intersection of the sets in X as Y=\cap X where Y=\{x\in\cup X:\forall t(t\in X\rightarrow x\in t)\}, provided X\ne \emptyset. To define the Cartesian product note that we define the ordered pair (a,b) as \{\{a\},\{a,b\}\} and then X\times Y=\{(x,y):x\in X\land y\in Y\}. 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 U such that \forall x(x\in U).

Proof: Suppose that there exists such a set U. Now, by the axiom of separation we have the set X=\{z\in U:z\notin z\}. Now either we have X\in X or X\notin X. In case X\in X then by definition of X we have X\notin X. In case X\notin X then again by definition of X we have X\in X. Both cases lead to contradictions.\Box

In naive set theory where any definable collection (such as \{z:z\notin z\}) 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 \{z:z\notin z\} does not make sense as the axiom of separation specifically asks for a set X from which to pick the element z 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 Z such that:
(i) \emptyset\in Z.
(ii) If x\in Z then \{x\}\in Z.

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 Z be the set provided by the above axiom. Let X be the set of subsets of Z that satisfy properties (i) and (ii) above. Let Z_0=\cap X. Then:
(a) X exists.
(b) Z_0 exists.
(c) If any set T satisfies properties (i) and (ii) of the axiom of infinity then Z_0\subset T.

Proof: (a) The set \{x\in \mathcal{P}(Z): x satisfies (i) and (ii) \} exists by the axiom of separation and equals X.
(b) The intersection is well defined if X\ne \emptyset which it is as Z\in X.
(c) Note that Z_0\cap T satisfies (i) and (ii) of the axiom of infinity and is in X so by definition of intersection Z_0\subset Z_0\cap T. If we suppose Z_0\nsubseteq T then \exists z_0\in Z_0 such that z_0\notin T following which z_0\notin Z_0\cap T. This contradicts Z_0\subset Z_0\cap T.\Box

We may define Z_0 as the set of whole numbers and show that the members of this set match our intuitive understanding of the members of \{0,1,2,3...\}. 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 \forall y(\exists no x\in y\rightarrow y\in Z). 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 Z we could have used the axiom of separation to define a set \emptyset=\{x\in Z:x\ne x\}. 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 \psi(x,y) is a formula such that \forall x\forall y\forall z(\psi(x,y)\land \psi(x,z)\rightarrow y=z) then for every set D there is a set R such that \forall y(y\in R\leftrightarrow \exists x(x\in D\land \psi(x,y))). The formula \psi(x,y) can now used to define the function governed by the relation f(x)=y 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 x contains an element y such that x\cap y=\emptyset.

This axiom disallows a set being a member of itself because of the following result:

Theorem: For all x, x\notin x.

Proof: By way of contradiction assume x\in x. By the theorem proved in the discussion on the axiom of pairing the set \{x\} exists. By the axiom of regularity there is an element y\in \{x\} such that y\cap\{x\}=\emptyset. Since \{x\} is a singleton so x=y and so x\cap\{x\}=\emptyset. This is a contradiction as by our hypothesis x\in x\cap\{x\}.\Box

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.



Filed under Set theory

2 responses to “The Zermelo Fraenkel axioms

  1. Pingback: Konig’s lemma | Notes on Mathematics

  2. Pingback: The axiom of choice | Notes on Mathematics

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s