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

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

В теории множеств теорема Кантора гласит, что

Любое множество менее мощно, чем множество всех его подмножеств.

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

Предположим, что существует множество $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$.

Заметим, что $2^A$ содержит подмножество, равномощное $A$ (например, множество всех одноэлементных подмножеств $A$), а тогда из только что доказанного следует $|2^A|>|A|$.

Ссылки

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