Теорема Кантора о существовании множеств мощности более континуума
Пусть M - некоторое множество и P (M) - булеан множества M. Тогда |P(M)|>|M|.
Доказательство
Если множество M - конечно и |M|=n, то теорема верна, т.к. |P(M)|= >n.
Очевидно, что для бесконечного множества M выполняется |P(M)| |M|, так как множество P(M) содержит по крайней мере все одноэлементные подмножества из элементов множества M.
Покажем что |P(M)| |M|. Доказательство будем проводить от противного.
Пусть |M|=|P(M)|, т.е. множества M и P(M) эквивалентны, а это означает, что между элементами этих множеств можно установить взаимно однозначное соответствие. Установим такое соответствие:
Элементу a из множества M поставим во взаимно однозначное соответствие множество A - элементы булеана P(M);
элементу в поставим во взаимно однозначное соответствие множество В (элемент множества (M));
элементус - множество С и т.д.
Постоим следующее множество X элементов из M:
для пары соответствующих членов (а,А) элемент амы поместим в множество Xтогда и только тогда, если элемент а не принадлежит множеству А, иэлементамы не поместим в множество X , если апринадлежит множествуА;алогично, элемент впомещаем в множество X , если этот элемент не принадлежит множеству В и не помещаем в множество X , если этот элемент принадлежит множеству В; так по всем элементам множества A.
Так как множество Xбудет состоять из элементов множества M, то это множество является элементом булеана множества M и ему, как и любому другому элементу из множества P(M), должен взаимно однозначно соответствовать некоторый элемент x из множества M.
Покажем, что этого не может быть.
Действительно, если элементxпринадлежит соответствующему ему множеству X, то этот элемент мы в множество Xвключить не должны, если же элемент xне принадлежит множеству X,то мы должны этот элемент включить в множество X.Полученное противоречие доказывает теорему.
Теорема Кантора-Бернштейна.
Пусть А и В произвольные множества. Если в в множестве А есть подмножество эквивалентное множеству В, а в множестве В есть подмножество эквивалентное множеству А, то А и В эквивалентные множества.
Доказательство.
Не уменьшая общности будем считать, что А и В, так как если =А или=В, то теорема верна.
Так как ~В, а B, то найдется множество , такое, что ~.
Так как ~A, а A, то найдется множество
~. Получили, что А~~, B~~.
Продолжая аналогичные рассуждения, получим:
~ , ~ ,при этом ,k=1,2,... .
Отсюда следует, что
\ ~ \ .(1)
Обозначим черезD =A ... .
Тогда
A = D (A\ ) ( \ ) ( \ ) ( \ ) ...=
= D (A\ ) ( \ ) ( \ )... ( \ ) ( \ ) ( \ )... .
= D ( \ ) ( \ ) ( \ ) ...=
=D ( \ ) ( \ ) ( \ )... ( \ ) ( \ ) ... .
Из полученных выражений для A и , а так же из условий (1) следует A~ , что и доказывает теорему.