2014-02-09
5180
Теорема Кантора
Множество бесконечных последовательностей нулей и единиц несчетно.
Предположим, что оно счетно. Тогда все последовательности нулей и единиц можно перенумеровать: 
Составим бесконечную вниз таблицу, строками которой будут наши последовательности:
(через 
мы обозначаем 
-й член 
-й последовательности). Теперь рассмотрим последовательность, образованную стоящими на диагонали членами 
, 
, 
, 
; ее -й член есть 
и совпадает с -м членом -й последовательности. Заменив все члены на противоположные, мы получим последовательность 
, у которой
так что последовательность отличается от любой из последовательностей 
(в позиции ) и потому отсутствует в таблице. А мы предположили, что таблица включает в себя все последовательности - противоречие.
Теорема 3 (обобщенная теорема Кантора). Для любого множества А имеет место неравенство 
< 
(Никакое множество 
не равномощно множеству всех своих подмножеств).
Доказательство. Докажем, что 
Построим вложение А в Р (А): 
. Очевидно, что f - искомое вложение.
Докажем, что между А и Р (А) не существует биекции. Доказываем от противного. Допустим, что существует биекция F: A®P (A). Отметим, что для каждого х Î А F (х) ÍA, поэтому для каждого х Î A уместно поставить вопрос: х Î F (x) или х Ï F (x)?
Элемент х назовем «хорошим», если х Î F (x). Пусть 
- множество всех «плохих» элементов из А. Так как F по допущению есть отображение «на», то существует х0 Î А такой, что F (х0) =Х0. Возникает вопрос, х0 -«плохой» или «хороший»?
Если х0 «хороший», то х0 Î F (x0), значит х0 Î X0, то есть х0 Ï F (x0) и х0 «плохой». Противоречие. Значит х0 не может быть «хорошим». Ему остается быть «плохим», то есть х0 Ï F (x0), поэтому х0 Î X0, значит х0 «хороший». Снова противоречие. Итак, допущение о существовании биекции между А и Р (А)приводит к противоречию. Поэтому 
< .
Эта теорема показывает, что для любого сколь угодно большого множества А существует множество В, мощность которого строго больше А. То есть последовательность мощностей ничем не ограничена.
