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

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

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

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

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

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

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

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

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

Примечания

Ссылки

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

См. также

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