Paradoxes of set theory

Naive set theory contains some interesting paradoxes, which eventually led to the development of a more careful set theory. These paradoxes often rely on the fact that in classical, naive set theory a set can contain itself as an element.

Russell’s paradox

One of the best-known paradoxes is Russell’s paradox. We can state it like this: take a set N that contains exactly those sets that do not contain themselves as an element. So if a set contains itself as an element, it does not belong to N. If it does not contain itself, it does belong to N.

The question is: does the set N contain the set N as an element, that is, does it contain itself?

By considering the cases we find that if N does not contain N, then it is a set that does not contain itself and should be in N, so N ∈ N should hold.

But if N does contain N as an element, then N ∈ N should not hold, because N contains only those sets that do not contain themselves as an element.

The paradox is that we always break one of the conditions. If N ∈ N, this contradicts the definition of N (it contains only sets that do not contain themselves, and here N clearly contains N as an element), and if N ∈ N does not hold, we again break the definition of N.

So we can’t build such a set, which should not happen in a sound set theory.

Russell’s paradox also has several everyday versions. One is the barber paradox. In a town there is a barber who shaves exactly those people who do not shave themselves. The question is: does the barber shave himself?

Cantor’s paradox

Another paradox is Cantor’s. It relies on the fact that if we have a set M, then its power set P(M) (the set of all subsets of M) always has a higher cardinality – it is bigger. For finite sets this is obvious at first sight, and for infinite sets it can be proved easily. This statement is known as Cantor’s theorem, and you can find its exact wording and proof on Wikipedia.

The paradox itself is simpler than the previous one. Imagine the set of all sets, and call it M. So for any set N we have N ∈ M. But by Cantor’s theorem, the cardinality of the power set P(M) is greater than the cardinality of M. That contradicts the fact that M contains all sets – if P(M) is bigger than M, it must contain elements that M does not.