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

Доказательство 
Предположим, что существует множество , равномощное множеству всех своих подмножеств , то есть, что существует такая биекция , ставящая в соответствие каждому элементу множества  некоторое подмножество множества .

Рассмотрим множество , состоящее из всех элементов , не принадлежащих своим образам при отображении :
 .

Отображение  биективно, а , поэтому существует  такой, что .

Теперь посмотрим, может ли  принадлежать . Если , то , а тогда, по определению , . И наоборот, если , то , а следовательно, . В любом случае, получаем противоречие.

Следовательно, исходное предположение ложно и  не равномощно . Таким образом доказана строгость неравенства.

Для определения знака неравенства построим сюръективное отображение g:  →  , сопоставляющее каждому подмножеству , состоящему из единственного элемента, этот самый элемент из . В  остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что  .

Примечания

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

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

Кантора
Мощность множеств