∀a∃b∀x(x ∈ b ” x ⊆ a)

Proof: By the Axiom of Comprehension, we may form the set c =

{x | x ⊆ b}. This is the desired set. By the Axiom of Extensionality,

there can be only one such set.

By way of example, let us form the powerset of the set b = {2, 3}. Thus,

we need a set whose members are all the subsets of b. There are four of these.

The most obvious two are the singletons {2} and {3}. The other two are the

empty set, which is a subset of every set, as we saw in Problem 15.11, and the

set b itself, since every set is a subset of itself. Thus:

„˜b = {…, {2}, {3}, {2, 3}}

Here are some facts about the powerset operation. We will ask you to prove

them in the problems.

Proposition 11. Let a and b be any sets.

1. b ∈ „˜b

Section 15.7

430 / First-order Set Theory

2. … ∈ „˜b

3. a ⊆ b i¬ „˜a ⊆ „˜b

It is possible for a set to have some of its own subsets as elements. For

example, any set that has the empty set as an element has a subset as an

element, since the empty set is a subset of every set. To take another example,

the set

{Washington Monument}

is both a subset and an element of the set

{Washington Monument, {Washington Monument}}

However, it turns out that no set can have all of its subsets as elements.

Proposition 12. For any set b, it is not the case that „˜b ⊆ b.

Proof: Let b be any set. We want to prove that „˜b ⊆ b. To prove

this, we construct a particular subset of b that is not an element of

b. Let

c = {x | x ∈ b § x ∈ x}

by the Axiom of Comprehension. This set c is clearly a subset of b

since it was de¬ned to consist of those members of b satisfying some

additional condition. It follows from the de¬nition of the powerset

operation that c is an element of „˜b. We will show that c ∈ b.

Toward a proof by contradiction, suppose that c ∈ b. Then either

c ∈ c or c ∈ c. But which? It is not hard to see that neither can

be the case. First, suppose that c ∈ c. Then by our de¬nition of

c, c is one of those members of b that is left out of c. So c ∈ c.

Next consider the possibility that c ∈ c. But then c is one of those

members of b that satis¬es the de¬ning condition for c. Thus c ∈ c.

Thus we have proven that c ∈ c ” c ∈ c, which is a contradiction.

So our assumption that c ∈ b must be false, so „˜b ⊆ b .

This theorem applies to both ¬nite and in¬nite sets. The proof shows how

to take any set b and ¬nd a set c which is a subset of b but not a member of b,

namely the set c = {x | x ∈ b and x ∈ x}. This is sometimes called the Russell

set for b, after Bertrand Russell. So what we have proved in the preceding can

Russell set for b

be restated as:

Chapter 15

The powerset of a set / 431

Proposition 13. For any set b, the Russell set for b, the set

{x | x ∈ b § x ∈ x},

is a subset of b but not a member of b.

This result is, as we will see, a very important result, one that immediately

implies Proposition 12.

Let™s compute the Russell set for a few sets. If b = {0, 1}, then the Russell

set for b is just b itself. If b = {0, {0, {0, . . . }}} then the Russell set for b is just

{0} since b ∈ b. Finally, if b = {Washington Monument}, then the Russell set

for b is just b itself.

Remember

The powerset of a set b is the set of all its subsets:

„˜b = {a | a ⊆ b}

Exercises

15.54 Compute „˜{2, 3, 4}. Your answer should 15.55 Compute „˜{2, 3, 4, 5}.

have eight distinct elements.

15.56 Compute „˜{2}. 15.57 Compute „˜….

15.58 Compute „˜„˜{2, 3}. 15.59 Prove the results stated in Proposi-

tion 11.

15.60 Here are a number of conjectures you might make. Some are true, but some are false. Prove

the true ones, and ¬nd examples to show that the others are false.

1. For any set b, … ⊆ „˜b.

2. For any set b, b ⊆ „˜b.

3. For any sets a and b, „˜(a ∪ b) = „˜a ∪ „˜b.

4. For any sets a and b, „˜(a © b) = „˜a © „˜b.

15.61 What is the Russell set for each of the following sets?

1. {…}

2. A set a satisfying a = {a}

3. A set {1, a} where a = {a}

4. The set of all sets

Section 15.7

432 / First-order Set Theory

Section 15.8

Russell™s Paradox

We are now in a position to show that something is seriously amiss with

the theory we have been developing. Namely, we can prove the negation of

Proposition 12. In fact, we can prove the following which directly contradicts

Proposition 12.

Proposition 14. There is a set c such that „˜c ⊆ c.

Proof: Using the Axiom of Comprehension, there is a universal set,

a set that contains everything. This is the set c = {x | x = x}. But

then every subset of c is a member of c, so „˜c is a subset of c.

The set c used in the above proof is called the universal set and is usually

universal set (V )

denoted by “V .” It is called that because it contains everything as a mem-

ber, including itself. What we have in fact shown is that the powerset of the

universal set both is and is not a subset of the universal set.

Let us look at our contradiction a bit more closely. Our proof of Propo-

sition 12, applied to the special case of the universal set, gives rise to the

set

Z = {x | x ∈ V § x ∈ x}

This is just the Russell set for the universal set. But the proof of Proposition 12

shows that Z is a member of Z if and only if Z is not a member of Z. This

set Z is called the (absolute) Russell set, and the contradiction we have just

established is called Russell™s Paradox.

Russell™s Paradox

It would be hard to overdramatize the impact Russell™s Paradox had on

set theory at the turn of the century. Simple as it is, it shook the subject to its

foundations. It is just as if in arithmetic we discovered a proof that 23+27=50

and 23+27= 50. Or as if in geometry we could prove that the area of a square

both is and is not the square of the side. But here we are in just that position.

This shows that there is something wrong with our starting assumptions of

the whole theory, the two axioms with which we began. There simply is no

domain of sets which satis¬es these assumptions. This discovery was regarded

as a paradox just because it had earlier seemed to most mathematicians that

the intuitive universe of sets did satisfy the axioms.

Russell™s Paradox is just the tip of an iceberg of problematic results in

reactions to the paradox

naive set theory. These paradoxes resulted in a wide-ranging attempt to clarify

the notion of a set, so that a consistent conception could be found to use in

mathematics. There is no one single conception which has completely won out

Chapter 15

Zermelo Frankel set theory zfc / 433

in this e¬ort, but all do seem to agree on one thing. The problem with the

naive theory is that it is too uncritical in its acceptance of “large” collections

like the collection V used in the last proof. What the result shows is that

there is no such set. So our axioms must be wrong. We must not be able to

use just any old property in forming a set.

The father of set theory was the German mathematician Georg Cantor. His

work in set theory, in the late nineteenth century, preceded Russell™s discovery

of Russell™s paradox in the earlier twentieth century. It is thus natural to

imagine that he was working with the naive, hence inconsistent view of sets.

However, there is clear evidence in Cantor™s writings that he was aware that

unrestricted set formation was inconsistent. He discussed consistent versus

inconsistent “multiplicities,” and only claimed that consistent multiplicities

could be treated as objects in their own right, that is, as sets. Cantor was not

working within an axiomatic framework and was not at all explicit about just

what properties or concepts give rise to inconsistent multiplicities. People

following his lead were less aware of the pitfalls in set formation prior to

Russell™s discovery.

Remember

Russell found a paradox in naive set theory by considering

Z = {x | x ∈ x}

and showing that the assumption Z ∈ Z and its negation each entails the

other.

Section 15.9

Zermelo Frankel set theory zfc

The paradoxes of naive set theory show us that our intuitive notion of set is

simply inconsistent. We must go back and rethink the assumptions on which

the theory rests. However, in doing this rethinking, we do not want to throw

out the baby with the bath water.

Which of our two assumptions got us into trouble, Extensionality or Com- diagnosing the problem

prehension? If we examine the Russell Paradox closely, we see that it is ac-

tually a straightforward refutation of the Axiom of Comprehension. It shows

that there is no set determined by the property of not belonging to itself. That

Section 15.9

434 / First-order Set Theory

is, the following is, on the one hand, a logical truth, but also the negation of

an instance of Comprehension:

¬∃c∀x(x ∈ c ” x ∈ x)

The Axiom of Extensionality is not needed in the derivation of this fact. So it is

the Comprehension Axiom which is the problem. In fact, back in Chapter 13,

Exercise 13.52, we asked you to give a formal proof of

¬∃y ∀x [E(x, y) ” ¬E(x, x)]

This is just the above sentence with “E(x, y)” used instead of “x ∈ y”. The

proof shows that the sentence is actually a ¬rst-order validity; its validity does

not depend on anything about the meaning of “∈.” It follows that no coherent

conception of set can countenance the Russell set.

But why is there no such set? It is not enough to say that the set leads

us to a contradiction. We would like to understand why this is so. Various

answers have been proposed to this question.

One popular view, going back to the famous mathematician John von

Neumann, is based on a metaphor of size. The intuition is that some predicates

limitations of size

have extensions that are “too large” to be successfully encompassed as a whole

and treated as a single mathematical object. Any attempt to consider it as a

completed totality is inadequate, as it always has more in it than can be in

any set.

On von Neumann™s view, the collection of all sets, for example, is not itself

a set, because it is “too big.” Similarly, on this view, the Russell collection of

those sets that are not members of themselves is also not a set at all. It is too

big to be a set. How do we know? Well, on the assumption that it is a set, we

get a contradiction. In other words, what was a paradox in the naive theory

turns into an indirect proof that Russell™s collection is not a set. In Cantor™s

terminology, the inconsistent multiplicities are those that are somehow too

large to form a whole.

How can we take this intuition and incorporate it into our theory? That

is, how can we modify the Comprehension Axiom so as to allow the instances

we want, but also to rule out these “large” collections?

The answer is a bit complicated. First, we modify the axiom so that we

can only form subsets of previously given sets. Intuitively, if we are given a

set a and a w¬ P (x) then we may form the subset of a given by:

{x | x ∈ a § P (x)}

The idea here is that if a is not “too large” then neither is any subset of it.

Chapter 15