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

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

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

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

Предположим, что существует множество A, равномощное множеству всех своих подмножеств 2A, то есть что есть биекция f, ставящая в соответствие каждому элементу множества A некоторое подмножество множества A. Рассмотрим множество B=\left\{\,x\in A : x\not\in f(x)\,\right\}. f биективно, а B \subseteq A, поэтому существует y \in A такой, что f(y) = B. Теперь посмотрим, может ли y принадлежать B. Если y \in B, то y \in f(y), а тогда, по определению B, y \not\in B. И наоборот, если y \not\in B, то y \not\in f(y), а следовательно, y \in B. В любом случае, получаем противоречие. Следовательно, исходное предположение ложно и A не равномощно 2A. Заметим, что 2A содержит подмножество, равномощное A (например, множество всех одноэлементных подмножеств A), а тогда из только что доказанного следует | 2A | > | A |

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home