Уровень C1 · Advanced

Рай для математиков

«Из рая, который создал для нас Кантор, никто не сможет нас изгнать». Давид Гильберт

Уровень C1 завершает часть I именно там, куда весь язык и вёл: полная аксиоматика $\mathsf{ZFC}$, выписанная и прочитанная строка за строкой; аксиома выбора, рассмотренная с трёх сторон, которые оказываются одним и тем же утверждением; и универсум фон Неймана, который наконец даёт любому множеству — конечному или трансфинитному — точное понятие глубины.

Что вы узнаете

—Полный список аксиом $\mathsf{ZFC}$ — конгруэнтность, экстенсиональность, степень, объединение, регулярность, замещение, бесконечность, выбор — с разбором того, что каждая формула утверждает на обычном языке, а не просто с её названием.
—Аксиому выбора в двух равносильных формах, интуитивное прочтение «мешок с мешками», и почему она вызывала споры с самого дня, когда Цермело сформулировал её в 1904 году.
—Три теоремы, доказуемо равносильные $\mathsf{AC}$ в $\mathsf{ZF}$: теорему Цермело о вполне упорядочении, лемму Цорна и максимальный принцип Хаусдорфа.
—Широкий спектр следствий $\mathsf{AC}$ — от «в любом векторном пространстве есть базис» и теоремы Тихонова до контринтуитивного парадокса Банаха–Тарского — и почему её счётная форма $\mathsf{AC}_\omega$ обладает собственным запасом полезных следствий (счётное объединение счётных множеств счётно, лемма Кёнига о бесконечности), но ни одним из парадоксальных.
—Ранг множества как глубину дерева, почему конечные шкалы перестают работать с появлением бесконечных множеств, и как это исправляют ординалы.
—Кумулятивную иерархию фон Неймана $V_\alpha$ — весь теоретико-множественный универсум, построенный уровень за уровнем из $\emptyset$.

1. Читаем аксиомы рая

Слова Гильберта про рай Кантора — не пустая похвала: к началу XX века теория множеств действительно стала языком, на который можно перевести любую другую математическую теорию. Но рай, построенный на неограниченном свёртывании, кишит расселовскими змеями (уровень B2), поэтому $\mathsf{ZFC}$ заменяет «любое свойство задаёт множество» восемью явными правилами построения: конгруэнтность и экстенсиональность фиксируют, что такое множество вообще; булеан, объединение и замещение говорят, как строить более крупные множества из уже имеющихся; регулярность исключает множества, содержащие сами себя; бесконечность наконец допускает по-настоящему бесконечное множество; а выбор — самая обсуждаемая из восьми — говорит, что из каждого элемента любого набора непустых множеств всегда можно извлечь выбранный элемент.

Читать аксиомы как предложения, а не как непрозрачные символы, — это и есть весь метод книги в миниатюре: $\forall x\in A\,\exists!y\in x\,\langle x,y\rangle\in f$ — это просто «$f$ выбирает ровно один элемент из каждого элемента $A$» — интуиция «мешка с мешками», записанная точно.

2. Одна аксиома, три облика

Цермело впервые сформулировал аксиому выбора в 1904 году, чтобы доказать, что любое множество можно вполне упорядочить, — и оказалось, что это утверждение и ещё два, на первый взгляд не связанных с ним, доказуемо равносильны ему в $\mathsf{ZF}$:

Аксиома выбора

У любого семейства непустых множеств есть функция выбора — выбирающая ровно один элемент из каждого элемента семейства.

Теорема Цермело

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

Лемма Цорна

Если в частично упорядоченном множестве любая цепь ограничена сверху, то в нём есть максимальный элемент.

В 1938 году Гёдель показал, что добавление $\mathsf{AC}$ к остальным аксиомам $\mathsf{ZF}$ не может внести противоречие, если его там ещё не было; в 1963 году Коэн методом форсинга показал, что $\mathsf{AC}$ также нельзя вывести из $\mathsf{ZF}$. Она независима — истинна в одних моделях теории множеств, ложна в других, — и именно поэтому книга рассматривает её как настоящий выбор математического мировоззрения, а не решённый факт.

Вторая большая идея главы отвечает на более тихий вопрос: насколько «глубоко» множество? Для наследственно- конечных множеств глубина — это просто самая длинная цепочка принадлежностей вниз до $\emptyset$, обычное натуральное число. Но как только появляются бесконечные множества, эта шкала ломается: $\{\omega\}$ стоит на один шаг принадлежности выше самого $\omega$, однако пути в его дереве принадлежности не длиннее, чем у $\omega$. Исправление — измерять глубину не натуральными числами, а ординалами, и строить универсум явно, уровень за уровнем:

Иерархия фон Неймана

\[V_0=\emptyset,\qquad V_{\alpha+1}=\mathcal P(V_\alpha),\qquad V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha\ \text{(}\lambda\text{ — предельный)}\]

У любого множества есть ранг — наименьшее $\alpha$, при котором оно появляется в $V_{\alpha+1}$ — и, согласно аксиоме регулярности, ранг есть у каждого множества.

3. Проверьте себя

Первые пять упражнений из блока задач главы, из русского издания.

Переведите следующие утверждения в формулы языка $\mathsf{ZF}$, используя предикат принадлежности $\in$ и логические связки:
1. Множество $A$ является подмножеством множества $B$.
2. Множества $A$ и $B$ не имеют общих элементов (не пересекаются).
3. Множество $A$ содержит ровно два элемента.
4. Множество $P$ является множеством всех подмножеств (булеаном) $A$ (т.е. $P = \mathcal P(A)$).
Сформулируйте следующие понятия и теоремы в виде одиночных формул на языке теории множеств (используя вспомогательные предикаты, если необходимо):
- Теорема Кантора: не существует сюръекции из $A$ в $\mathcal P(A)$.
- Аксиома счётного выбора ($\mathsf{AC}_\omega$).
- Определение фильтра: семейство $\mathcal F \subseteq \mathcal P(S)$ является фильтром на $S$, если $S \in \mathcal F$ и $\emptyset \notin \mathcal F$; $\mathcal F$ замкнуто относительно пересечения; и $\mathcal F$ замкнуто относительно надмножеств.
- Принцип максимума Хаусдорфа: в любом частично упорядоченном множестве любая цепь содержится в максимальной цепи.
Пусть $S$ — бесконечное множество. Рассмотрим совокупность $\mathcal F$ всех подмножеств $X \subseteq S$, таких что $S \setminus X$ конечно. Докажите, что $\mathcal F$ является фильтром.
Пусть $A = \{a, b, c\}$. Определите, какие из следующих отношений на $A$ являются рефлексивными, симметричными, антисимметричными или транзитивными:
1. $R_1 = \{\langle a, a\rangle, \langle b, b\rangle, \langle c, c\rangle\}$.
2. $R_2 = \{\langle a, b\rangle, \langle b, a\rangle, \langle a, a\rangle\}$.
3. $R_3 = \{\langle a, b\rangle, \langle b, c\rangle, \langle a, c\rangle\}$.
Пусть функция $J: \omega \times \omega \to \omega$ задана формулой $J(a, b) = 2^a(2b + 1) - 1$. Докажите, что $J$ является биекцией.

Всего в уровне C1 — 24 упражнения, каждое с полным разобранным решением в приложении книги.

Остальная часть уровня C1 — и часть II за её пределами

Этот конспект пропускает полный вывод равносильности аксиомы выбора, теоремы Цермело и леммы Цорна, приём с определяемым отображением, лежащий в основе аксиомы замещения, и заключительный раздел главы о том, как внутри $\mathsf{ZFC}$ конструируются математические структуры. Дальше часть II — «Доказательная база» — заново проходит Язык, Логику, Арифметику и Теорию множеств с полной формальной строгостью.

Все способы купить К обзору книги

← Уровень B2 — Фундамент математики К обзору книги →