Cantor's theorem

See power set.

"There exists no surjection from A onto P(A)."

Let f be a map from set A to its power set P(A). Then f:AP(A) is not surjective.

Proof

Let B={xA:xf(x)}
BP(A) because BA.
If f is surjective, then there exists some ξA such that f(ξ)=B.
By the definition of B, ξBξf(ξ).
This is a contradiction, since f(ξ)=B if f is surjective.
Therefore, f is not surjective.

QED

Powered by Forestry.md