Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2001/ia/paper-4/1e/a/solution

Suppose were a surjection onto the power set of the set . Form the subset
Surjectivity would give with . But then holds exactly when , a contradiction. Hence no such surjection exists, and in particular there is no bijection between a set and its power set. This is the diagonal construction in Cantor's theorem; it also covers the empty set, whose power set has one element.

New to topics? Read the docs here!