Proving Cantor's Theorem: Non-Existence of a Surjection from a Set to Its Power Set
Cantor's theorem is a fundamental result in set theory that demonstrates the existence of an inherent infinite hierarchy of infinities. This theorem states that for any set A, the power set of A, denoted as PA, which is the set of all subsets of A, has a strictly greater cardinality than A itself. This article will explore a detailed proof that there is no surjection from a non-empty set A to its power set PA, using Cantor's theorem and a clever set-based contradiction.
Statement of the Theorem
For any non-empty set A, there is no function φ: A → PA that is a surjection. This means that there is no way to create a function that maps every element of A to a unique subset of A such that every subset of A is hit at least once.
Proof by Contradiction
To prove the theorem, we proceed by contradiction. Assume that there is a surjection φ: A → PA. This means that for every subset S ? A, there is some element a ∈ A such that φ(a) S.
Defining a Special Subset
Define a subset B ? A as follows:
B {a ∈ A | a ? φ(a)}This set B contains all elements a of A such that a is not an element of the subset that φ maps a to.
Analyzing the Subset B
Since φ is a surjection, there must be some element b ∈ A such that φ(b) B. We will now investigate the membership of b in the set B.
Case 1: b ∈ B
By the definition of B, if b ∈ B, then b ? φ(b). But since φ(b) B, this implies that b ? B. This is a contradiction.
Case 2: b ? B
By the definition of B, if b ? B, then b ∈ φ(b). But since φ(b) B, this implies that b ∈ B. This is also a contradiction.
Conclusion
In both cases, we have arrived at a contradiction. Therefore, our initial assumption that there exists a surjection φ: A → PA must be false.
Thus, we conclude that there is no surjection from a non-empty set A to its power set PA. This completes the proof of Cantor's theorem.
Further Reading
If you're interested in exploring this topic further, you can read more about set theory, power set, and Cantor's theorem. The provided references offer a deeper dive into the subject matter, including detailed proofs and examples to further solidify your understanding.