sets-formalism.tex

\section{Формализм}

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

Обычно рассмотрение формализма теории множеств начинают с обсуждения парадокса Рассела, на примере которого объясняются ряд тонкостей аксиом теории множеств и мотивируются определения. Мы не будем исключением.

{\bfseries Парадокс Рассела.} Пусть $U$ — множество всех множеств. $A = \{x\in U|x\not\in x\}$, то есть множество таких множеств, которые не содержат себя самого в качестве элемента. Вопрос: принадлежит ли $A$ самому себе, то есть верно ли, что $A\in A$?

Если предположить, что $A\in A$, то по определению $A$, он не должен быть элементом $A$. Если $A\not\in A$, то по определению $A$, $A \in A$. Это сильно напоминает парадокс брадобрея, рассмотренный в первой главе, и утверждение парадокса Рассела на самом деле легко сводится к тому же самому утверждению: $\exists A\forall x\in A (x\in A \leftrightarrow x\not\in x)$. Однако в качестве $x$ мы можем взять $A$ и получить запись $A\in A \leftrightarrow A\not\in A$. Это высказывание всегда ложно.

Когда мы рассматривали парадокс брадобрея, то придя к такому выражению мы сделали вывод о том, что изначальная постановка задачи была некорректна — такого брадобрея просто не могло существовать. Так и здесь очевидно, что множества $A$, описанного в условии парадокса, очевидно не может существовать. Стало быть где-то мы использовали запись, которую мы использовать не имеем права. Первое предположение, которое обычно делают люди, глядя на этот парадокс, что некорректна запись $x\in x$, и соответственно первое желание — запретить множеству быть элементом самого себя.

Аксиоматика Цермело-Френкеля (сокращённо ZF), которую мы будем рассматривать в этом параграфе, как раз запрещает выражения вида $x\in x$. Для такого запрета специально вводится аксиома Foundation Axiom: «Для любого непустого множества $x$ найдётся такое $y\in x$, что $x$ и $y$ не пересекаются». Такая сложная формулировка на самом деле оправдана. Если бы вместо неё мы написали что-то простое вроде $\neg \exists x, x\in x$, то в таком виде эта аксиома все равно продолжала бы приводить к парадоксам вроде парадокса Рассела. Например, оказалась бы корректной запись $x=\{y\}$, $y=\{x\}$. В этом случае, действительно, $x\not\in x$, но однако $x\in y\in x$, а это ничуть не лучше того, что было изначально.

При этом важно заметить, что даже при этой аксиоме, у нас возможна ситуация, когда некоторый элемент множества является одновременно и его подмножеством: $x\in y \wedge x\subset y$. Например, вот: $a = \{b, c\}$, где $c=\{ b\}$. Очевидно, что $c\in a \wedge c\subset a$.

Может показаться, что эта ситуация тоже нежелательна. Однако, это не так. На самом деле вся арифметика построена именно на таких множествах. Если быть точным, то в современной математике натуральные числа определены следующим образом:

0) $0 = \emptyset$

1) $1 = 0 \cup \{0\} = \{0\}$

2) $2 = 1 \cup \{1\} = \{0, 1\}$

3) $3 = 2\cup \{2\} = \{0, 1, 2\}$

4) $4 = 3 \cup \{3\} = \{0, 1, 2, 3\}$

И так далее. В общем случае определена операция инкремента $S: n\mapsto n\cup \{n\}$, через которую и определяется множество натуральных чисел, обозначаемое символом $\mathbb{N}$. Сама функция инкремента часто обозначается как $+1$, то есть $S(n) = n+1$. $+1$ в данном случае не какая-то операция над числом и единицей, а просто другое обозначение для функции $S$. Мы пока примем сформулированное определение натуральных чисел как факт, а подробнее будем рассматривать его в следующей главе.

Как видно, накладывая ограничения на структуру множеств, Foundation Axiom тем не менее оставляет значительный простор для конструирования множеств, и это ещё одна причина, по которой она формулируется именно в таком виде.  Иные виды формулировок, которые могли бы придти на ум, могли бы не оставить нам возможности определить подобным образом натуральные числа. Мы конечно могли бы определить их и как-нибудь по-другому, однако приведённое определение пока является наиболее простым и удобным из всех известных науке. Об этом опять же будет в следующей главе.

Тем не менее с этой аксиомой оказывается все не совсем гладко, о чем свидетельствует следующая теорема.

{\bfseries Теорема.} В предположении Foundation Axiom, не существует бесконечной последовательности $x_1, x_2, x_3, \ldots$ такой, что $x_2 \in x_1$, $x_3 \in x_2$, $x_3 \in x_4, \ldots$, то есть последовательности, в которой каждый элемент является множеством, причём каждый элемент является так же элементом предыдущего элемента.

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

{\bfseries Определение.} {\slshape Последовательностью} элементов множества $A$ называется функция $x:\mathbb{N}\to A$. Элементы $x(n)\in A$ называются {\slshape элементами последовательности} и обозначаются как $x_n$.

При перечислении элементов последовательности, обычно предполагают, что первым элементом является $x_1$, затем $x_2$ и так далее. Формально это не совсем соответствует определению, которое мы только что привели: элементы последовательности мы начинаем нумеровать с единицы, однако множество натуральных чисел «начинается» с нуля. Чтобы добиться точности, мы могли бы либо нумеровать элементы последовательности начиная нулём, либо определять последовательность как отображение $\mathbb\{N\}\setminus \{0\} \to X$. На практике же эта неточность ни на что не влияет и поэтому можно оставить все как есть.

Если в нашем условии теоремы рассмотреть некоторое множество множеств $U$ и вспомнить о функции инкремента $+1$, то теорему можно переформулировать таким образом:

{\bfseries Теорема.} В предположении Foundation Axiom, не существует последовательности $\{x_n\}$ такой, что $x_{n+1} \in x_n$.

{\bfseries Доказательство.} Предположим противное. Пусть $f: \mathbb{N}\to U$ — такая функция, что $f(n+1) \in f(n)$. Foundation Axiom требует, чтобы существовало $A\in \mathrm{Im} f$, такое, что $A \cap \mathrm{Im}f = \emptyset$. Однако для любого $A\in \mathrm{Im} f$ найдётся такое $n$, что $A = f(n)$ в силу определения $f$. Отсюда $f(n+1) \in A$ и $f(n+1)\in \mathrm{Im}f$. Это значит, что $f(n+1)\in A \cap \mathrm{Im}f$, то есть $A$ и $\mathrm{Im}f$ все же пересекаются вопреки нашему предположению. Полученное противоречие доказывает теорему. \qed

Рассмотрим множество людей не Земле. Каждый из людей состоит из множества органов. Каждый орган из множества тканей. Ткани — из клеток. Клетки из органоидов, органоиды из молекул, молекулы из атомов и так далее. Это не очень точная и не очень формальная последовательность с научной точки зрения, но для наших целей этого вполне достаточно. Атом можно продолжать разбивать на субатомные частицы, их можно разбивать далее, получив кварки, которые, пока только предположительно, могут состоять из преонов (это открытый вопрос науки). Если будет доказано существование преонов, вполне вероятно, что встанет вопрос о том, из чего состоят преоны. В общем виде можно задаться таким вопросом, сформулированную ещё в древние времена: можно ли различные объекты физического мира разбивать на составные части сколь угодно долго, либо же мы неминуемо придём к некоторым неделимым составным частям?

Foundation Axiom внезапно отвечает на этот вопрос: да, мы обязательно должны придти к неделимым составным частям. Foundation Axiom конечно работает с формальными множествами, а приведённые физические рассуждения с объектами реального физического мира, поэтому считать, что Foundation Axiom действительно говорит что-то о реальном мире, мы не можем. Однако же подобная интерпретация наводит на мысли о том, что данная аксиома вероятно и не особо-то хороша.

Как мы говорили, аксиоматика ZF, которую мы сейчас рассмотрим, все же содержит в себе Foundation Axiom, однако, ZF не единственная возможная формализация теории множеств. Существуют и другие системы аксиом, в которых, наоборот, используется Anti-Foundation Axiom (кратко AFA, которая тоже может формулироваться по-разному). Простейший вариант такой аксиоматики это так называемая New Foundation Set Theory, в которой на уровне аксиом определяются ориентированные графы, допускающие циклы (дуги вида $(a, a)$), и AFA явно постулирует, что каждая вершина графа является множеством.

«Как же тогда в New Foundation обстоит дело с парадоксом Рассела?» — спросит читатель, если он ещё тут. Ответ на этот вопрос неожиданный: на самом деле парадокс Рассела вообще почти никак с Foundation Axiom не связан. Сама постановка парадокса содержит множество других внутренних противоречий, которые и приводят к нему, но эти противоречия разрешаются и без Foundation Axiom. Проблема с записью $x\in x$, которую мы пытались разрешить выше, оказывается, является лишь «наведённым эффектом» от других проблем формулировки, а Foundation Axiom при всей своей очевидности, оказывается, что не особо-то и нужна.

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

Итак, нам надо с чего-то начать. Увы, чтобы определить какое-то понятие, нам неминуемо необходимо пользоваться другими понятиями, которые тоже в свою очередь надо как-то определять. Поскольку бесконечную цепочку определений мы физически не можем построить, нам придётся смириться с тем, что у нас будет одно базовое понятие, которое не будет иметь никакого определения. Таким понятием для нас станет понятие {\slshape символа}.

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

Следующие символы будем называть {\slshape логическими символами}:

— {\slshape логические связки} $\neg$, $\wedge$, $\vee$, $\rightarrow$ и $\leftrightarrow$;

— {\slshape квантификаторы} $\forall$, $\exists$;

— {\slshape равенство} $=$;

— {\slshape переменные}, просто некоторый набор до сих пор не задействованных символов.

Так же будем выделять {\slshape нелогические символы} (это так же просто классификация неиспользуемых ранее символов):

— символы {\slshape отношений}{\slshape };

— символы {\slshape операций};

— {\slshape константные} символы.

Это все пока просто классификация. Скажем, аксиоматика ZF требует лишь одного символа отношения $\in$. Можно было бы рассмотреть дополнительно символы вроде $\cup$, $\cap$, $\bigtriangleup$ и подобных в качестве операций, а символ $\emptyset$ в качестве константного символа, однако аксиомы ZF не используют их, как будет видно ниже. Я повторюсь, что на данный момент мы не наделяем символы никаким смыслом — для нас это пока не более чем закорючки на бумаге, которые мы пока просто классифицировали без какой-либо особой логики.

{\bfseries Определение.} {\slshape Термом} называется либо константный символ, либо переменная, либо запись $f(a, b, \ldots, z)$, где $a, b, \ldots, z$ — некоторые прочие термы, а $f$ — символ операции.

{\bfseries Определение.} {\slshape Атомом} называется либо запись $a = b$, где $a$ и $b$ — термы, либо запись $f(a, b, \ldots, z)$, где $a, b, \ldots, z$ — некоторые прочие термы, а $f$ — символ отношения.

{\bfseries Определение.} {\slshape Формулой} называется одна из следующих записей:

— отдельный атом является формулой;

— если $\phi$ и $\psi$ являются формулами, то записи вида $\neg \phi$, $\phi \wedge \psi$, $\phi \vee \psi$, $\phi \rightarrow \psi$, $\phi \leftrightarrow \psi$ так же являются формулами;

— если $\phi$ — формула, а $v$ — переменная, то $\forall v \phi$ и $\exists v \psi$ так же являются формулами

{\bfseries Определение.} Переменная $v$ в составе формулы называется {\slshape свободной}, если перед этой формулой не написано $\exists v$ или $\forall v$

{\bfseries Определение.} {\slshape Предложением} называется формула без свободных переменных.

Приведённые нами определения несколько упрощены, но в целом достаточны. Например, с точки зрения определений, данных выше, запись $a\cap b$ не является формулой, однако формулой является $\cap(a, b)$. Мы могли бы расширить наши определения, чтобы покрыть более широкий класс формул, но это был бы довольно скучный бессодержательный рассказ в угоду формализму. При желании формально это может проделать читатель самостоятельно, это не сложно. Мы же двинемся дальше, а для краткости будем полагать, что записи вроде $a\cap b$ являются сокращением записей в соответствии с определениями. Для нас важнее сейчас понять общую идею, а не достичь максимальной корректности с формальной точки зрения.

Теперь можно вспомнить правила вывода из первой главы. Они формулировались просто как правила, по которым можно преобразовывать формулы (хотя само понятие формулы мы строго не определяли). Например, правило modus ponens говорило, что две формулы $\phi$ и $\phi\rightarrow\psi$ можно преобразовать в формулу $\psi$. Эти правила можно применять к произвольным формулам, не наделённых никаким смыслом. Это как раз наш случай. Мы будем их применять просто к закорючкам на бумаге, совершенно не думая о том, что эти закорючки что-то вообще значат.

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

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

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

Впрочем, первый параграф был довольно большой, и даже в том виде как мы сформулировали понятие теории, набор теорем логики, которые мы предположительно можем использовать, тоже объёмный, и все это предлагается принять на веру, основываясь на каких-то неформальных рассуждениях. Чтобы объем принимаемого на веру оказался меньше, можно в принципе договориться о том, что многие логические символы являются лишь сокращениями для длинных записей. Так, можно считать, что $x\vee y$ — это не более чем сокращённая форма записи для $\neg (\neg x \wedge \neg y)$, а $\exists x P(x)$ — сокращённая форма записи для $\neg \forall x \neg P(x)$. Правила вывода так же многие можно в этом случае либо выкинуть, либо доказать используя только преобразования формул.

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

Вот теперь мы можем формулировать аксиомы Цермело-Френкела (ZF):

{\bfseries 1. Extensionality Axiom}: $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \rightarrow x = y)$

Эта аксиома утверждает, что множество полностью определяется своими элементами, то есть если множества $x$ и $y$ состоит из одних и тех же элементов, то $x=y$. Довольно разумное требование, здесь сложно как-то ещё это прокомментировать.

{\bfseries 2. Foundation Axiom}: $\forall x(\exists y (y\in x)\rightarrow \exists y(y\in x\wedge \neg \exists z (z\in x \wedge z\in y)))$

Возможно после того, как я сформулировал эту аксиому выше словами обычного русского языка, у вас могло бы возникнуть желание записать эту аксиому как-то вроде $\forall x \not= \emptyset \exists y\in x, x\cap y = \emptyset$. Такая запись однако не может являться предложением нашей теории, так как у нас на данный момент пока не определены $\emptyset$ и операция $\cap$. Поэтому приходится расписывать это все подробно. Попробуйте разобраться каким именно образом предложение выше выражает желаемый смысл аксиомы.

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

{\bfseries 3. Comprehension Scheme Axiom}: Для каждой формулы $\phi$ со свободными переменными $v_1, \ldots, v_n, x$ верно, что $\forall z \exists y \forall v_1 \ldots \forall v_n (x\in y \leftrightarrow x \in z \wedge \phi(x, v_1, \ldots, v_n))$.

Опять же выглядит страшно, но это станет понятнее, когда мы изложим её смысл. Изначальный посыл этой аксиомы дать возможность формулировать множества по заданной формуле. Мы говорили уже о о том, что каждый предикат даёт возможность формировать подмножество, и смысл этой аксиомы в том, что нам нужна возможность формировать множества типа $\{x|\phi(x)\}$.

При заданном фиксированном $\phi$ можно было бы сформулировать эту аксиому как-то так: $\exists y \forall x (x\in y \leftrightarrow \phi(x))$. Однако, эта формулировка привела бы все к тому же парадоксу Рассела, если определить $\phi(x) = x \not \in x$. Действительно, в этом случае $\exists y \forall x (x\in y \leftrightarrow x\not \in x)$, и если положить $x=y$ (мы имеем на это право из-за квантора общности), то получим противоречие $y \in y \leftrightarrow y\not \in y$.

Чтобы избежать парадокса Рассела в данном случае, мы должны потребовать, чтобы можно было формировать не произвольные множества, а лишь подмножества некоторых уже существующих множеств: $\forall z \exists y \forall x (x\in y \leftrightarrow x \in z \wedge \phi(x))$. Данная формальная уловка действительно «лечит» парадокс Рассела: теперь для формулы $x \in y \leftrightarrow x \in z \wedge x\not \in x$ всегда можно взять в качестве $y$ пустое множество, и оба атома $x \in y$ и $x \in z$ окажутся в этом случае ложны, что сделает истинной эквиваленцию (вспоминаем первую главу).

Здесь есть два тонких места. Первое заключается в том, что мы пока не определили понятие пустого множества. Однако с помощью Comprehension Axiom это делается довольно легко, если сформировать подмножество некоторого множества $z$ по предикату $x \not= x$: $\emptyset = \{x \in z |x \not= x\}$. Понятно, что такое множество не содержит ни одного элемента, это же можно считать и как определение пустого множества (если бы нашёлся такой $y$, который принадлежал бы определённому нами множеству, то было бы $y\not= y$, что всегда ложно). В силу Extensionality Axiom такое множество единственно, и мы имеем право ввести следующее определение:

{\bfseries Определение.} $\emptyset$ это уникальное множество, такое что $\forall x (x\not\in \emptyset)$.

Второе тонкое место заключается в потенциальной возможности существования множества всех множеств. Если предположить, что существует такое $z$, что $\forall x (x \in z)$, то в формуле $y \in y \leftrightarrow y\in z \wedge y \not \in y$, рассматриваемой выше, даже если $y = \emptyset$ использованный нами для разрешения парадокса, будет верным $y \in z$, и тогда выражение $y \in y \leftrightarrow y\in z \wedge y \not \in y$ окажется ложным. Отсюда следует следующая теорема:

{\bfseries Теорема.} $\neg \exists x \forall y (y \in x)$.

Это и есть теорема о том, что не существует множества всех множеств. Предположение же парадокса Рассела «Пусть $U$ — множество всех множеств» уже само по себе заключает в себе противоречие.

Как теперь видно, парадокс Рассела кроется совершенно не в Foundation Axiom, а в Comprehension Axiom, хотя на первый взгляд казалось очевидным совершенно другое. Реальная причина парадокса не в возможности написать формально $x\in x$ (от такой возможности мы в действительно не можем уйти, если пользоваться определениями формул и теорий как мы их определили), а в слишком вольных терминах при определении подмножеств и самом предположении о существовании множества всех множеств.

Но вернёмся к аксиоме. Общий её смысл я думаю теперь понятен. Переменные $v_i$ необходимы лишь для обобщения аксиомы на случаи формул с несколькими свободными переменными, не более того (рассмотренные нами выше примеры имели лишь одну свободную переменную). Может возникнуть ещё вопрос почему мы саму формулу $\psi$ не снабдили квантором $\forall$, ведь в этом случае мы могли бы записать аксиому без дополнительных слов вроде «для каждой формулы $\psi$...».

Дело в том, что квантор мы имеем право навешивать лишь на переменные, а формула переменной понятное дело не является. Поэтому несмотря на интуитивное желание написать $\forall\psi$, делать мы этого не имеем права. При этом как уже говорилось, любое предложение это некоторая вполне конкретная запись. Предложение не может содержать в себе «некоторую произвольную формулу», потому что в терминах «некоторой произвольной формулы» с формальной точки зрения было бы непонятно как совершать логические выводы и что вообще внутри себя эта формула может иметь.

Поэтому фразу «для каждой формулы $\phi$» надо трактовать как то, что на самом деле для каждой отдельной формулы $\psi$ мы записываем отдельную аксиому Comprehension Scheme с этой вот конкретной формулой. Всего формул у нас бесконечное число, и соответственно аксиом у нас получается бесконечно много. Это, однако, ничему не противоречит, просто это надо иметь ввиду. По этой причине говорят, что $ZF$ — бесконечная система аксиом.

Возможность формировать подмножества с помощью Comprehension Scheme ведёт так же в возможности определить операцию пересечения множеств:

{\bfseries Определение. }$\cap z = \{x \in a| \forall y \in z, x\in y\}$ для произвольного $a \in z$.

Здесь $z$ можно интерпретировать как множество множеств, которые пересекаются операцией $\cap$. Пересечение лишь двух множеств (то что мы определяли ранее) определяется отсюда как $A\cap B = \cap\{A, B\}$.

Возникает желание определить аналогичным образом и объединение множеств. Для объединения, однако, оказывается, что сформулированных до сих пор аксиом недостаточно. Comprehension гарантирует лишь существование подмножеств, но однако для произвольных $a$ и $b$ совершенно не факт, что будет существовать множество, содержащее их обоих. Разным аспектам этого посвящается следующие три аксиомы.

{\bfseries 4. Pairing Axiom}: $\forall a \forall b \exists z (a\in z \wedge b \in z)$.

Напрямую однако эта аксиома не говорит о том, что для любых $a$ и $b$ существует множество $\{a, b\}$. Оно действительно существует, но для того, чтобы его получить, необходимо применить Comprehension Scheme. С помощью Pairing Axiom мы можем гарантировать существование некоторого $z$ который будет содержать $a$ и $b$ в том числе возможно наряду и с некоторыми другими элементами. Однако из этого мы все же можем выразить подмножество $\{a, b\} = \{x \in z| x = a \vee x = b\}$.

Если в рассуждениях выше задать $a = b$, то можно утверждать, что для любого $a$ существует так же множество $\{a\}$, что тоже ранее было не очевидно.

Используя возможность строить множества $\{a, b\}$ мы теперь можем определить и упорядоченные пары как $(a, b) = \{a, \{a, b\}\}$. Выглядит возможно странно, но действительно для множества $\{a, \{a, b\}\}$ всегда можно определить его элементы, и более того их порядок. Это именно то что требовалось от упорядоченных пар, и определить их по-другому конечно было бы можно, но мы все равно как-то были бы обязаны действовать исходя из определения множеств.

{\bfseries 5. Union Axiom:} $\forall f \exists z \forall y \forall x (x \in y \wedge y \in f \rightarrow x \in z)$.

Здесь можно интерпретировать $f$ как некоторое множество множеств, обозначаемых в данном случае как $y$, элементы которых в свою очередь обозначаются как $x$. Множество $z$ — это некоторое множество, содержащее в качестве подмножества все $y \in f$, то есть их объединение. По Comprehension Scheme опять же можно получить и точное объединение множеств:

{\bfseries Определение.} $\cup z = \{x \in a|x\in y, y\in z\}$, где $\forall y (y \subset a)$.

Здесь я для удобства ввёл символ $\subset$. Его можно трактовать как сокращённую форму записи для $\forall x (x\in A \rightarrow x \in B)$, что впрочем мы и определяли в первом параграфе (я просто отмечаю на всякий случай, что в данном случае нет нарушения определённого нами формализма и всё легко определяется).

Аналогично с пересечением можно определить и объединение лишь двух множеств $A\cup B = \cup \{A, B\}$.

Рассмотренные до сих пор аксиомы уже гарантируют нам существование натуральных чисел: для любого $n$ можно определить $x\cup\{x\}$, а так же мы уже имеем $\emptyset$. Не хватает только пока определения функций и отношений, определение которых требует наличия декартова произведения. Его возможно ввести с помощью следующей аксиомы.

{\bfseries 6. Replacement Scheme Axiom:} для каждой формулы $\psi$ со свободными переменными $x, y, v_1, \ldots, v_n$ верно, что $\forall X \forall v_1 \ldots \forall v_n (\forall x\in X \exists ! y \phi(x, y, v_1, \ldots, v_n) \rightarrow \exists Y \forall x \in X \exists y \in Y \phi(x, y, v_1, \ldots, v_n))$.

В этой аксиоме мы использовали сокращение $\exists!y$ для фразы «существует единственный $y$». Запись $\exists!x\phi(x)$ можно рассматривать как сокращённую форму для $\exists x \phi(x) \wedge \neg \exists y (y\not=x \wedge \phi(y))$.

По аналогии с Comprehension Scheme данная аксиома является на самом деле сразу целым набором аксиом, по одной для каждой возможной формулы. Так же по аналогии с Comprehension Scheme переменные $v_1, \ldots, v_n$ служат лишь для обобщения аксиомы и не несут особо глубокого смысла.

Мотивация за этой аксиомой такая: пусть $\phi(x, y)$ — описание некоторой функции $X\to Y$. На самом деле понятия функции у нас пока нет, поэтому правильнее говорить, что это не функция, а формула, такая что $\forall x\in X \exists!y \phi(x, y)$. Логично, что образ этой функции $\{y|\exists x \in X \phi(x, y)\}$ должен являться множеством. Из аксиом 1-5 этого доказать не получится, поэтому это выражает отдельная аксиома Replacement Scheme. Так же как и Pairing Axiom она требует лишь существования некоторого надмножества, содержащего множество $Y$, но далее точное множество $Y$ как обычно можно получить применив Comprehension Scheme.

С помощью Replacement Scheme можно определить декартово произведение. Во-первых вспомним, что для любых $a\in A$ и $b\in B$ мы уже успешно определили упорядоченную пару $(a, b)$. Тогда, если зафиксировать некоторое $b$, можно рассмотреть отображение $a \mapsto (a, b)$. На языке формул это можно записать как $\forall a\in A \exists!z (z = (a, b))$. Образом этого отображения должно быть множество $A\times\{b\} = \{(a, b)| a\in A\}$, которое действительно будет являться множеством по Replacement Scheme.

Определив $A\times\{b\}$ мы можем рассмотреть отображение $b\mapsto A \times \{b\}$ (или в виде формулы $\forall b\in B \exists! z (z = A\times\{b\})$) и по аналогии образом этого отображения будет множество $X = \{A\times \{ b \} | b \in B\}$. Декартово произведение теперь можно определить как $A\times B = \cup X$.

Отсюда можно уже определять отношения, функции, да и вообще все что угодно. Таким образом, всё, рассматриваемое до сих пор, мы смогли определить и доказать используя только первые 6 (даже 5 за вычетом Foundation) аксиом. Следующие аксиомы мы сформулируем очень кратко, так как для наших целей они пока не нужны и потребуются значительно позже, и соответствующие комментарии по их поводу у нас будут позже.

{\bfseries 7. Infinity Axiom:} $\exists x (\emptyset \in x \wedge \forall y \in x ((y\cup\{y\}\in x)))$

Эта аксиома гарантирует, что все натуральные числа все же образует множество $\mathbb{N}$. Без неё мы могли бы работать с натуральными числами, но не могли бы работать с множеством натуральных чисел собственно как со множеством. Например, мы не могли бы определить множество $\mathbb{N}\times\mathbb{N}$, без которых затруднительно определить арифметику отрицательных и рациональных чисел (будет позже в этом курсе).

{\bfseries 8. Power Set Axiom.} $\forall x \exists y \forall z (z\subset x \rightarrow z\in y)$

Гарантирует существование множества $2^X$ для любого $X$. Необходима для определения вещественных чисел (опять же будет позже).

Эти восемь аксиом собственно и образуют аксиоматику ZF. К перечисленным аксиомам почти всегда добавляется ещё следующая «аксиома выбора», вместе с которой аксиоматика носит название ZFC:

{\bfseries 9. Choice Axiom.} Формулировку разобьём на несколько строк:

$\forall A \forall B \forall f\subset A\times B \\(\forall x \in A \exists! y\in B, (x, y)\in f\rightarrow\\ (\exists S\forall y\in B(\exists x\in A, (x, y)\in f \rightarrow \\ \exists!x\in X, (x, y)\in f\cap S\times B)))$

Выглядит, опять же, страшно, но на деле ничего особого. Все, что здесь сказано — это то что из произвольного множества мы можем выбрать некоторый элемент, и на деле формальная запись этой аксиомы никогда не применяется — обычно просто говорят «возьмём некоторый элемент $x$ из множества $X$», и это как раз подразумевает использование аксиомы выбора. Ниже я кратко опишу как выбор элемента из множества связан с формальной записью выше, но это в принципе уже программа максимум — на практике подобные рассуждения да и само приведённое формальное определение совершенно излишни и никем никогда не рассматриваются.

Итак, пусть нам дана функция $f: A\to B$. Каждый $b \in B$ имеет прообразом некоторое множество. Причём для разных $b\in B$ эти прообразы не пересекаются. Мы можем сказать, что на $A$ задано отношение эквивалентности следующим образом: $x\sim y$, если $f(x) = f(y)$. Тогда выбор некоторого элемента из множества — это все равно что выбор элемента из класса эквивалентности. Пусть мы выбрали из каждого такого класса эквивалентности по одному представителю, и сформировали из них множество $S$. Ограничение $f|_S$ будет инъективным. Возможность такого выбора (то есть утверждение аксиомы выбора) эквивалентно возможности такого ограничения произвольной функции $f$, чтобы она стала инъективной.

Осталось формализовать эти понятия. Если $f: A\to B$, то формально это можно записать как $f\subset A\times B \wedge \forall x \in A \exists!y\in B, (x, y)\in f$

Если дополнительно к этому функция $f$ инъективна, то мы можем сказать, что $\forall y\in B (\exists x\in A, (x, y)\in f \rightarrow \exists!x, (x, y)\in f)$. Здесь необходима проверка $\exists x\in A, (x, y)\in f$, чтобы убедиться в том, что конкретный $y\in B$ вообще имеет прообраз.

Теперь, вспомнив, что $f|_S = f\cap S\times B$, мы после некоторых раздумий получаем формулировку аксиомы выбора в том виде, как я её привёл.

Из аксиомы выбора следует множество парадоксов, самый пожалуй душещипательный их которых следующий:

{\bfseries Парадокс Банаха-Тарского.} Любой шар можно разрезать на конечное число кусков, а потом из этих кусков собрать два таких же точно шара.

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