To show that the cardinality of the power set of a countable set is greater than the cardinality of the countable set itself.

Proof: Without loss of generalization, let the countable set be the set ℕ of positive integers. By contradiction, assume that Q is a bijection between ℕ and its power set ℘(ℕ). We can therefore write Q(ℕ) = {Q1, Q2, ..., Qk, ...} and define a set W as follows:

∀k ∈ ℕ, k ∈ W ⇔ k ∉ Qk

We know that W ∈ Q(ℕ), as all of its elements are in ℕ. But we also know that W cannot be in our list, as it differs from each of the Qk's due to the presence or absence of the integer k. A contradiction, and the result is established.

QED

Note: The argument is similar to the diagonalization argument that is used to establish that there are more reals numbers than integers.

We can generalize the above result to all infinite sets, countable or otherwise. Consider the set A of all sets. By definition, all subsets of ℘(A) are in A. But ℘(A) contains more elements than does A, a contradiction.

cactuspear home