Let

**F**

denote the *Collection of all Finite Sets*. Since **F** contains {1}, {1, 2}, {1, 2, 3}, …, the collection **F** is infinite. Put another way,

The collection **F** of all finite sets is not finite.

While this is not a surprise, it prepares us for similar ideas concerning deeper implications about more abstract collections.

**Example 9.1.1** The following is a classic example due to Bertrand Russell. Let

**C**

be the *Collection of All Sets*. We will prove the following.

**Theorem 9.1.2 C** *is not a set*.

Proof: Assume for the sake of contradiction that **C** is a set. Then **C** has the rather unsettling property

**C** ∈ **C**.

That is, **C** is an element of itself. This is like saying that a bag of sand is itself a grain of sand (bag and all), that this book is contained on one page of this book, or that a crowd of people is a person. And yet, although unsettling, **C** ∈ **C** is a consequence of the assumption that **C** is a set. This unsettling statement will lead us to a wonderful contradiction. Picture (9.1) will help with the argument that follows.

To produce a contradiction, we will do something that may strike you as familiar. Define a set *W* = {sets *S* | *S* ∈ *S*}. That is,

*W* = the set of all sets *S* that contain themselves as an element.

The complement of *W*

*W*′ = {sets *S* | *S* *S*}

You might be more comfortable with *W* if you note that by our assumption, ...

Start Free Trial

No credit card required