Georg Cantor was a German mathematician responsible for the invention of set theory. Before him, the concept of infinity was not well studied or considered by mathematicians. The importance of Cantor’s development of set theory is very clear as it is the basis for much of modern mathematics. We will take a look at Cantor’s Theorem, but first some preliminaries.
Definition: Given a set . The power set of is defined to be the set of all subsets of .
Example: Suppose . The power set of is
Definition: Suppose and are sets. A map is said to be a surjection if for every member of there is a member of that maps to under . i.e. .
Cantor’s Theorem: There is so surjection from a set to its power set.
Proof: Let be a set and suppose is a surjection. Since is a map we are guaranteed that for each . Each element in is a subset of by definition of power set. So either or .
We build a new set Note then that hence since is a surjection, there is some member of so that . This means that and a contradiction.
This theorem leads to the idea of larger infinities, also known as infinite cardinals. We know the set of natural numbers is countable. Let us call the size of this set . By Cantor’s Theorem, the power set of the natural numbers is somehow larger. In fact it is an entire order of infinity larger which we call . This can be continued indefinitely and we see that there are infinitely many sizes of infinity. For more on the subject, check out “Basic Set Theory” by A. Levy.