Cantor's theorem
For any set there is no bijection : the diagonal set is never in the image of a map .
Theorem 6.15
For any set , there is no bijection from to .
Proof
Given any map , consider
Then , but does not belong to the image of : for every the sets and differ at the element , so for all . Hence is not surjective.
Remarks
-
The construction is reminiscent of Russell’s paradox.
-
There is no universal set. Suppose were universal; then , giving a surjection and contradicting the theorem.
Related
Stated in
- Theorem 6.15§6 Countability