Лекция дискрет 06

Th.1.4.8 (Обобщённая теорема Кантора) Для любого множества мощность его булеана больше, чем мощность самого множества

Доказательство Th.1.4.8

0.Рассмотрим первое требование определения. Для произвольного множества М

очевидно, что оно равномощно некоторому подмножеству своего булеана, а именно самому себе, так как M B (M).

1.Для рассмотрения второго требования определения допустим, что существует множество M такое, что M B (M). Тогда существует взаимно однозначное соответствие f: M B (M), которое каждому элементу x M ставит в

соответствие некоторое множество B B (M).

2.Рассмотрим множество B тех элементов x M, которые не принадлежат своим образам при соответствии f, то есть B = { x M: x Char(x) } M

3.Соответствие f – взаимно однозначное, т.е. сюръективное, B B (M), значит,

существует y M, которому соответствует множество B, т.е. Char(y) = B.

4.Возможны два случая: B = , B ≠ .

5.Рассмотрим первый случай: B = . Очевидно, что в силу свойств пустого множества y B (= ). Но тогда y Char(y) и, по определению множества В, y B (= ). Это противоречие опровергает возможность B =

1.Для рассмотрения второго требования определения допустим, что существует множество M такое, что M B (M). Тогда существует взаимно однозначное соответствие f: M B (M), которое каждому элементу x M ставит в соответствие некоторое множество BB (M).

2.Рассмотрим множество B тех элементов x M, которые не принадлежат своим образам при соответствии f, то есть B = { x M: x Char(x) } M

3.Соответствие f – взаимно однозначное, т.е. сюръективное, BB (M), значит,

существует y M, которому соответствует множество B, т.е. Char(y) = B.

………………….

Случай B = рассмотрели, осталось рассмотреть B ≠

6.Допустим, y B. Тогда y Char(y) и, по определению множества B, y B.

7.Допустим, y B. Тогда y Char(y) и, по определению множества В, y B.

8.Противоречие, значит, неверно предположение о существовании множества M такого, что M B (M).

Доказали, что выполнены оба требования определения B (M)> M .

Доказано Th.1.4.8

Образ элемента aΑ при соответствии G: Char(a) = b: (a, b) G } B

В связи с доказательством Обобщённой теоремы Кантора вспомните о брадобрее!

В некотором городе есть единственный брадобрей, который бреет всех мужчин города, которые не бреются сами, и только этих мужчин. Должен ли он брить самого себя?

Если да (то есть парикмахер должен брить себя сам), то он будет относиться к тем, кто бреется сам, а тех, кто бреется сам, он не должен брить. Если нет, то он будет принадлежать к тем, кто не бреется сам, и, значит, он должен будет брить себя. Таким образом, парикмахер бреет себя в том и только в том случае, когда он не бреет себя.

0.a1b1a2b2a3b3……akbk……

Аналогично доказывается, что континуумы трёх, четырёх, … (счётного множества) измерений имеют такую же мощность, как и одномерный континуум

А что дальше? Булеан B ( [0, 1] ) – множество подмножеств множества

действительных чисел отрезка [0, 1]

Согласно обобщённой теореме Кантора, мощность этого булеана │B ( [0, 1] ) │ превышает мощность │[0, 1] │, т.е. B ( [0, 1] ) не является континуальным множеством.

По определению – мощность булеана │B ( [0, 1] ) │-

гиперконтинуум. Мощность гиперконтинуального множества обозначается א2 (алеф-два)

Но в B ( [0, 1] ) также имеются подмножества, отсюда - гипер-гиперконтинуум B (B ( [0, 1] ) ) = א3 (алеф-три),

……….

Пример гиперконтинуума: множество всех произвольных функций на [0, 1]

Каждому подмножеству из B ( [0, 1] ) поставим во

взаимно-однозначное соответствие характеристическую функцию этого подмножества

По определению - мощность │B ( [0, 1] ) │-

гиперконтинуум, значит, гиперконтинуально множество характеристических функций

Тем более гиперконтинуально множество любых произвольных функций на [0, 1]

Важно для программистов!

Th.1.4.9

Любое бесконечное множество содержит счётное подмножество

Th.1.4.10

Всякое подмножество счётного множества конечно или счётно

Логика развития основных понятий главы 1

Множество – совокупность некоторых объектов, образованная по какому-либо правилу