11. Ординалы и кардиналы / Парадоксы теории множеств

Иван Ященко

<<< |1|…|8|9|10|11|12|13|14|15|16|17| >>>

11. Ординалы и кардиналы

Теорема о приложении. Из двух различных вполне упорядоченных множеств одно есть левый луч другого.

Такая формулировка нуждается в уточнении. Когда в математических рассуждениях рассматривают некоторые объекты, сразу оговаривают, какие их них считать равными, эквивалентными. Например, когда изучают группы, их рассматривают с точностью до изоморфизма^*18. Так и здесь, мы рассматриваем вполне упорядоченные множества с точностью до изоморфизма, т. е. с точностью до отображения, сохраняющего порядок ( $a < b \Leftrightarrow f(a) < f(b)$ ). Поэтому теорема означает следующее. Если есть два вполне упорядоченных множества $A$ и $B$ , и мы одно из них "прикладываем" к другому, то либо они совпадут, либо одно из них будет левым лучом другого.

^*18 Нам не важно, когда в группе два элемента, это 0 и 1 или слон и жираф. Если таблица умножения слона на жирафа такая же, как нуля на единицу, ну и ладно.

Доказательство очевидно по трансфинитной индукции. Введем трансфинитную индукцию по первому множеству. Отправим наименьший элемент $A$ в наименьший элемент $B$ . Далее, пусть все $\alpha$ из $A$ , меньшие некоторого $\alpha_0$ , уже отправлены в элементы $B$ . Если в $B$ еще остались элементы без прообразов, выберем среди них наименьший и отправим в него $\alpha_0$ , если в $B$ элементы без прообразов кончились, то $B$ — левый луч $A$ . Иначе ждем, пока закончится $A$ .

Определение. Назовем ординалом вполне упорядоченное множество. (Опять же, на самом деле мы называем ординалом не множество, а класс эквивалентности вполне упорядоченных множеств по отношению "изоморфно".) Между ординалами можно ввести отношение порядка с помощью теоремы о приложении, т. е. $A < B$ , если $A$ — левый луч $B$ (однако все ординалы множества не образуют, иначе существовало бы множество всех множеств).

Давайте посмотрим на счетные ординалы.

Первый ординал — это $\varnothing$ . Потом идет $1$ ^*19. Следующий ординал — это $2$ , потом $3$ , и т. д. Дальше идет ординал "натуральные числа", который обозначают $\omega$ . Если после всех натуральных чисел поставить самое большое число (получим сходящуюся последовательность), то будет $\omega + 1$ , и т. д., до $\omega + \omega$ (или $2\omega$ ), т. е. до двух сходящихся последовательностей одна за другой. Дальше $3\omega$ , $4\omega$ и т. д., до $\omega \cdot \omega$ . Этот ординал можно представить себе так: возьмем последовательность $a_n = \dfrac{1}{n}$ , и к каждому элементу приставим по сходящейся последовательности (рис. 10).

^*19 На самом деле это, конечно, $\{\varnothing\}$ , но поскольку все уже в школе привыкли писать $1$

, то…

Рис. 10

После всех счетных ординалов следует первый несчетный ординал $\omega_1$ , который можно получить, например, так. Вполне упорядочим отрезок. Возьмем минимальный несчетный левый луч. Его и назовем $\omega_1$ . Так можно продолжать долго. В итоге у нас получится цепочка

$\varnothing,\ 1,\ 2,\ 3, \dots,\ \omega,\ \omega + 1,\ \omega + 2, \dots,\ \omega + \omega,\ 3\omega, \dots,\ \omega \cdot \omega,\ \omega^3, \dots,\ \omega_1, \dots$

Что же такое кардиналы? Некоторые ординалы обладают особым свойством, а именно, они неравномощны никакому своему левому лучу. Такие ординалы называются начальными, или кардиналами. (Кардиналы на самом деле еще можно определить так: это классы эквивалентности множеств по отношению "равномощно".) Ни ординалы, ни кардиналы не образуют множества, но эти "немножества" в некотором смысле одинаковы (можно применить несколько формализованную теорему о приложении для класса ординалов и класса кардиналов).

11.1. Континуум-гипотеза

Понятно, что кардиналы можно складывать (что получится?), умножать (придумайте, как) и т. д., но для них также определено и понятие степени: через $2^{\alpha}$ обозначим мощность множества всех подмножеств $\alpha$ . Ясно, скажем, что $2^{\omega} > \omega$ , но совсем не ясно, равны ли $2^{\omega}$ и $\omega_1$ . Некоторые вещи можно утверждать наверняка. Например, выполняется следующая

Теорема. $2^{\omega} = \mathfrak{c} =[0,1]$ нельзя представить в виде объединения счетного числа множеств мощности меньше континуума{7}.

По-другому это можно сказать так: если континуум разбит в объединение счетного числа множеств, то хотя бы одно из них имеет мощность континуум. Если бы мы знали, что множество мощности меньше континуума счетно, то все очевидно: счетное объединение счетных множеств счетно. Но мы этого не знаем. Однако все равно попробуйте доказать эту теорему.

Аналогично можно доказать более общее утверждение:

$2^{\alpha}>\bigcup_{\beta<\alpha}\gamma_{\beta}$ , где $\gamma_{\beta}< 2^{\alpha}$

т. е. множество всех подмножеств $\alpha$ не представляется в виде объединения " $\alpha$ штук" множеств мощности меньше $2^{\alpha}$ . Как выясняется, верна следующая

Теорема. Теорема, изложенная выше, и отношение порядка, введенное нами между кардиналами, — это единственные ограничения на всю цепочку кардиналов (т. е. с учетом этих двух условий "может быть все что угодно").

Это значит следующее. Многие годы математики пытались доказать или опровергнуть естественное утверждение, называемое континуум-гипотезой:

$2^{\alpha} = \alpha^{+}$ , где $\alpha^{+}$ — следующая после $\alpha$ мощность.

В 1930-е годы Гедель доказал, что континуум-гипотеза непротиворечива со стандартной аксиоматикой, в 1960-е годы Коэн понял, что отрицание континуум-гипотезы также непротиворечиво с этой аксиоматикой, в 1980-е была как раз доказана теорема о том, что "может быть все что угодно".

Как вообще можно доказать, что некоторое утверждение непротиворечиво с какой-то аксиоматикой, например, с аксиоматикой Цермело–Френкеля? Нужно его добавить к этой аксиоматике и построить модель для получившейся системы утверждений. Одна из моделей строится довольно просто: нужно аккуратно выкинуть из цепочки кардиналов все промежуточные между $\alpha^{+}$ и $2^{\alpha}$ для каждого $\alpha$ , тогда континуум-гипотеза будет выполняться. Вторая модель несколько сложнее.

11.2. Самый большой кардинал

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

Назовем кардинал $\alpha$ сильно недостижимым, если для любого кардинала $\beta$ , меньшего $\alpha$ , множество всех подмножеств $\beta$ строго меньше $\alpha$ . Назовем кардинал $\alpha$ измеримым по Уламу, если существует счетно-аддитивная мера $\mu$ на множестве всех подмножеств $\alpha$ , принимающая на каждом множестве значение либо $0$ , либо $1$ , причем $\mu(\varnothing) = 0$ , $\mu(\alpha) = 1$ . Также нужно потребовать, чтобы $\mu$ не являлась так называемой $\delta$ -мерой, т. е. не имела вид

$\mu(A)=\begin{cases} 1, & \text{если}\ a\in A \\ 0, & \text{если}\ a\notin A\end{cases}$

где $a$ — некоторое фиксированное число.

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

4. Доказать, что если $\alpha$ — измеримый по Уламу кардинал, то $\alpha$ сильно недостижим.

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

5. Доказать, что если существует сильно недостижимый кардинал, то теория множеств со стандарной системой аксиом Цермело–Френкеля непротиворечива.

Как известно, доказывать непротиворечивость теории множеств сложно. Даже существует теорема, говорящая о том, что это сделать довольно проблематично. Отсюда видно, что только что сформулированное утверждение очень сильное по своей сути. Попробуем дать идею его доказательства.

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

{7} $\mathfrak{c}$ — общепринятое обозначение для мощности отрезка $[0,1]$ .

<<< |1|…|8|9|10|11|12|13|14|15|16|17| >>>

Содержание

Комментарии: 0

Похожее

Парадоксы теории множеств и их философская интерпретация

Парадоксы являются следствием дихотомии языка и мышления, выражением глубоких диалектических (теорема Гёделя позволила проявить диалектику в процессе познания) и гносеологических трудностей, связанных с понятиями предмета и предметной области в формальной логике, множества (класса) в логике и теории множеств, с употреблением принципа абстракции, позволяющего вводить в рассмотрение новые (абстрактные) объекты (бесконечность), со способами определения абстрактных объектов в науке и т. п. Поэтому не может быть дано универсального способа устранения всех парадоксов.
А нужен ли выбор? (альтернатива аксиоме выбора в теории множеств)

Михаил Раскин

Современная математика в качестве своего основания использует теорию множеств. Традиционно при анализе теоретико-множественных тонкостей используется аксиоматика Цермело-Френкеля с аксиомой выбора, обозначаемая ZFC. На аксиому выбора опираются доказательства наличия базиса в любом векторном пространстве и существования неизмеримого множества в математическом анализе. К сожалению, теория множеств обязана работать и со множествами, которые не описываются достаточно подробно и конкретно, чтобы мы могли себе их представить. В курсе будет рассмотрен один пример, к чему это приводит. Оказывается, ценой ослабления аксиомы выбора можно получить теорию множеств, в которой любая ограниченная функция на отрезке интегрируема по Лебегу. То, что используется аксиома выбора, в каком-то смысле, произошло исторически. Курс основан на статье Р.М. Соловэя о построении теории множеств, в которой все множества вещественных чисел измеримы.
«Мы не можем ждать милостей от природы», или применение метода вынуждения в построении моделей теории множеств

Михаил Раскин

В теории множеств есть несколько известных вопросов о том, следует ли из некоторых аксиом другая аксиома (или гипотеза; аксиома — это просто гипотеза, которой пользуется подавляющее большинство). Как и в других областях математики, недоказуемость можно продемонстрировать с помощью модели, в которой верны предположения, но не верна гипотеза. Для построения одного из самых известных таких примеров, модели теории множеств, в которой есть промежуточная мощность между мощностями натурального ряда и вещественной прямой, Коэн разработал метод вынуждения.
Теория множеств для начинающих

Виктор Викторов

Основные понятия, операции над множествами, тождества, свойства дополнения, правило Де Моргана, свойства симметрической разности; отображение (функция), факторотображение, отношение эквивалентности, парадокс брадобрея; упорядоченные множества, минимальный, наименьший, максимальный и наибольший элементы в упорядоченном множестве, мажоранта и миноранта; аксиома выбора, вполне упорядоченное множество.
Числа и многочлены

Проскуряков И. В.

Целью этой книги является строгое определение чисел, многочленов и алгебраических дробей и обоснование их свойств, уже известных из школы, а не ознакомление читателя с новыми свойствами. Поэтому читатель не найдет здесь новых для него фактов (за исключением, быть может, некоторых свойств, действительных и комплексных чисел), но узнает, как доказываются вещи, хорошо ему известные, начиная с «дважды два — четыре» и кончая правилами действий с многочленами и алгебраическими дробями. Зато читатель познакомится с рядом общих понятий, играющих в алгебре основную роль.
Математика на шахматной доске

Гик Е. Я.

В книге рассказывается о разнообразных связях, существующих между математикой и шахматами: о математических легендах о происхождении шахмат, об играющих машинах, о необычных играх на шахматной доске и т. д. Затронуты все известные типы математических задач и головоломок на шахматную тему: задачи о шахматной доске, о маршрутах, силе, расстановках и перестановках фигур на ней. Рассмотрены задачи «о ходе коня» и «о восьми ферзях», которыми занимались великие математики Эйлер и Гаусс. Дано математическое освещение некоторых чисто шахматных вопросов - геометрические свойства шахматной доски, математика шахматных турниров, система коэффициентов Эло.
Десять великих идей науки. Как устроен наш мир

Питер Эткинз

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

Смаллиан Рэймонд

В книге «Алиса в Стране Смекалки» кэрролловская Алиса из Страны Чудес и ее друзья раскрывают перед читателем нескончаемую вереницу задач-головоломок. Они доставят удовольствие всем любителям занимательной математики, а почитателям творчества Льюиса Кэрролла в особенности.
Математическое понимание природы

Владимир Арнольд

Сборник «Задачи для детей от 5 до 15 лет» вызвал много отзывов. И дети, и взрослые читатели часто сожалели, что там были только математические задачи, — ведь и все естествознание заслуживает столь же активного, творческого к себе отношения. Теперь я отвечаю на эти пожелания — следуя скорее Яну Амосу Каменскому, чем современным педагогам, то есть всегда стремясь быть понятным читателю, не имеющему предварительных знаний (но столь же любознательному, как большинство подростков).
Невероятные числа профессора Стюарта

Отрывок из книги «Невероятные числа профессора Стюарта» заслуженного профессора математики Уорикского университета, известного популяризатора науки Иэна Стюарта, посвященной роли чисел в истории человечества и актуальности их изучения в наше время.

Далее >>>