<<

. 79
( 107 .)



>>

Zermelo Frankel set theory zfc / 435



Formally, we express this by the axiom
∀a∃b∀x[x ∈ b ” (x ∈ a § P (x))]
In this form, the axiom scheme is called the Axiom of Separation. Actually, Axiom of Separation
as before, we need the universal closure of this w¬, so that any other free
variables in P (x) are universally quanti¬ed.
This clearly blocks us from thinking we can form the set of all sets. We
cannot use the Axiom of Separation to prove it exists. (In fact, we will later
show that we can prove it does not exist.) And indeed, it is easy to show that
the resulting theory is consistent. (See Exercise 15.68.) However, this axiom
is far too restrictive. It blocks some of the legitimate uses we made of the
Axiom of Comprehension. For example, it blocks the proof that the union of
two sets always exists. Similarly, it blocks the proof that the powerset of any
set exists. If you try to prove either of these you will see that the Axiom of
Separation does not give you what you need.
We can™t go into the development of modern set theory very far. Instead,
we will state the basic axioms and give a few remarks and exercises. The
interested student should look at any standard book on modern set theory.
We mention those by Enderton, Levy, and Vaught as good examples.
The most common form of modern set theory is known as Zermelo-Frankel Zermelo-Frankel set
theory zfc
set theory, also known as zfc. zfc set theory can be thought of what you get
from naive set theory by weakening the Axiom of Comprehension to the Axiom
of Separation, but then throwing back all the instances of Comprehension that
seem intuitively true on von Neumann™s conception of sets. That is, we must
throw back in those obvious instances that got inadvertently thrown out.
In zfc, it is assumed that we are dealing with “pure” sets, that is, there is
nothing but sets in the domain of discourse. Everything else must be modeled
within set theory. For example, in zfc, we model 0 by the empty set, 1 by {…},
and so on. Here is a list of the axioms of zfc. In stating their fol versions, axioms of zfc
we use the abbreviations ∃x ∈ y P and ∀x ∈ y P for ∃x(x ∈ y § P ) and
∀x(x ∈ y ’ P ).
1. Axiom of Extensionality: As above.
2. Axiom of Separation: As above.
3. Unordered Pair Axiom: For any two objects there is a set that has both
as elements.
4. Union Axiom: Given any set a of sets, the union of all the members of
a is also a set. That is:
∀a∃b∀x[x ∈ b ” ∃c ∈ a(x ∈ c)]



Section 15.9
436 / First-order Set Theory


5. Powerset Axiom: Every set has a powerset.

6. Axiom of In¬nity: There is a set of all natural numbers.

7. Axiom of Replacement: Given any set a and any operation F that de¬nes
a unique object for each x in a, there is a set

{F (x) | x ∈ a}

That is, if ∀x ∈ a∃!yP (x, y), then there is a set b = {y | ∃x ∈ aP (x, y)}.

8. Axiom of Choice: If f is a function with non-empty domain a and for
each x ∈ a, f (x) is a non-empty set then there is a function g also with
domain a such that for each x ∈ a, g(x) ∈ f (x). (The function g is
called a choice function for f since it chooses an element of f (x) for
each x ∈ a.)

9. Axiom of Regularity: No set has a nonempty intersection with each of
its own elements. That is:

∀b[b = … ’ ∃y ∈ b(y © b = …)]

Of these axioms, only the Axioms of Regularity and Choice are not direct,
straightforward logical consequences of the naive theory. (Technically speak-
ing, they are both consequences, though, since the naive theory is inconsistent.
After all, everything is a consequence of inconsistent premises.)
The Axiom of Choice (ac) has a long and somewhat convoluted history.
Axiom of Choice
There are many, many equivalent ways of stating it; in fact there is a whole
book of statements equivalent to the axiom of choice. In the early days of set
theory some authors took it for granted, others saw no reason to suppose it
to be true. Nowadays it is taken for granted as being obviously true by most
mathematicians. The attitude is that while there may be no way to de¬ne
a choice function g from f , and so no way to prove one exists by means of
Separation, but such functions exists none-the-less, and so are asserted to
exist by this axiom. It is extremely widely used in modern mathematics.
The Axiom of Regularity is so called because it is intended to rule out
Axiom of Regularity or
Foundation “irregular” sets like a = {{{. . . }}} which is a member of itself. It is sometimes
also called the Axiom of Foundation, for reasons we will discuss in a moment.
You should examine the axioms of zfc in turn to see if you think they are
true, that is, that they hold on von Neumann™s conception of set. Many of
the axioms are readily justi¬ed on this conception. Two that are not aren™t
obvious are the power set axiom and the Axiom of Regularity. Let us consider
these in turn, though brie¬‚y.



Chapter 15
Zermelo Frankel set theory zfc / 437



Sizes of in¬nite sets

Some philosophers have suggested that the power set of an in¬nite set might
be too large to be considered as a completed totality. To see why, let us start
by thinking about the size of the power set of ¬nite sets. We have seen that sizes of powersets
if we start with a set b of size n, then its power set „˜b has 2n members. For
example, if b has ¬ve members, then its power set has 25 = 32 members. But if
b has 1000 members, then its power set has 21000 members, an incredibly large
number indeed; larger, they say, than the number of atoms in the universe.
And then we could form the power set of that, and the power set of that,
gargantuan sets indeed.
But what happens if b is in¬nite? To address this question, one ¬rst has
to ¬gure out what exactly one means by the size of an in¬nite set. Cantor sizes of in¬nite sets
answered this question by giving a rigorous analysis of size that applied to all
sets, ¬nite and in¬nite. For any set b, the Cantorian size of b is denoted | b |. |b|
Informally, | b |=| c | just in case the members of b and the members of c can
be associated with one another in a unique fashion. More precisely, what is
required is that there be a one-to-one function with domain b and range c.
(The notion of a one-to-one function was de¬ned in Exercise 50.)
For ¬nite sets, | b| behaves just as one would expect. This notion of size is
somewhat subtle when it comes to in¬nite sets, though. It turns out that for
in¬nite sets, a set can have the same size as some of its proper subsets. The
set N of all natural numbers, for example, has the same size as the set E of
even numbers; that is | N | = | E |. The main idea of the proof is contained in
the following picture:

01 2 ... n ...

02 4 ... 2n ...

This picture shows the sense in which there are as many even integers as there
are integers. (This was really the point of Exercise 15.51.) Indeed, it turns out
that many sets have the same size as the set of natural numbers, including
the set of all rational numbers. The set of real numbers, however, is strictly
larger, as Cantor proved.
Cantor also showed that that for any set b whatsoever,

| „˜b | > | b|

This result is not surprising, given what we have seen for ¬nite sets. (The
proof of Proposition 12 was really extracted from Cantor™s proof of this fact.) questions about
powerset axiom
The two together do raise the question as to whether an in¬nite set b could be



Section 15.9
438 / First-order Set Theory


“small” but its power set “too large” to be a set. Thus the power set axiom
is not as unproblematic as the other axioms in terms of Von Neumann™s size
metaphor. Still, it is almost universally assumed that if b can be coherently
regarded as a ¬xed totality, so can „˜b. Thus the power set axiom is a full-
¬‚edged part of modern set theory.

Cumulative sets

If the power set axiom can be questioned on the von Neumann™s conception
of a set as a collection that is not too large, the Axiom of Regularity is
regularity and size
clearly unjusti¬ed on this conception. Consider, for example, the irregular set
a = {{{. . . }}} mentioned above, a set ruled out by the Axiom of Regularity.
Notice that this set is its own singleton, a = {a}, so it has only one member.
Therefore there is no reason to rule it out on the grounds of size. There might
be some reason for ruling it out, but size is not one. Consequently, the Axiom
of Regularity does not follow simply from the conception of sets as collections
that are not too large.
To justify the Axiom of Regularity, one needs to augment von Neumann™s
cumulative conception
of sets size metaphor by what is known as the “cumulation” metaphor due to the
logician Zermelo.
Zermelo™s idea is that sets should be thought of as formed by abstract acts
of collecting together previously given objects. We start with some objects
that are not sets, collect sets of them, sets whose members are the objects
and sets, and so on and on. Before one can form a set by this abstract act of
collecting, one must already have all of its members, Zermelo suggested.
On this conception, sets come in distinct, discrete “stages,” each set arising
at the ¬rst stage after the stages where all of its members arise. For example,
if x arises as stage 17 and y at stage 37, then a = {x, y} would arise at stage
38. If b is constructed at some stage, then its powerset „˜b will be constructed
at the next stage. On Zermelo™s conception, the reason there can never be a
set of all sets is that as any set b arises, there is always its power set to be
formed later.
The modern conception of set really combines these two ideas, von Neu-
mann™s and Zermelo™s. This conception of set is as a small collection which
is formed at some stage of this cumulation process. If we look back at the
irregular set a = {{{. . . }}}, we see that it could never be formed in the cu-
mulative construction because one would ¬rst have to form its member, but
it is its only member.
More generally, let us see why, on the modi¬ed modern conception, that
regularity and
cumulation Axiom of Regularity is true. That is, let us prove that on this conception, no
set has a nonempty intersection with each of its own elements.



Chapter 15
Zermelo Frankel set theory zfc / 439



Proof: Let a be any set. We need to show that one of the elements
of a has an empty intersection with a. Among a™s elements, pick any
b ∈ a that occurs earliest in the cumulation process. That is, for any
other c ∈ a, b is constructed at least as early as c. We claim that
b © a = …. If we can prove this, we will be done. The proof is by
contradiction. Suppose that b © a = … and let c ∈ b © a. Since c ∈ b, c
has to occur earlier in the construction process than b. On the other
hand, c ∈ a and b was chosen so that there was no c ∈ a constructed
earlier than b. This contradiction concludes the proof.

One of the reasons the Axiom of Regularity is assumed is that it gives one a
powerful method for proving theorems about sets “by induction.” We discuss
various forms of proof by induction in the next chapter. For the relation with
the Axiom of Regularity, see Exercise 16.10.

Remember

1. Modern set theory replaces the naive concept of set, which is incon-
sistent, with a concept of set as a collection that is not too large.

2. These collections are seen as arising in stages, where a set arises only
after all its members are present.

3. The axiom of comprehension of set theory is replaced by the Axiom
of Separation and some of the intuitively correct consequences of the
axiom of comprehension.

4. Modern set theory also contains the Axiom of Regularity, which is
justi¬ed on the basis of (2).

5. All the propositions stated in this chapter”with the exception of
Propositions 1 and 14”are theorems of zfc.




Exercises


15.62 Write out the remaining axioms from above in fol.


15.63 Use the Axioms of Separation and Extensionality to prove that if any set exists, then the empty
 set exists.




Section 15.9
440 / First-order Set Theory


15.64 Try to derive the existence of the absolute Russell set from the Axiom of Separation. Where
 does the proof break down?

15.65 Verify our claim that all of Theorems 2“13 are provable using the axioms of zfc. (Some of the
 proofs are trivial in that the theorems were thrown in as axioms. Others are not trivial.)

15.66 (Cantor™s Theorem) Show that for any set b whatsoever, | „˜b | = | b | . [Hint: Suppose that f is
 a function mapping „˜b one-to-one into b and then modify the proof of Proposition 12.]

15.67 (There is no universal set)
 1. Verify that our proof of Proposition 12 can be carried out using the axioms of zfc.
2. Use (1) to prove there is no universal set.

15.68 Prove that the Axiom of Separation and Extensionality are consistent. That is, ¬nd a universe

<<

. 79
( 107 .)



>>