O'Reilly logo

The Mathematics of Infinity: A Guide to Great Ideas, 2nd Edition by Theodore G. Faticoni

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

CC.

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

images

To produce a contradiction, we will do something that may strike you as familiar. Define a set W = {sets S | SS}. 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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required