ńņš. 79 |

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 |