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

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

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

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

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

Предположим, что существует множество A, равномощное множеству всех своих подмножеств 2^A, то есть что есть биекция f, ставящая в соответствие каждому элементу множества A некоторое подмножество множества A. Рассмотрим множество f биективно, а , поэтому существует такой, что f(y) = B. Теперь посмотрим, может ли y принадлежать B. Если , то , а тогда, по определению B, . И наоборот, если , то , а следовательно, . В любом случае, получаем противоречие. Следовательно, исходное предположение ложно и A не равномощно 2^A.

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

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

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