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

Теорема Кантора
Теорема Кантора
Названо в честь	Георг Кантор
Изучается в	теория множеств
	Медиафайлы на Викискладе

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

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

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

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

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\colon A\to 2^{A}$ , сопоставляющее каждому элементу $a$ из $A$ подмножество $\{a\}$ , состоящее из этого единственного элемента. В $2^{A}$ остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что $\left|2^{A}\right|>|A|$ .