Limits of Logic #1: Cantor's Theorem
1.5.3 Exercise: Cantor's Theorem
For any set , there is no onto function from to .
Proof:
Consider a function and assume for contradiction that it is an onto function. That means, for any subset , there is some such that .
Consider .
Since is an onto function (by assumption), there is some such that .
Now, either or .
If , then by the criteria of membership in , we have that which is a contradiction.
If , then by the criteria of membership in , we have that which is a contradiction.
And so, there is no such such that , which implies that is not onto, and this contradicts our assumption.
Therefore, there is no onto function from a set to its power set .
This is a theorem about how sets work, fundamentally. Particularly, it is expressing a fact about sizes of sets -- a set is always smaller than its power set.
Why is this theorem interesting?
The theorem is immediately interesting because it expresses that the power set operation on any set takes us to another set that is strictly larger than the original one. This takes us to different sizes of infinities. For example, the set of natural numbers is infinite, which means its powerset is of an even larger infinite size.
But there's something interesting beyond just moving to larger and larger sets. Sometimes we care about two things thing-1 (with set representation ) and thing-2 (with set representation ) where the fact that there's always something "left over" in thing-2 when mapping to it from thing-1 expresses an interesting fact about the non set theoretic relationship between the two things.
1.5.4 Example: Undefinable Sets
Let be a set of strings of symbols. Let be a set of "descriptions" ( ).
Any is a "description" such that for any string , is either "true of" or not.
Call a set of strings is definable if and only if there is some such that is "true of" all .
A consequence of Cantor's theorem is that there'll always be some set of strings that is undefinable.
Consider any function and not that since , the function cannot be onto.
Now let be such that for , such that is "true of" all . Therefore, the range of is the set of all definable sets of strings. Since cannot be onto, there is always some that is not definable.
And so, we can immediately draw an interesting conclusion about (this informal sense of) definability and truth from Cantor's theorem. There is at least one set of strings such that no one description is true of all strings of that set -- an undefinable set.
Of course, there is much more to say about truth, definability, the set of all strings and their formal senses. That said, the example's strngth has nothing to do with considering a set of strings, or the "true of" relation. The example can be stated in a generic form.
Let be a non-empty set. For any two place relation , call an definable iff there is some such that for all . There will always be some undefinable subset .
It's also interesting to relate Cantor's theorem to Russell's paradox. Informally stated as the "barber paradox":
The barber shaves all men in the community who do not shave themselves, and only them.
Now, does the barber shave himself? If yes, then the barber does shave someone who shaves himself -- a contradiction. If no, then the barber does not shave all men who do not shave themselves -- a contradiction as well.
Therefore, our statement cannot be true. This gives us Cantor's theorem when we consider the statement as a stand-in for a set
where is the set of "all men in the community" and the function takes a man in the community to the set of men that he shaves . This makes the set of all men who only shave those who don't shave themselves.
Is it a paradox that exists? No, the existence of is not a paradox; it simply expresses that the "shaves" relation (or any function from a set to the power set) is not onto -- Cantor's theorem.