Set Theory Proof

Here's a proof that I have always found fascinating.

Theorem: Given any set A, the power set of A has strictly larger cardinality than A.

For two sets to have the same cardinality, there must exist a bijection between the two sets. So, let us assume that there exists such a bijection between A and P(A), denoted f:A->P(A).

For each x in A, either x is in f(x) or x is not in f(x). Consider the subset S of A defined as
S = {x in A | x is not in f(x)}.

Since we have assumed that f:A->P(A) is a bijection and S is in P(A), then there exists some t in A such that f(t) = S.

Either t is in S or t is not in S. Suppose t is in S. Then t satisfies the condition that t is not in f(t) which is S. Therefore t is not in S. Suppose t is not in S. Then t does not satisfy the condition, and t is in f(t)=S. Therefore t is in S.

So in either case, we arrive at the contradiction that t is in S and simultaneously t is not in S. The source of the contradiction is the assumption that there exists a bijection f:A->P(A). Therefore, there exists no such bijection and the cardinality of P(A) is not the same as the cardinality of A. Since the cardinality of P(A) cannot be smaller than the cardinality of A, the conclusion is that P(A) has strictly larger cardinality than A. (Q.E.D.)