Favorite Theorems: Cantor’s Theorem
This one is being added to my list just because of how slick the proof is. We finally proved it during Intermediate Analysis on Thursday. By the way, in case you turned glossy eyed at the sight of the following proof, I encourage you to scroll down to the end of this and read the story at the bottom. It is an interesting paradox, somewhat related to this proof.
Thm: (Cantor's Theorem) For every set 
, 
a surjection of onto the set 
, the power set of .
For reference note that the power set of , denoted 
, is the set of all subsets of . To call a mapping a surjection implies that it is "onto". In other words, if 
, then 
is onto if and only if, for every element ![b\in B, \ \ \exists \ a\in A \](/latexrender/pictures/4adf2e9688ddc0c3096a8a9207fc0782.png "b\in B, \ \ \exists \ a\in A \")
such that 
Proof: For a contradiction we assume that there is a function, 
that is onto. Let 
, which implies that 
. So then either, 
or 
.
Let 
. Now, because 
then there must be some 
such that 
.
So either (i) 
or (ii) 
. But therein lies the problem. If (i) is true and , then, by definition of 
, 
which is a contradition. If (ii) is true and then, by definition of , 
which is also a contradiction.
Thus, 
cannot be a surjection. 
It kind of reminds of those kinds of logical hurdles such as are inherent with such phrases as the "set of all sets". For example, you might say that there is some set 
that is the set of all sets. Of course, since is a set, then it is an element of itself. So some sets are elements of themselves but clearly there are some sets that are not elements of themselves. For example, the set of all teacups, since elements of this set are teacups and not sets of teacups. Well, if you try to consider the set, 
of all sets that are not elements of themselves, you run into trouble. The trouble is that if is an element of , then it is not an element of . But if is not an element of then it is. Impossible.
Naive set theory leads to some interesting paradoxes. One particularly interesting example an applied form of Russell's paradox (from KurzweilAI.net)
A judge is sentencing a man for a crime that he finds reprehensible and for which he wishes to mete out the most severe sentence. He tells the convicted man not only that he is sentenced to die, but that the sentence is to be carried out in a unique way. "The sentence is to be carried out no later than next Saturday. Furthermore, I want the sentence to be carried out in such a way that on the morning of your execution, you will not know for certain that you are going to be executed on that day. When we come for you, it will be a surprise."
When the judge finishes describing his unusual sentence, the condemned man seems surprisingly pleased and replies, "Well, that's great judge. I am greatly relieved." To this the judge says, "I don't understand. How can you be relieved?"
The man replies, "Well, your honor, in order for your sentence to be carried out, I could not be executed on Saturday." "Why is that?' asks the judge. "Since the sentence must be carried out by Saturday, if we actually get to Saturday, I will know for certain that I am to be executed on that day, and thus it would not be a surprise."
"I suppose you are right," responds the judge. "You cannot be executed on Saturday. I still do not see why you are relieved." "Well," says the prisoner, "if we have definitely ruled out Saturday, then I cannot be executed on Friday either."
"Why is that?'' asks the judge. "We have agreed that I definitely cannot be executed on Saturday. Therefore, Friday is the last day I can be executed. Thus, if Friday rolls around, I will definitely know that I am to be executed on that day, and therefore it would not be a surprise. So I cannot be executed on Friday." "I see," says the judge.
"Thus the last day I can be executed would be Thursday. But if Thursday rolls around, I would know I had to be executed on that day, and thus it would not be a surprise. So Thursday is out. By the same reasoning we can eliminate Wednesday, Tuesday, Monday, and today."
The judge scratches his head as the confident prisoner is led back to his cell. On Thursday, the prisoner is taken to be executed. He is very surprised. So the judge's orders are successfully carried out.