<<

. 78
( 107 .)



>>

bers are just the subsets of b. In symbols:

∀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

<<

. 78
( 107 .)



>>