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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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


Доказательство[править | править вики-текст]

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

Ссылки[править | править вики-текст]