Understanding the Power Set and Its Infinite Nature

The concept of the power set of a set and its infinite nature is a fundamental topic in set theory and has profound implications in understanding the limits of countability. This article will delve into the intricacies of the power set and explain why it is uncountable for infinite sets, using the powerful Cantor diagonal method.

Introduction to Power Sets

A power set of a set A, denoted as PA, is the set of all possible subsets of A. For a finite set A with N elements, the power set PA is finite and contains exactly 2N elements. This includes the set itself and the empty set. However, for an infinite set, specifically a countably infinite set like the set of all natural numbers, the power set is uncountable.

Countability of Finite and Infinite Sets

Let us consider the nature of countable and uncountable sets. A set is finite if it has a finite number of elements. The power set of a finite set is also finite, with a cardinality of 2N. On the other hand, an infinite set, such as the set of all natural numbers, is countably infinite if its elements can be put into a one-to-one correspondence with the set of natural numbers. For such sets, their power sets are uncountable, meaning that they cannot be put into a one-to-one correspondence with the natural numbers.

The Cantor Diagonal Method

The power set of a countably infinite set like the natural numbers is uncountable, and this is rigorously proven using the Cantor diagonal method. This ingenious method helps demonstrate that no function can map a countably infinite set onto its power set, meaning the power set is not only uncountable but also strictly larger in size.

Assumption: Suppose there exists a function f that maps each natural number n to a subset of the natural numbers, denoted as fn.

Denote An for each n as the subset corresponding to n under f. Represent An by a binary sequence where each term anj is 1 if j is in An and 0 if j is not in An.

Now, construct a new subset B of natural numbers as follows:

If anj is 1, set bnj 0. If anj is 0, set bnj 1.

Clearly, the subset B differs from every An in at least one position, specifically the position corresponding to n. This means B is not in the image of the function f, as it differs from each An by definition.

Therefore, f cannot be onto, and the power set of the natural numbers is uncountable.

Implications and Variations

This theorem holds under the assumption of unrestricted comprehension in set theory. However, variations of set theory, such as Quine’s New Foundations (NFU), allow for the existence of a set of all sets by requiring that comprehensions be stratified, i.e., no self-referential definitions. In these systems, the power set can be larger than the set itself.

In NFU, the set of all sets includes the set of all sets, but the power set of the set of all sets is not provably as large as the set itself. This differentiates the behavior of sets in unrestricted comprehension systems from more conservative or computationally oriented systems.

Conclusion

The power set of an infinite set, particularly a countably infinite set, is uncountable, as shown by the Cantor diagonal method. Understanding this concept is crucial for grasping the limits of countability in set theory and the fundamental differences between finite and infinite sets. This knowledge has implications in various fields, including computer science, where self-referential definitions play an important role.