next up previous
Next: About this document ... Up: Set Theory Handout Previous: Naive Set Theory Is

Zermelo-Frankel Set Theory

This is just an extremely quick overview. The Axiom of Extensionality remains the same, but the Comprehension Axiom is replaced by something of a hodgepodge of axioms that are not as intuitively obvious. Here is a quick list:

Axiom 4.1 (Axiom of Extensionality)   $ \forall a \forall b [ \forall x (x \in a \leftrightarrow x \in b ) \to a=b] $

Axiom 4.2 (Axiom of Separation)   $ \forall a \exists b \forall x [x \in b \leftrightarrow (x \in a \wedge P(x))] $

Axiom 4.3 (Unordered Pair Axiom)   $ \forall z_1 \forall z_2 \exists a \forall x (x \in a \leftrightarrow (x=z_1 \vee x=z_2)) $

Axiom 4.4 (Union Axiom)   $ \forall a \exists b \forall x [x \in b \leftrightarrow \exists c \in a (x \in c)] $

(Remember that $\exists c \in a (x \in c) $ is just a shorthand way of writing $\exists c (c \in a \wedge x \in c)$.)

Axiom 4.5 (Powerset Axiom)   $ \forall z \exists a \forall x (x \in a \leftrightarrow x \subseteq z)$

Axiom 4.6 (Axiom of Infinity)   $ \exists a (\emptyset \in a \wedge \forall x (x \in a \to s(x) \in a)) $

The function $s(x)$ needs comment here. There are two ways to look at this. We can think of $s(x)$ as the singleton function, a function which takes any item as argument and yields the singleton set with that item as its only member as its value. Thus the set that the Axiom of Infinity declares to exist is the set:

\begin{displaymath}\{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \ldots\}\end{displaymath}

However, recall that we are also using sets to model the natural numbers. $\emptyset$ is interpreted as 0, $\{\emptyset\}$ as 1, and so on. So we could equally well think of $s(x)$ as the successor function which takes any natural number as argument and yields the successor of that number as value.

Axiom 4.7 (Axiom of Replacement)   $\forall a [\forall x \in a \exists!yP(x,y) \to \exists b (b = \{y\vert\exists x \in aP(x,y)\}]$

Here we have used the informal brace notation for the set $b$. The idea is that if P(x,y) corresponds to a function from members of a given set to objects, then we can form a new set by replacing every member of the given set with the object the function maps it to.

Axiom 4.8 (Axiom of Choice)   If $f$ is a function with non-empty domain $a$ and for each $x \in a$, $f(x)$ is a non-empty set then there is a function $g$ also with domain $a$ such that for each $x \in a$, $g(x) \in f(x)$.

This is Barwise and Etchemendy's formulation on p. 436. I haven't even tried to do this entirely in symbols! The general idea is that for any collection of sets, you can choose one member from each of them. The function $f(x)$ gives us our initial collection of sets (namely the values of $f(x)$ for the elements in its domain), and the function $g(x)$ is the function that chooses a single item from each of the sets that are the values of $f(x)$. The Axiom of Choice, although widely accepted, is controversial. There's a very interesting web page on the Axiom of choice, with links to further online material, at schectex/ccc/choice.html.

Axiom 4.9 (Axiom of Regularity)   $ \forall b [ b \not= \emptyset \to \exists y \in b(y \cap b = \emptyset)] $

This rules out certain nasty sets, especially certain sets that contain themselves as members. Barwise and Etchemendy mention in particular the set $\{\{\{\ldots\}\}\}$ -- this set has only one member, which is the same as itself. (And its member has only member, also identical to itself, and so on! A somewhat unsettling set.) But it violates the Axiom of Regularity, since its intersection with its only member is not empty. In fact any set whose only member is itself, i.e. any set $a$ such that $a = \{a\}$, will violate the Axiom of Regularity.

It may seem at first that the Axiom of Regularity does not rule out all sets that contain themselves as members. Consider the set $a$ such that $a = \{\{5\}, a \}$. The intersection of $a$ with its member listed second is clearly not $\emptyset$, but its intersection with $\{5\}$ is still $\emptyset$, since the only member of $\{5\}$ is 5, and neither of the members of $a$ is 5. So the axiom does not appear to rule out all sets that contain themselves, only the sets that contain only themselves.

However, in combination with the Unordered Pair Axiom, the Axiom of Regularity does in fact rule out every set that contains itself as a member. Remember that the Unordered Pair Axiom says that, for every pair of items $z_1$ and $z_2$, there is a set containing those items and nothing else. Notice that this axiom includes, as a degenerate case, the case in which $z_1 = z_2$. Therefore, if our set $a$ which contains iself is a set, then there must be a set $\{a\}$ that contains $a$ and nothing else. But we have already seen that the Axiom of Regularity rules this out. So these two axioms together show that there is no set that is a member of itself.

next up previous
Next: About this document ... Up: Set Theory Handout Previous: Naive Set Theory Is
cbrown 2002-01-27