Система аксиом фон Неймана — Бернайса — Гёделя

Первый вариант NBG включал функции, а не множества, как базовые понятия (фон Нейман, 1920-е годы). В серии статей, опубликованных в 1937—1954 годах, Пол Бернайс изменил теорию фон Неймана, сделав множества и отношение принадлежности базовыми понятиями; он также обнаружил, что эту теорию можно аксиоматизировать конечным числом аксиом. Гёдель (1940) во время исследования независимости континуум-гипотезы упростил и использовал теорию. Монтегю показал, что ZFC не может быть конечно аксиоматизировано.

Следующие 5 аксиом совпадают с соответствующими аксиомами ZFC

• Аксиома экстенсиональности. ${\displaystyle \forall x(x\in a\leftrightarrow x\in b)\rightarrow a=b}$. Множества, содержащие одинаковые элементы, равны.
• Аксиома существования пары. ${\displaystyle \forall x\forall y\exists z\forall w(w\in z\leftrightarrow (w=x\lor w=y))}$. Для каждого множества ${\displaystyle x}$ и для каждого множества ${\displaystyle y}$ существует множество ${\displaystyle {x,y}}$, элементами которого являются только ${\displaystyle x}$ и ${\displaystyle y}$). Из аксиомы существования пары (полагая ${\displaystyle x=y}$) следует, что для каждого множества ${\displaystyle x}$ существует множество, состоящее только из одного элемента: ${\displaystyle {x}}$. Далее, можно определить упорядоченную пару множеств ${\displaystyle (a,\;b)}$ как, например, ${\displaystyle \{\{a\},\;\{a,\;b\}\}}$. Используя схему порождения класса подклассов (см. ниже) получаем, что любое отношение также является классом. Некоторые из этих отношений являются функциями одной или нескольких переменных, инъекциями, биекциями из одного класса в другой. Аксиома существования пары является аксиомой в теории множеств Цермело и теоремой в ZFC.
• Аксиома объединения. Для каждого множества ${\displaystyle x}$ существует множество состоящее в точности из всех элементов элементов ${\displaystyle x}$.
• Аксиома множества подмножеств. Для каждого множества ${\displaystyle x}$ существует множество состоящее в точности из всех подмножеств ${\displaystyle x}$.
• Аксиома бесконечности. Существует множество ${\displaystyle x}$, которое удовлетворяет двум условиям: пустое множество принадлежит ${\displaystyle x}$; для каждого ${\displaystyle y}$, принадлежащего ${\displaystyle x}$, множество ${\displaystyle \{y,\;\{y\}\}}$ также принадлежит ${\displaystyle x}$. Эту аксиому можно сформулировать так, что существование пустого множества будет подразумеваться[3].

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

• Аксиома экстенсиональности (для классов). ${\displaystyle \forall x(x\in A\leftrightarrow x\in B)\rightarrow A=B}$. Классы с одинаковыми элементами — это равные классы.
• Аксиома регулярности. Каждый непустой класс ${\displaystyle A}$ содержит элемент, пересечение которого с ${\displaystyle A}$ пусто.

Последние две аксиомы являются отличительной особенностью NBG.

• Аксиома ограничения мощности. Для каждого класса ${\displaystyle C}$ множество ${\displaystyle c}$ удовлетворяющее условию ${\displaystyle c=C}$ существует тогда и только тогда, когда нет биекции между ${\displaystyle C}$ и классом ${\displaystyle V}$ всех множеств. Из этой аксиомы, принадлежащей фон Нейману, могут быть выведены схема аксиом выделения подмножеств, схема аксиом преобразования и аксиома глобального выбора. В частности, аксиома глобального выбора может быть выведена поскольку класс ординалов не является множеством; поэтому есть биекция между классом всех ординалов и ${\displaystyle V}$. Если аксиому ограничения мощности ослабить до следующей: если область определения функции классов является множество, то и область значений также является множеством — то ни в какой форме аксиома выбора не является теоремой NBG. В этом случае аксиому выбору в любой из форм можно добавить как аксиому, если это необходимо. Аксиома выбора в такой форме может быть найдена в Mendelson (1997) NGB. Там мы находим обычную аксиому выбора для множеств, и следующую форму схемы аксиом преобразования: если класс ${\displaystyle F}$ — это функция, чья область определения — это множество, то её область значений тоже множество[4]
• Схема аксиом порождения подклассов. Для каждой формулы ${\displaystyle \varphi }$, не содержащей кванторов для переменных-классов (формула может содержать переменные-классы как параметры) существует класс ${\displaystyle A}$ такой, что ${\displaystyle \forall x(x\in A\leftrightarrow \varphi (x))}$. Эта аксиома утверждает принцип неограниченного выделения (подмножеств) наивной теории множеств. Однако, классы предпочтительнее множеств, так как исключаются парадоксы из теории множеств.

Схема аксиом порождения подклассов — единственная схема в NBG. Ниже мы покажем, как эту схему можно заменить на ряд частных случаев, в результате чего NBG станет конечно аксиоматизируемой. Если связанные переменные в формуле ${\displaystyle \varphi (x)}$ смогут пробегать классы (а не только множества), то мы получим теорию множеств Морза — Келли, собственное расширение ZFC, которое не может быть конечно аксиоматизировано.

Привлекательная и несколько загадочная особенность NBG состоит в том, что схему порождения подклассов можно заменить на несколько аксиом, описывающих частные случаи. Нижеприведенные аксиомы могут полностью заменить схему порождения подклассов. Способ аксиоматизации, приведенной ниже, не обязательно совпадает с той, что можно найти в печатных источниках[5].

Мы опишем нашу аксиоматизацию путём описания структуры формул. Во-первых, нам необходимо иметь первоначальный запас классов.

• Множества. Для каждого множества ${\displaystyle x}$ существует класс ${\displaystyle X}$ такой, что ${\displaystyle X=x}$. Эта аксиома вместе с аксиомами существования множеств предыдущего раздела позволяет получить начальный набор классов и позволит нам составлять формулы с классами как параметрами.

Далее опишем способ, с помощью которого мы будем формировать выражения логики высказываний. Пусть ${\displaystyle A={x|\varphi }}$ и ${\displaystyle B={x|\psi }}$. Тогда ${\displaystyle \{x|\lnot \varphi \}=V-A}$, ${\displaystyle \{x|\varphi \vee \psi \}=A\cup B}$. Так как с помощью операций ${\displaystyle \lnot }$ и ${\displaystyle \land }$ можно записать любые выражения логики высказываний, нам достаточно определить дополнение и пересечение классов.

• Дополнение. Для каждого класса ${\displaystyle A}$ дополнение ${\displaystyle V-A=\{x|x\notin A\}}$ является классом.
• Пересечение. Для любых классов ${\displaystyle A}$ и ${\displaystyle B}$ пересечение ${\displaystyle A\cap B=\{x|x\in A\land x\in B\}}$ является классом.

Теперь мы начнем двигаться в сторону включения кванторов в формулы. Для того чтобы использовать несколько переменных нам необходимо уметь описывать отношения. Определим упорядоченную пару ${\displaystyle a}$ и ${\displaystyle b}$ как обычно: ${\displaystyle \{\{a\},\{a,b\}\}}$. Далее опишем аксиомы, использующие упорядоченные пары:

• Произведение. Для любых классов ${\displaystyle A}$ и ${\displaystyle B}$ произведение ${\displaystyle A\times B=\{(a,\;b)|a\in A\land b\in B\}}$ является классом (на практике нам понадобится только ${\displaystyle V\times A}$).
• Перестановки. Для любого класса ${\displaystyle R}$ существуют классы:

${\displaystyle \mathrm {Conv1} \ (R)=\{(b,\;a)|(a,\;b)\in R\}}$

${\displaystyle \mathrm {Conv2} \ (R)=\{(b,\;(a,\;c))|(a,\;(b,\;c))\in R\}}$

• Ассоциативность. Для любого класса ${\displaystyle R}$ существуют классы:

${\displaystyle \mathrm {Assoc1} \ (R)=\{((a,\;b),\;c)|(a,\;(b,\;c))\in R\}}$

${\displaystyle \mathrm {Assoc2} \ (R)=\{(d,\;(a,\;(b,\;c))|(d,\;((a,\;b),\;c)))\in R\}}$

Эти аксиомы позволяют добавлять фиктивные аргументы, а также изменять порядок аргументов в отношениях любой арности. Особая форма ассоциативности разработана специально для того, чтобы можно было переносить любое выражение из списка в начало списка (разумеется также с использованием перестановок). Мы представляем список аргументов ${\displaystyle (x_{1},\;x_{2},\;\ldots ,\;x_{n})}$ как ${\displaystyle (x_{1},\;(x_{2},\;\ldots ,\;x_{n}))}$ (то есть как пару голова (первый аргумент) и хвост (остальные аргументы)). Идея состоит в том, чтобы применять ${\displaystyle \mathrm {Assoc1} }$ пока интересующий нас аргумент не станет вторым, затем применить ${\displaystyle \mathrm {Assoc1} }$ или ${\displaystyle \mathrm {Assoc2} }$, а затем применять ${\displaystyle \mathrm {Assoc2} }$ пока не нивелируется использование ${\displaystyle \mathrm {Assoc1} }$.

Далее мы хотим аксиоматизировать следующий набор утверждений: если ${\displaystyle \{(x,\;y)|\varphi (x,\;y)\}}$ — класс представляющий собой отношение, то его область значений ${\displaystyle \{y|\exists x\;\varphi (x,\;y)\}}$ — это класс.

• Области значений. Для каждого класса ${\displaystyle R}$ существует класс ${\displaystyle \mathrm {Rng} \ (R)=\{y|\exists x\;(x,\;y)\in R\}}$.

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

Наконец, каждая простая формула подразумевает существование следующих отношений на классах:

• Принадлежность. Существует класс ${\displaystyle [\in ]=\{(x,\;y)|x\in y\}}$.
• Диагональный класс. Существует класс ${\displaystyle [=]=\{(x,\;y)|x=y\}}$.

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

Мендельсон ссылается на свои аксиомы B1 — B7 как на аксиомы существования классов. Четыре из них совпадают с приведенными выше: B1 — принадлежность; B2 — пересечение; B3 — дополнение; B5 — умножение. B4 — область значений приведена в форме существования области определения (квантор существования стоит у ${\displaystyle y}$, а не у ${\displaystyle x}$). Последние две аксиомы следующие:

• B6 ${\displaystyle \forall X\exists Y\forall uvw[(u,\;v,\;w)\in Y\leftrightarrow (v,\;w,\;u)\in X]}$
• B7 ${\displaystyle \forall X\exists Y\forall uvw[(u,\;v,\;w)\in Y\leftrightarrow (u,\;w,\;v)\in X]}$

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

ZFC, MK, NBG имеют модель, определяемую с использованием ${\displaystyle V}$ (стандартная модель в ZFC и универсум в NBG). Теперь пусть ${\displaystyle V}$ включает недостижимое кардинальное число ${\displaystyle k}$. Обозначим ${\displaystyle \mathrm {Def} \ (x)}$ ${\displaystyle \Delta _{0}}$ определяемые подмножества ${\displaystyle X}$. Тогда

• ${\displaystyle V_{k}}$ — это модель ZFC
• ${\displaystyle \mathrm {Def} (X)}$ — это модель NBG
• ${\displaystyle V_{k+1}}$ — это модель MK.

Система понятий NBG позволяет говорить о больших объектах без риска наткнуться на парадокс. В частности во многих трактовках теории категорий под большой категорией подразумевается категория, где набор объектов является собственным классом, как и набор морфизмов. Малые категории, с другой стороны, — это категории, где наборы объектов и морфизмов являются множествами. Поэтому мы можем без риска парадоксов говорить о категории всех множеств или категории всех малых категорий. Эти категории, разумеется, большие. Но нельзя говорить о категории всех категорий, так как она должна была бы включать категорию всех малых категорий. Однако существуют другие расширения систем понятий, которые позволяют говорить о наборе всех категорий как категории (см. о квазикатегории всех категорий в Adámek et al. (1990)).

Системы понятий, включающей классы и множества, достаточно для обоснования теории категорий (Muller, 2001).