Posted by: Gary Ernest Davis on: October 4, 2010

I have mentioned in several posts now that many people do not think it is problematic to bundle all

Another apparently harmless naive thought about set formation is that one can always construct the set of all subsets of a given set. For a set the set of all subsets of is denoted by . For simple sets such as we can easily visualize and the relations between its elements – i.e. the subsets of :

where denotes the empty set, and rising lines indicate the set below is a subset of the set above.

Perhaps someone might balk at reflecting on a set consisting of all subsets of the natural numbers, yet there is a simple device to make this construction seem plausible.

The set of all subsets of a set is in one-to-one correspondence with the set of all functions from the set into the two element set .

This correspondence is established as follows: for each subset define a function by ; conversely, for each function define a subset of by .

So to think about all subsets of the set of natural numbers, it is equivalent, to think about all functions .

Such functions give a value of for each natural number, and so correspond to sequences where each is either .

Georg Cantor established the following extremely simple,Â yet devastating, result: for any set for which the set of all subsets of exists, there cannot be a one-to-one correspondence between and .

The argument is incredibly simple as it is elegant.

A one-to-one correspondence between and is established by a function that is invertible.Â Cantor shows that no function is invertible. Here’s how he does it: let be a function. Define the subset by . Then, for every exactly when . Because either for every it follows that for all , and therefore the function is not invertible.

This is Cantor’s famous diagonal argument. Quite simple and relatively uncontroversial. Yet is has a devastating and astonishing consequence.

Given that, naively, we can always form the set of all subsets of a set , we see that the set of all subsets of natural numbers cannot be put into one-to-one correspondence with itself. Because the mapping from is one-to-one, but not invertible, the set has greater cardinality than that of . That is, the set of all subsets of natural numbers is a set of greater order of infinity than the set of natural numbers itself.

What now stops us from forming the set which, by Cantor’s argument, has a higher order of infinity again, and so on, and so on(*ad infinitum* and beyond …) ? This is a glimpse of Cantor’s paradise from which, David Hilbert averred, no one shall expel us.

1 | Neal Richter

October 4, 2010 at 10:27 am

Great post.