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

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

Множество бесконечных последовательностей нулей и единиц несчетно.

Предположим, что оно счетно. Тогда все последовательности нулей и единиц можно перенумеровать: Составим бесконечную вниз таблицу, строками которой будут наши последовательности:

(через мы обозначаем -й член -й последовательности). Теперь рассмотрим последовательность, образованную стоящими на диагонали членами , , , ; ее -й член есть и совпадает с -м членом -й последовательности. Заменив все члены на противоположные, мы получим последовательность , у которой

так что последовательность отличается от любой из последовательностей (в позиции ) и потому отсутствует в таблице. А мы предположили, что таблица включает в себя все последовательности - противоречие.

Теорема 3 (обобщенная теорема Кантора).Для любого множества А имеет место неравенство < (Никакое множество не равномощно множеству всех своих подмножеств).

Доказательство.Докажем, что Построим вложение А в Р(А): . Очевидно, что f - искомое вложение.

Докажем, что между А и Р(А) не существует биекции. Доказываем от противного. Допустим, что существует биекция F: A®P(A). Отметим, что для каждого хÎА F(х)ÍA, поэтому для каждого хÎA уместно поставить вопрос: хÎF(x) или хÏF(x)?

Элемент х назовем «хорошим», если хÎF(x). Пусть - множество всех «плохих» элементов из А. Так как F по допущению есть отображение «на», то существует х₀ÎА такой, что F(х₀)=Х₀. Возникает вопрос, х₀-«плохой» или «хороший»?

Если х₀ «хороший», то х₀ÎF(x₀), значит х₀ÎX₀, то есть х₀ÏF(x₀) и х₀ «плохой». Противоречие. Значит х₀ не может быть «хорошим». Ему остается быть «плохим», то есть х₀ÏF(x₀), поэтому х₀ÎX₀, значит х₀ «хороший». Снова противоречие. Итак, допущение о существовании биекции между А и Р(А)приводит к противоречию. Поэтому < .

Эта теорема показывает, что для любого сколь угодно большого множества А существует множество В, мощность которого строго больше А. То есть последовательность мощностей ничем не ограничена.