power set

The power set of a set A is the set 2^A (PA is used in some textbooks) of all its subsets: 2^A={B:B⊆A}. For finite sets, if |A|=n (A has n elements) then |2^A|=2ⁿ. This explains the funny symbolism we picked.

For infinite sets a special axiom is needed to guarantee its existence (as a set). A problem arises, though: Even for the smallest infinite set ℵ₀ (we adopt the usual set theory convention that the cardinal number is itself a set of its cardinality) we have no full understanding what all its subsets are! The set ℵ=2^ℵ₀ has the cardinality (also denoted c) of the continuum (the set of real numbers).

The continuum hypothesis (CH) is that 2^ℵ₀=ℵ₁ (the second infinite cardinal). The generalised continuum hypothesis (GCH) is that 2^ℵ_k=ℵ_k+1. Paul Cohen proved that (if set theory is consistent; see is mathematics consistent?) each is independent of the Zermelo Fraenkel axioms (ZF) of set theory, even with the axiom of choice (ZFC).

As an addition to ariels' pretty comprehensive writeup, I feel an explanation in simpler terms of the power set is needed for us with a mere mortal's grasp of mathematics.

As written above, the power set contains every possible subset of one set. The simplist example of this is using the set {0,1}. Here, there are four possible sets - {0}, {1}, {0,1} and {} - the last being an empty set, present as a member in all sets. Therefore the power set for {0,1} contains these four subsets, e.g. { {0},{1},{0,1}, {} }.

Cardinality comparison

The cardinality c of the real numbers is less than or equal to the cardinality of the power set of the positive integers. It's easy to show the 'less than or equal to' bit, and a little bit more difficult to show that, as ariels said above, the two cardinalities are in fact equal. By way of illustration, I'll create a function from the power set of the naturals to the reals and show that not every subset of the naturals has a unique real number to pair with it, then show that this doesn't affect the cardinality comparison.

The function

Let f be a function from P(Z+) (the power set of the natural numbers, i.e., the positive integers) to [0,1] (the real numbers from 0 to 1 inclusive) defined by the following. Let R be a subset of the naturals. Then R = {r1*1, r2*2, r3*3, ...} \ {0} where ∀ i, r_i ∈ {0, 1}. Let f(R) = r1*2^(-1) + r2*2^(-2) + r3*2^(-3) + ..., so f(R) ∈ [0, 1]. Now we try to show that f is one to one and onto (a bijection).

Onto

Let r ∈ [0, 1]. Then r has a binary representation, i.e., r = 0.a1a2a3... = a1*2^(-1) + a2*2^(-2) + a3*2^(-3) + ... (where each a_i is a 'binary digit', either 0 or 1). Let K = {a1*1, a2*2, a3*3, ...} \ {0}. Then K is a subset of the naturals. So ∀ r ∈ [0, 1], there exists a subset K of the naturals such that f(K) = r, thus f is onto.

One to one

Consider the sets A = {1} and B = {2, 3, 4, 5, ...}. f(A) = 0.1 (binary), while f(B) = 0.01111.... As real numbers, f(A) = f(B), but A != B. So f is not one to one.

So this function is not one to one and thus not a bijection. Since it is onto, however, c is no bigger than (and perhaps smaller than) |P(Z+)|.

Fixing the comparison

As ariels mentioned to me, the only 'problem' is with the geometric series pairs (i.e., any real in [0, 1] which has a finite representation in binary and its geometric series equivalent form), and there are only a countable number of these. So the original function can be made into a bijection by considering P(Z+) \ 'the set of finite subsets of Z+' -> (0, 1] (note that we cannot include 0 because it has only a finite binary expansion). Now the function is a bijection between uncountable sets. 'The set of finite subsets of Z+' is countable, so adding that set back in does not increase the cardinality of either uncountable set, therefore c is equivalent to |P(Z+)|.

---

Many thanks to jrn for taking issue with several mistakes that were present in this writeup. If any others are discovered, please let me know and I'll do my best to fix them.