Math 4200
To Infinity and Beyond!
Theorem. Suppose A is any set, and P(A) is the collection of all subsets of A. Then there does not exist a function f from A onto P(A). This implies that A and P(A) have different cardinalities; that is, P(A) is strictly larger than A.
Proof:
Suppose there exist a function 
such that f maps
A onto P(A).
Let 
. If f is
an onto function, there exists w in A such that
. Now either 
or 
.
If
then 
and by the definition of S , . This is a logical
contradiction.
If
then 
and by the definition of S , . This is also a
logical contradiction.
In either case we obtained a
contradiction, so our assumption that f maps A onto P(A)
must be false. Therefore there does not exist a function f from A onto P(A).
There is no set whose cardinality is strictly
between that of the integers and that of the real numbers.