Russell's Paradox and Cantor's Theorem

Russell's paradox asks whether the "set" R defined by

R = {x: x is not an element of x}

is an element of itself. As it was mentioned in a previous article, Russell's solution to his paradox was his theory of types. He arranged all propositions into a hierarchy. The lowest level of the hierarchy consisted of propositions about individuals, not sets. The next lowest level consisted of propositions about sets of individuals. The next lowest level consisted of propositions about sets of sets of individuals, and so on. Thereby the definition (one of these "valid" propositions) of any set only referred to objects of the same "type" (at the same level).

It seems that Russell discovered the paradox as a result of his analysis on Cantor's theorem on the cardinality (i.e. the "number of elements") of the power set (i.e. the set of all subsets) of a set. In the following discussion, let P(A) denote the power set of a set A. Furthermore, some common axioms of the set theory are assumed.

Cantor considered if there was uncountable set. A infinte set is countable if it can be put into one-to-one correspondence with the set ℕ of all natural numbers. For example the set of all even numbers is countable (considering the mapping that maps a natural number n to 2n), so that the set of all even number has the same cardinality (the same "number of elements") as ℕ. A infinite set is said to be uncountable if it is not countable. Cantor considered the set of all infinite sequences of elements that were either 0 or 1. For instance (0, 0, 0, ...) is one of these sequences. Clearly, it is infinite. Cantor used his diagonal argument to prove that this set is uncountable. That is, any mapping from ℕ to this set cannot be a one-to-one correspondence. Let this set be denoted by S. Consider any mapping f: ℕ → S. Then for each natural number n, we have a sequence f(n), and we denote it by (f(n)₀, f(n)₁, f(n)₂, ...). Along the diagonal, we then have a sequence (f(0)₀, f(1)₁, f(2)₂, ...). Cantor obtained a sequence (a₀, a₁, a₂, ...) in S such that a_n ≠ f(n)_n for each natural number n (if f(n)_n is 0, then a_n is taken to be 1). Thereby this sequence is different from f(n) for every natural number n. Hence, S is uncountable.

With this argument, Cantor had actually proved that P(ℕ), the power set of ℕ, was uncountable. In fact the set S is in one-to-one correspondence with P(ℕ) - for a sequence (a₀, a₁, a₂, ...) in S, consider the subset A of ℕ such that A contains n if (and only if) a_n = 1. Thus we can "translate" the diagonal argument as follows. Consider any f: ℕ → P(ℕ). Then for each natural number n, we have a set f(n) of natural numbers, so that we can ask if f(n) contains a given natural number m. Thus we can define a set A such that A contains a natural number n if and only if f(n) does not contains n. That is,

A = {n ∈ ℕ: n ∉ f(n)}.

Then for any natural number n, A ≠ f(n). That is, f is not surjective. Hence, P(ℕ) is uncountable.

It is clear that in the above argument ℕ can be replaced by any non-empty set, and we can conclude that there is no surjection from a set to its power set.

It follows immediately that there does not exist a set of all sets. Otherwise, if U was a set of all sets, then P(U) would be a subset of U, and we would have a trivial surjection f: U → P(U) such that f(x) = x for all x belonging to P(U), and f(y) was any subset of U, such as the empty set, for all y not belonging to P(U). It then leads to a contradiction that for all x ∈ U, f(x) ≠ A, where

A = {x ∈ U: x ∉ x}.

It is in fact Russell's paradox.