Paradoxes of set theory

Naive set theory contains some interesting paradoxes that eventually led to the development of a more detailed set theory. These paradoxes often rely on the fact that in classical, naive, set theory it is possible for a set to contain itself as its element.

Russell's paradox

Among the most famous paradoxes is Russell's paradox. This can be defined as follows: consider the set N, which contains precisely those sets that do not contain themselves as their element. Thus, if a set contains itself as its element, then it does not belong to the set N. If it does not contain itself, then it belongs to the set N.

The question is, does the set N contain as its element the set N, i.e. itself?

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

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

So the paradox is that we always violate one of the conditions. If N ∈ N, then it contradicts the definition of the set N (it contains only sets that do not contain themselves, here obviously N contains N as its element) and if N ∈ N does not hold, then we again violate the definition of N.

So we cannot construct such a set, which should not happen in a proper set theory.

Russell's paradox also has several natural interpretations. For example, the barber's paradox. There is a barber in town who shaves the very people who don't shave themselves. The question is, does the barber shave himself?

Cantor's paradox

Another paradox is Cantor's paradox. This relies on the fact that if we have a set M, then its potency set P(M) (the set of all subsets of the set M) always has a higher cardinality, it is larger. In finite sets this can be seen at a glance, for infinite sets it can be easily proved. This statement, by the way, is called Cantor's theorem, and its exact wording and proof can be found on Wikipedia.

The paradox itself is already simpler than the previous one. Imagine the set of all sets, let us denote it by M. Thus, for any set N, it is true that N ∈ M. But by Cantor's theorem, the cardinality of the power set P(M) is greater than the cardinality of M. But this conflicts with the fact that M contains all sets - if the set P(M) is larger than M, it must necessarily contain elements that the set M does not contain.