Proving the Uncountability of the Power Set of a Countable Set

Introduction

In the realm of set theory, one of the most striking results is Cantor's theorem. This theorem states that for any set ( A ), the power set ( mathcal{P}(A) ) has a strictly greater cardinality than ( A ) itself. This means that even if ( A ) is a countable set, ( mathcal{P}(A) ) is still uncountable. In this article, we will delve into a step-by-step proof of this theorem when ( A ) is a countable set.

Step 1: Definition of Countable Set

A set ( A ) is considered countable if it is either finite or countably infinite. For the purposes of this proof, we will focus on the case where ( A ) is countably infinite. The finite case is trivial, as the power set of a finite set is also finite and thus not applicable for our purpose.

Step 2: Assume ( A ) is Countably Infinite

Let us assume ( A {a_1, a_2, a_3, ldots} ), where each ( a_i ) is an element of ( A ).

Step 3: Show that ( mathcal{P}(A) ) is Uncountable

We will demonstrate that it is impossible to list all subsets of ( A ) in a countable manner. To do this, we will assume that ( mathcal{P}(A) ) is countable and derive a contradiction.

Assumption: ( mathcal{P}(A) ) is countable. This implies that all subsets of ( A ) can be listed as ( S_1, S_2, S_3, ldots ).

We will construct a specific subset ( S ) of ( A ) that is not in this list, forming a contradiction.

Constructing the Subset ( S )

Define ( S ) as follows:

For each ( i ), let:

$$ S { a_i in A mid a_i otin S_i } $$

Translationally, ( S ) contains all elements ( a_i ) for which the ( i )-th subset ( S_i ) does not contain ( a_i ).

Determining the Membership of ( S ):

If ( a_i in S ) then by the construction of ( S ), ( a_i otin S_i ) because we included ( a_i ) only if it is not in ( S_i ). Conversely, if ( a_i otin S ) then by the construction ( a_i ) must be in ( S_i ).

Conclusion: In both cases, ( S ) cannot be equal to any subset ( S_i ) from our listing. Therefore, ( S ) is a subset of ( A ) that is not on the list ( S_1, S_2, S_3, ldots ).

Step 4: Contradiction

This leads to a contradiction, as we assumed that we had listed all subsets of ( A ). Therefore, our initial assumption that ( mathcal{P}(A) ) is countable must be false.

Conclusion: Hence, we conclude that if ( A ) is a countable set then ( mathcal{P}(A) ) is uncountable. This proof is a classic result in set theory and demonstrates the richness of the power set compared to its original set.

Summary

This step-by-step proof of Cantor's theorem sheds light on the uncountability of the power set of a countable set. Understanding this concept is crucial for further studies in set theory and mathematical logic.

References

Cantor, G. (1891). iüber eine elementare Frage der Mannigfaltigkeitslehre/i. emM diluted/em., 1, 75-78.