Теория множеств Цермело–Френкеля

Теория множеств Цермело-Френкеля — аксиоматическая теория множеств первого порядка. Под этим названием известны две аксиоматические системы — система без аксиомы выбора (ТМЦФ) и система с аксиомой выбора (ТМЦФ с аксиомой выбора). Обе системы являются очень известными фундаментальными системами для математики благодаря своей выразительной силе.

Хотя возможны различные аксиоматизации теории множеств, ТМЦФ и ТМЦФ с аксиомой выбора являются наиболее распространёнными известными.

ТМЦФ с аксиомой выбора, как твёрдо полагают, непротиворечива, хотя сама ТМЦФ с аксиомой выбора не может доказать свою формализованную непротиворечивость (Con(ТМЦФ)), пока она фактически непротиворечива по теореме Гёделя о неполноте. Если ТМЦФ с аксиомой выбора не является непротиворечивой, доказуемо-теоретический ординал не определён или определён как $\omega_1^\text{CK}$ в зависимости от контекста. Если ТМЦФ с аксиомой выбора является $\Pi^1_1$-надёжной, то доказуемо-теоретический ординал ТМЦФ с аксиомой выбора является рекурсивным, что делает его меньше, чем ординал Чёрча-Клини. $\Pi^1_1$-надёжность подразумевает непротиворечивость, и, следовательно, не доказуема в рамках самой ТМЦФ с аксиомой выбора. Хотя доказуемо-теоретический ординал ТМЦФ с аксиомой выбора неизвестен, он больше, чем почти все другие рекурсивные ординалы, появляющиеся в гугологии.

Основы

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

Формальные языки и теории

Формальный язык состоит из алфавита и набора правил формирования. Алфавит — набор допустимых символов. Предложения в языке состоят из строк символов, а правила формирования точно определяют, какие предложения считаются допустимыми. Интуитивно правила формирования можно рассматривать как правила грамматики, сообщающие нам, правильно ли написано предложение.

Теория — набор предложений на данном формальном языке, называемых аксиомами теории. Дедуктивная система в теории — это набор правил вывода, которые мы используем для создания новых предложений, учитывая набор существующих предложений. Если мы начнём с набора аксиом, а затем продолжим применять всевозможные правила вывода, мы создадим набор предложений, которые мы назовём теоремами. Интуитивная связь, которую здесь следует установить, заключается в том, что аксиомы — то, что мы предполагаем как истинное, а теоремы — то, что мы доказываем. Правила вывода — основные элементы, необходимые для доказательства: всякий раз, когда вы применяете правило вывода к истинному утверждению, вы получаете ещё одно истинное утверждение.

Одна теория, называемая исчислением предикатов, очень полезна для теоретиков множеств. Её самая важная особенность — предоставить нам логические связки $\land ,\lor ,\neg ,\Rightarrow ,\Leftrightarrow ,\forall ,\exists ,(,)$ как часть её алфавита. Она также даёт нам правила вывода, чтобы придать этим логическим связкам смысл. Полное описание выходит за рамки этой статьи.

Язык теории множеств дополняет исчисление предикатов бесконечным числом множественных переменных, обозначаемых буквами, и двумя множественными связками $=,\in$. Таким образом, одна теория множеств является теорией, использующей язык теории множеств.

Истина, последовательность и неполнота

Отсюда мы предположим, что теории, с которыми мы имеем дело, являются расширениями исчисления предикатов.

Начиная с аксиом теории, мы можем вывести, какие утверждения истинны, а какие ложны. При наличии теории $T$ мы говорим, что $T$ доказывает предложение $\phi$, обозначаемое $T\vdash \phi$, если правила вывода могут быть повторно применены конечное число раз к аксиомам, в конечном итоге приводя к $\phi$. Мы также говорим, что $T$ доказывает истинность $\phi$.

Отрицание $\phi$, обозначаемое $\neg\phi$, можно рассматривать как логическую противоположность $\phi$. Если $T\vdash \neg \phi$, мы говорим, что $T$ опровергает $\phi$, или доказывает ложность $\phi$.

Если утверждение может быть доказано истинным, то здравый смысл подсказывает нам, что оно не может быть доказано ложным. К сожалению, в формальных языках это не так просто. Вот тривиальный пример: некоторая теория $T$ содержит как $\phi$, так и $\neg\phi$ в качестве аксиом. Понятно, что такая теория не будет иметь очень широкого применения: зачем работать с истинным и ложным, если у нас нет дихотомии? Но оказывается, что правда более жестока — если мы можем доказать, что некоторое утверждение является одновременно истинным и ложным, принцип взрыва говорит нам, что мы можем доказать, что всё является истинным и ложным! Теория, которая доказывает некоторое утверждение, а также его отрицание, называется противоречивой, а когда это невозможно, теория 'непротиворечивой.

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

Известный пример — Континуум-гипотеза, которая утверждает, что нет кардинальных чисел строго между $\aleph_0$ и $2^{\aleph_0}$. Курт Гёдель доказал, что это не может быть опровергнуто в ТМЦФ с аксиомой выбора, но позже Пол Коен доказал, что это также не может быть доказано в ТМЦФ с аксиомой выбора. Упс. Поэтому мы говорим, что континуум-гипотеза была доказана независимо от ТМЦФ с аксиомой выбора, что не является очень удовлетворительным ответом на проблему. Другим известным примером является аксиома выбора — известно, что она независима от ТМЦФ. Теоретики множеств поняли, что аксиома выбора — очень разумное предположение, поэтому она была добавлена, чтобы сформировать теперь широко принятую ТМЦФ с аксиомой выбора. Здесь вы можете видеть, что в математической логике мы должны идти по линии, насколько мы можем принять аксиомы. То, что делает аксиому разумной, — спорный и субъективный вопрос, и начало 20 века изобиловало академическими дебатами на эту тему.

Мы хотели бы иметь теорию, которая является одновременно непротиворечивой и полной, так что каждое предложение, выраженное на языке теории, может быть либо доказано, либо опровергнуто (но не оба одновременно). Такие теории существуют — одна из них — арифметика Пресбургера. К сожалению, арифметика Пресбургера очень слаба, и её язык даже недостаточно силён, чтобы формировать утверждения об умножении!

Так есть ли какие-либо полезные сильные теории, которые являются одновременно последовательными и полными? Оказывается, их нет. Это первая теорема Гёделя о неполноте, и её полная и формальная форма такова:

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

Для глубокого, начального уровня освещения этой темы см. удостоенную Пулитцеровской премии книгу Гёдель, Эшер, Бах Дугласа Хофштадтера. Среди множества переплетённых тем в книге одна из них — пошаговое руководство по построению аксиоматической теории арифметики и конкретный пример того, как "озадачить" её независимым утверждением.

Модели: Неформальные

Теория довольно похожа на свод законов. Он диктует, что законно, а что нет. Но какой смысл в своде законов без города, который обеспечивает соблюдение закона и соблюдает его? Вот тут-то и появляется понятие модели. Теория даёт нам правила (теоремы), которым нужно следовать, тогда как модель — фактическая реализация этих правил.

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

Утверждение	Истина
Париж — столица Франции	Истина
Это утверждение истинно.	Истина
Бог реален	Истина
Синий цвет лучше зелёного	Ложь
2 + 2 = 5	Ложь
...	...

Здесь нет понятия независимости, поскольку мы не имели дело с правилами вывода или аксиомами. Каждое утверждение на 100% истинно или на 100% ложно (представьте, что эти утверждения являются частью формальной системы, которой русский язык не является).

Теория, с другой стороны, представляет собой набор аксиом и правил вывода, которые генерируют таблицу, подобную этой:

Утверждение	Вывод
Париж — столица Франции	Доказуемо
Это утверждение истинно.	Доказуемо
Бог реален	Независимо
Синий цвет лучше зелёного	Независимо
2 + 2 = 5	Опровержимо
...	...

Теперь мы можем перейти к понятию удовлетворения. Дана теория $T$ и множество $M$, если каждое утверждение, которое истинно в $T$, также истинно для $M$, и каждое утверждение, которое ложно в $T$, также ложно в $M$, то $M$ является моделью $T$, или $M$ моделями $T$. Множество, представленное первой таблицей, является допустимой моделью теории, представленной второй таблицей. Значения истинности не независимых утверждений совпадают с таковыми модели.

Модели: Формальные

Мотивация большинства наших теорий заключается в формализации наших попыток доказать утверждения об абстрактных объектах. Например, арифметика Пеано была создана для формализации теорем о множестве натуральных чисел. Множество натуральных чисел удовлетворяет всем аксиомам Пеано, и поэтому мы можем сказать, что это множество моделирует эти аксиомы, или что это модель PA. Аналогично можно утверждать, что универсум всех множеств является моделью ТМЦФ. Разница между этими двумя примерами в том, что универсум всех множеств не является множеством — нечто, известное как собственный класс. Это проблема, потому что ни ТМЦФ, ни ТМЦФ с аксиомой выбора не могут говорить о собственных классах. Мы хотим, чтобы модель была множеством.

Внутри множества каждое предложение либо истинно, либо ложно. Это не подлежит доказуемости: истинность каждого предложения теперь является неотъемлемым свойством множества. Если внутри этого множества все аксиомы теории $T$ истинны, то мы говорим, что это множество является моделью теории $T$.

Важным свойством исчисления предикатов является то, что если предложение $\phi$ может быть выведено из предложений, которые истинны внутри модели, то $\phi$ также истинно в модели. Благодаря этому мы можем видеть, что если $T$ несовместимо, то у него нет модели — внутри модели ни одно предложение не может быть одновременно истинным и ложным. Поэтому каждая теория с моделью непротиворечива.

Обратное также верно — каждая теория, которая непротиворечива, имеет модель. Это как раз Гёделя о полноте. Эта эквивалентность очень важна, поскольку работа с моделями формальных теорий позволяет нам доказать независимость многих утверждений.

Аксиомы

Первые восемь из этих аксиом являются аксиомами ТМЦФ. Вместе с последней они образуют ТМЦФ с аксиомой выбора. Предполагаемая интерпретация для $\in$ — "является членом…", а для $=$ — "является тем же множеством, что и…".

Аксиома объёмности

$\forall x\forall y(\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow (x=y))$

Данные множества $x, y$, если они имеют точно такие же элементы, то они равны.

Это также можно рассматривать как определение равенства, а не как аксиому, поскольку нам не требуется, чтобы $=$ был в нашем алфавите.

Аксиома пары

$\forall x\forall y\exists z(x\in z\land y\in z)$

Для заданных множеств $x, y$ существует множество $z$, содержащее $x$ и $y$. Используя индукцию, мы можем показать, что для множеств $x_1,...,x_n$ существует множество $z$, содержащее $x_1$,...,$x_n$ для $n>2$. Используя объёмность, мы можем показать, что для множества $x_1$ существует множество $z$, содержащее $x_1$.

Аксиома регулярности

Также известна как аксиома основания.

$\forall x(\exists a(a\in x)\Rightarrow \exists y(y\in x\land \neg \exists z(z\in y\land z\in x)))$

Если множество $x$ непустое (т. е. имеет элемент $a$), то существует элемент $y\in x$ такой, что $y$ и $x$ не пересекаются. Эквивалентная формулировка следующая: предположим, что мы начинаем с множества $x_0$, и на каждом шаге мы берём некоторый элемент $x_{i+1}\in x_{i}$. Затем этот процесс в конечном итоге останавливается, поскольку мы приходим к пустому множеству.

Примером применения является то, что ни одно множество не может быть элементом самого себя.

Схема аксиом выделения

Схема аксиом — это бесконечный класс аксиом, которые разделяют свою общую структуру. Для каждого предложения $\phi (x,z,w)$ теории множеств, где $y$ не является свободным, мы имеем следующую аксиому:

$\forall x\forall w\exists y\forall z(z\in y\Leftrightarrow (z\in x\land \phi (x,z,w)))$

Интуитивный смысл заключается в том, что определяемое подмножество множества само является множеством. Точнее, для каждого множества $x$, формулы $\phi$ и параметра $w$ существует множество $y$, состоящее из этих элементов $z\in x$, удовлетворяющее $\phi (x,z,w)$.

Эта схема аксиом также известна как схема аксиом ограниченного понимания, в отличие от неограниченного понимания. Последняя аксиома отбрасывает требование $z\in x$. Однако эта аксиома противоречива, поскольку при использовании $\phi (a,b):=\neg a\in a$ это приводит к парадоксу Рассела.

Аксиома степени

$\forall x\exists y\forall z(z\in y\Leftrightarrow \forall w(w\in z\Rightarrow w\in x))$

Для каждого $x$ существует множество $y$, элементы которого являются в точности подмножествами $x$. Это множество называется мощностью множества $x$ и обозначается ${\mathcal {P}}(x)$. По теореме Кантора это позволяет нам строить множества увеличивающихся размеров, т. е. увеличивающихся кардиналов.

Аксиома бесконечности

$\exists x(\emptyset \in x\land \forall y(y\in x\Rightarrow (y\cup \{y\})\in x))$

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

Обратите внимание, что $\emptyset$ и $y\cup \{y\}$ на самом деле не являются частью языка теории множеств, а являются сокращениями обозначений. $\emptyset \in x$ можно переформулировать как $\exists z(z\in x\land \forall w(\neg w\in z))$ и $(y\cup \{y\})\in x$ можно переформулировать как $\exists z(z\in x\land y\in z\land \forall w(w\in z\Rightarrow (w=y\lor w\in y)))$.

Аксиома объединения

$\forall x\exists y\forall z(z\in y\Leftrightarrow \exists w(w\in x\land z\in w))$

Для каждого множества $x$ существует множество $y=\bigcup _{z\in x}z$, объединение всех элементов x.

Схема преобразования множеств

Ещё одна схема аксиом. Ниже приведена аксиома для каждой формулы $\phi (a,b,c)$:

$\forall p(\forall x\forall y\forall z(\phi (x,y,p)\land \phi (x,z,p)\Rightarrow y=z)\Rightarrow \forall x\exists y\forall z(z\in y\Leftrightarrow \exists w(w\in x\land \phi (w,z,p))))$

Здесь $p$ — параметр, а $\phi (x,y,p)$ выражает, что некоторая функция $f$ принимает значение $y$ в $x$. Тогда для каждого $x$ существует множество $y$, которое является образом $x$ при $f$, т. е. $z$ находится в $y$ тогда и только тогда, когда у нас есть некоторый $w$ с $f(w)=z$.

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

$\forall x(\neg (\emptyset \in x)\land \forall p\forall q\forall r(p\in q\land p\in r\land q\in x\land r\in x\Rightarrow q=r)\Rightarrow \exists y\forall z(z\in x\Rightarrow \exists !w(w\in z\land w\in y)))$

Если $x$ — набор непересекающихся непустых множеств, то существует множество $y$, которое имеет ровно один общий элемент с каждым элементом $x$.

$\exists !a\phi (a)$ — сокращённая запись, говорящая "существует уникальное $a$, удовлетворяющее $\phi (a)$", то есть $\exists a(\phi (a)\land \forall b(\phi (b)\Rightarrow b=a))$.

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