WikiSort.ru - Не сортированное

Теорема Кантора — классическое утверждение теории множеств.

Формулировка

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

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

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

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

Ссылки

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