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).


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.