Let \(S\) be a set, and let \(P(S ) \) be the power set of \(S\), which is the set of subsets of \(S \).
Suppose that surjects. We define so that is an element of , hence a subset of , and is an element of .
By assumption surjects, so there exists such that .
First, let . Then
so such that . But since , this is a contradiction because , but .
Now let . Then since is not in , cannot be an element of such that . So if , then must also be a member of . But supposing that surjects, there is a such that , which means that , but . This is a contradiction.
We conclude from both cases that cannot surject, because there exists no such that . In other words, for all .
In this note, we have shown that no map from set to its power set can surject, which proves that there exists no bijection from S to its power set. This fundamental result means that for any set S, the set of all subsets of , ,has a strictly greater cardinality than . That