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

{{#if: | }} Шаблон:Карточка теоремы Теорема Кантора — классическое утверждение теории множеств. Доказано Георгом Кантором в 1891 году. Утверждает, что любое множество <math>A</math> менее мощно, чем множество всех его подмножеств <math>2^A</math>.

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

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

Рассмотрим множество <math>B</math>, состоящее из всех элементов <math>A</math>, не принадлежащих своим образам при отображении <math>f</math><ref>Оно существует по аксиоме выделения, значение есть подмножество <math>A</math>.</ref>:

<math>B=\left\{\,x\in A : x\not\in f(x)\,\right\}</math>.

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

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

Следовательно, исходное предположение ложно и <math>A</math> не равномощно <math>2^A</math>. Таким образом доказана строгость неравенства.

Для определения знака неравенства построим инъективное отображение <math>g\colon A \to 2^A</math>, сопоставляющее каждому элементу <math>a</math> из <math>A</math> подмножество <math>\{a\}</math>, состоящее из этого единственного элемента. В <math>2^A</math> остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что <math>\left|2^A\right|>|A|</math>.

Ссылки

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

См. также

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