Russell's Paradox
Russell's Paradox is an important result from set theory that uncovers the fact that the naive formulation of set theory, where the sets are freely defined, directly lead to a contradiction.
Let's first explore what this formulation of set theory might be.
A set is a mathematical object. The central question that can be asked of a set is whether another mathematical object belongs to it.
If so, it is said that the latter object is an element of the set.
Examples of sets may be given as:
A = {1} → the set of the number one
B = {car, ball} → the set of “car” and “ball”
C = {pug, dalmatian, ...} → the set of dog breeds
Notice that a membership criterion may be provided, instead of enumerating every element, as shown in “C” above.
Let's turn our attention to this example of set definition:
D = {x ∈ ℕ | x mod 2 = 0}
The set “D” is the set of all natural numbers (x ∈ ℕ) that satisfy the condition of having the remainder of division by 2 to be equal to zero (x mod 2 = 0).
In other words, D is the set of all even numbers.
What Russell realized was that, under these unrestricted conditions, one could formulate a set defined with the following membership criterion:
E = {the set of all sets that don't contain themselves}
So, do A, B, C, D belong to E?
Since they don't contain themselves, yes, A, B, C, D are elements of E.
But, for the harder question, does E contain itself?
Let's take this question in two parts.
(i) Let's assume that the proposition is true, E contains itself. But notice that, according to E's own definition, E shouldn't contain itself, which is a contradiction. Therefore we couldn't have assumed that E contains itself.
(ii) Let's assume that E isn't an element of itself. Take notice again that, given E definition and membership criterion, E should be an element of itself, which is again a contradiction. So, we couldn't have assumed that E isn't an element of itself!
Therefore, given both (i) and (ii) are false, we can't affirm either to be true: E is an element of itself; and E is not an element of itself. This is plainly a contradiction.
Through this counter-example, what Russell demonstrates is that a naive set theory, thusly formulated, by putting no limits on how sets might be defined, leads to a contradiction.
Therefore, a more careful and restrictive set of axioms is required to arrive at a sound theory of sets.