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

---

Теорема Кантора — классическое утверждение теории множеств. Доказано Георгом Кантором в 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 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}}$. Таким образом доказана строгость неравенства.

---