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

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

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

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

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

$B=\{x\in A:x\in ̸f(x)\}$.

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

Теперь посмотрим, может ли $y$ принадлежать $B$. Если $y\in B$, то $y\in f(y)$, а тогда, по определению $B$, $y\in ̸B$. И наоборот, если $y\in ̸B$, то $y\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.

См. также

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