The Mathematics of Infinity: A Guide to Great Ideas, 2nd Edition

Chapter 9

Logic and Meta-Mathematics

9.1 The Collection of All Sets

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, ...