Треп о математике 2.4

Sergei Nickolaev написал(а) к All в May 23 23:19:16 по местному времени:

Привет, All!

Продолжаем говорить о мощностях: теорема Кантора.
Сформулируем ее так:
Множество бесконечных последовательностей нулей и единиц несчётно.

Предположим, что оно счётно. Тогда все последовательности нулей и единиц можно перенумеровать: a0, a1, . . . Составим бесконечную вниз таблицу, строками которой будут наши последовательности:
a0 = a00 a01 a02 . . .
a1 = a10 a11 a12 . . .
a2 = a20 a21 a22 . . .
. . . . . . . . . . . .
(через aij обозначаем j-й член i-й последовательности)
Теперь рассмотрим последовательность - диагональ этой таблицы:
a00 a11 a22 . . .
Сделаем из нее другую последовательность, заменив все члены ее на противоположные (то есть нули заменим на единицы, а единицы на нули):
Последовательность b = b1 b2 b3 . . . (bi = 1-aii) отличается от любой последовательности ai (в i-ой позиции гарантированно, так как bi <> aii), значит последовательности b нет в нашей таблице. Получили противоречие с предположением о счетности множества последовательностей нулей и единиц, теорема доказана.

Мы раньше уже доказывали, что множество таких последовательностей равномощно множеству вещественных чисел, теперь доказали, что множество вещественных чисел несчетно и его мощность больше мощности натурального ряда.
Множество бесконечных последовательностей нулей и единиц однозначно сопоставляется с множеством характеристических функций подмножеств натурального ряда, получаем, что множество всех подмножнств натурального ряда несчетно и равномощно множеству вещественных чисел.

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

А именно - множество алгебраических уравнений с целыми коэффициентами очевидно счетно, число корней у такого уравнения конечно (не больше, чем степень уравнения), значит множество алгебраических чисел - счетно. Значит множество не алгебраических (трансцендентных) чисел не только не пусто, но и бесконечно (и равномощно множеству вещественных чисел).
К тому времени, когда Кантор опубликовал свою знаменитую теорему (1874 год, кстати, это была первая публикация по теории множеств), примеры трансцендентных чисел уже были известны (1844 год, французский математик Ж. Лиувилль), но доказательство было существенно сложнее ...

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

Общая формулировка теоремы Кантора:
Никакое множество X не равномощно множеству всех своих подмножеств.

(Для пустого множества - очевидно, дальше будем считать, что X - непусто).

Предположим, что это - не так, тогда имеется функция f задающая взаимно-однозначное соответствие между множеством X и множеством его подмножеств P(X). Каждому элементу x множества X сопоставлен f(x) - элемент множества P(X) (какое-то подмножество множества X).

Какие-то x будут принадлежать сопоставленным им подмножествам, какие-то не будут. (Тот, которому сопоставлено все множество X - будет; тот, которому сопоставлено пустое множество - не будет)

Выберем все x, которые не принадлежат сопоставленным им подмножествам. Они сами составляют некоторое подмножество множества X. Обозначим это подмножество Z.
Теперь покажем, что подмножеству Z не сопоставлен никакой элемент множества X (тем самым получим противоречие с предположением, что у нас есть взаимно-однозначное соответствие элементов и подмножеств!).
Предположим, что такой элемент есть и пусть z - элемент множества X, сопоставленный подмножеству Z. То есть Z=f(z).
Получаем: (z принадлежит Z) <=> (z не принадлежит f(z)) <=> (z не принадлежит Z) - противоречие, значит элемента, сопоставленного Z не имеется и не существует взаимно-однозначного соответствия между X и P(X). Ура!
(Примечание: первая эквивалентность - по построению подмножества Z, вторая - из того, что f(z)=Z).

Заметим, что любое множество X равномощно некоторой части P(X) (например, состоящей из одноэлементных подмножеств), поэтому получаем: мощность P(X) больше мощности X.

Обратите внимание на то, что ни в формулировке, ни в доказательстве не требуется, чтобы множество X было бесконечным. Работает для всяких множеств!

Тут же задачка: докажите, что n < 2^n для любых натуральных n. :-)

Мощность множества X обычно обозначается, как |X|.
Обозначим множество натуральных чисел N.
Получаем бесконечную иерархию кардиналов:
|N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ...

Почему иерархия кардиналов этим не исчерпывается и про арифметику кардиналов - в другой раз.

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)