The power set of a countably infinite set is uncountably infinite.
Understanding Countable and Uncountable Sets
Before diving into the power set, let's clarify the terms:
- Countably Infinite Set: A set whose elements can be put into a one-to-one correspondence with the set of natural numbers (1, 2, 3, ...). Examples include the set of integers and the set of rational numbers.
- Uncountably Infinite Set: A set that is infinite but cannot be put into a one-to-one correspondence with the natural numbers. A classic example is the set of real numbers.
The Power Set
The power set of a set S is the set of all possible subsets of S, including the empty set and S itself. For example:
| Set (S) | Power Set (P(S)) |
|---|---|
| {a} | { {}, {a} } |
| {a, b} | { {}, {a}, {b}, {a, b} } |
| {a, b, c} | { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } |
Key Observation
Notice that the size (cardinality) of the power set grows much faster than the size of the original set.
Power Set of a Countably Infinite Set
Cantor's theorem, a fundamental result in set theory, states that for any set S, the power set of S (denoted as P(S)) has a greater cardinality than S itself. This means that if a set is countably infinite, its power set is not only infinite but also uncountably infinite.
According to the provided reference:
In particular, Cantor's theorem shows that the power set of a countably infinite set is uncountably infinite. The power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers (see Cardinality of the continuum).
Let's consider the set of natural numbers, ℕ = {1, 2, 3, ...} which is a countably infinite set.
-
The power set of ℕ, denoted by P(ℕ), includes all possible subsets of ℕ. This includes sets like:
- { } (the empty set)
- {1}
- {1, 2}
- {2, 4, 6}
- {1, 3, 5, 7...} (the set of odd numbers)
- The full set of natural numbers {1, 2, 3...} itself.
- All other possible subsets.
-
Cantor's theorem states that the cardinality of P(ℕ) is strictly larger than the cardinality of ℕ.
-
The power set of the natural numbers, P(ℕ) is uncountably infinite.
-
Furthermore, P(ℕ) has the same cardinality as the set of real numbers (ℝ), known as the cardinality of the continuum.
This establishes that the power set of any countably infinite set, not just the natural numbers, is always uncountably infinite. This uncountably infinite set is larger than the original countably infinite set.
