nLab Cantor's paradox

Idea

Cantor's Paradox is a paradox of naïve set theory based on an observation of Bertrand Russell that is similar to, but predates, Russell's Paradox. Like Russell's Paradox, it is essentially about diagonalisation? and Cantor's Theorem.

Argument

Assume a set $V$ of all sets, and consider the power set $\mathcal{P}V$. Since every element of $\mathcal{P}V$ is a set, $\mathcal{P}V$ is a subset of $V$. In particular, we have an injection $\mathcal{P}V \hookrightarrow V$, which contradicts the conclusion of Cantor's Theorem.

History

Cantor's Paradox may be credited to Georg Cantor, because he considered its implications before Russell did; however, he did not view it as a paradox, but merely a demonstration that the collection of all sets was an ‘inconsistent multiplicity’. (That is also the usual modern view, if we interpret Cantor's inconsistent multiplicities as proper classes.)

The argument above is a little opaque, because it relies on Cantor's Theorem, which must be proved as well to complete the argument. However, if one applies the (constructive!) proof of Cantor's Theorem to Cantor's Paradox and evaluates all of the definitions involved, then one ends up with the set $\{x \;|\; x \notin x\}$ of Russell's Paradox; this is precisely what Russell himself did to develop his paradox. That paradox is now the usual go-to paradox to demonstrate the inconsistency of naïve set theory, especially material set theory.

Related concepts

• Russell's paradox

• Burali-Forti's paradox

category: paradox