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

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

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

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

Рассмотрим множество $B$, состоящее из всех элементов $A$, не принадлежащих своим образам при отображении $f$:

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

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

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

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

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

Ссылки

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

См. также

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