Теорема Кантора

Предположим, что существует множество ${\displaystyle A}$, равномощное множеству всех своих подмножеств ${\displaystyle 2^{A}}$, то есть, что существует такая биекция ${\displaystyle f}$, ставящая в соответствие каждому элементу множества ${\displaystyle A}$ некоторое подмножество множества ${\displaystyle A}$.

Рассмотрим множество ${\displaystyle B}$, состоящее из всех элементов ${\displaystyle A}$, не принадлежащих своим образам при отображении ${\displaystyle f}$[1]:

${\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}}$.

Отображение ${\displaystyle f}$ биективно, а ${\displaystyle B\subseteq A}$, поэтому существует ${\displaystyle y\in A}$ такой, что ${\displaystyle f(y)=B}$.

Теперь посмотрим, может ли ${\displaystyle y}$ принадлежать ${\displaystyle B}$. Если ${\displaystyle y\in B}$, то ${\displaystyle y\in f(y)}$, а тогда, по определению ${\displaystyle B}$, ${\displaystyle y\not \in B}$. И наоборот, если ${\displaystyle y\not \in B}$, то ${\displaystyle y\not \in f(y)}$, а следовательно, ${\displaystyle y\in B}$. В любом случае, получаем противоречие.

Следовательно, исходное предположение ложно и ${\displaystyle A}$ не равномощно ${\displaystyle 2^{A}}$. Таким образом доказана строгость неравенства.

Для определения знака неравенства построим сюръективное отображение g: ${\displaystyle 2^{A}}$→ ${\displaystyle A}$, сопоставляющее каждому подмножеству ${\displaystyle 2^{A}}$, состоящему из единственного элемента, этот самый элемент из ${\displaystyle A}$. В ${\displaystyle 2^{A}}$ остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что ${\displaystyle |2^{A}|>|A|}$.

• Р. Курант, Г. Роббинс Что такое математика? Глава II, § 4, С. 111—122.

• Диагональный аргумент
• Парадокс Рассела