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

У этого термина существуют и другие значения, см. Теорема Кантора (значения).

Теорема Кантора — классическое утверждение теории множеств. Доказано Георгом Кантором в 1891 году. Утверждает, что любое множество ${\displaystyle A}$ менее мощно, чем множество всех его подмножеств ${\displaystyle 2^{A}}$.

Теорема Кантора
Названо в честь	Георг Кантор
Изучается в	теория множеств
Медиафайлы на Викискладе

Доказательство

Предположим, что существует множество ${\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}}$. Таким образом доказана строгость неравенства.

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