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

Система аксиом фон Неймана — Бернайса — Гёделя (NBG, аксиоматика Гёделя — Бернайса) в метаматематике — одна из основных аксиоматических теорий множеств. Эта система является расширением канонической теории Цермело — Френкеля с аксиомой выбора (ZFC). Предложения, сформулированные на языке теории ZFC, доказуемы в ZFC тогда и только тогда, когда они доказуемы в NBG.

Теория NBG дополнительно включает понятие собственного класса — объекта, имеющего элементы, но который сам не может быть элементом каких-либо объектов. NBG включает только такие определения понятий, которые не ссылаются на определяемое понятие; значения связанных переменных в формулах могут быть только множествами. Исключение этого принципа (отсутствие ссылок на определяемое понятие внутри определений) превращает систему NBG в систему Морза — Келли^[en] (MK). NBG в отличие от ZFC и MK может быть конечно аксиоматизирована (конечным числом аксиом).

Система понятийПравить

Принципиальным в NBG является различие между собственными классами и множествами. Пусть $a$$a$  и $s$$s$  — объекты. Тогда простое высказывание $a\in <!--\; \in \; -->s$$a\in s$  определено, если $a$$a$  — множество, а $s$$s$  — класс; иначе говоря, $a\in <!--\; \in \; -->s$$a\in s$  определено, если $a$$a$  не является собственным классом. Классы могут быть очень большими, в NBG есть даже класс всех множеств, всеобщий класс, называемый $V$$V$ . Однако, в NBG невозможно существование класса всех классов (так как собственный класс не может быть элементом класса) или множество всех множеств (его существование противоречит системе аксиом).

В системе аксиом NBG все объекты, удовлетворяющие всем данным формулам логики первого порядка NBG, образуют класс. Если класс не может удовлетворять системе аксиом ZFC, то он является собственным классом. Развитие классов отражает развитие наивной теории множеств. Принцип абстракции дан, а значит классы могут быть сформированы из всех объектов, удовлетворяющих всем предложениям логики первого порядка; причём простые предложения могут включать отношение принадлежности или предикаты, использующие это отношение. Равенство, операция образования пары элементов, подклассы и другие подобные понятия определяются и не требуют аксиоматизации — их определения означают конкретную абстракцию формулы. Множества описываются методом, близким к ZF. Определим $\mathrm{Rp}<!--\; \; -->(A,a)$$\operatorname {Rp} (A,a)$  (множество $a$$a$  представляет класс $A$$A$ ) — бинарное отношение, определяемое так

$\mathrm{Rp}<!--\; \; -->(A,a):=\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->x\in <!--\; \in \; -->a).$$\operatorname {Rp} (A,a):=\forall x(x\in A\leftrightarrow x\in a).$ 

Это означает, что $a$$a$  представляет $A$$A$ , если все элементы $a$$a$  принадлежат $A$$A$  и наоборот. Классы, не имеющие представляющего их множества, называются собственными классами. Примером собственного класса является класс всех множеств, которые не содержат самих себя (класс, апеллирующий к парадоксу Рассела).

ИсторияПравить

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

Аксиоматизация NBGПравить

Ниже переменные, обозначаемые строчными буквами, обозначают множества, а переменные, обозначаемые заглавными буквами, — классы. Таким образом, $x\in <!--\; \in \; -->y$$x\in y$  обозначает, что множество $x$$x$  принадлежит множества $y$$y$  (является элементом множества $y$$y$ ); а $x\in <!--\; \in \; -->Y$$x\in Y$  обозначает, что множество $x$$x$  является элементом класса $Y$$Y$ . Выражения $x=y$$x=y$ , $x=Y$$x=Y$ , $X=Y$$X=Y$  обозначает, что $\mathrm{\forall <!--\; \forall \; -->}a(a\in <!--\; \in \; -->X\leftrightarrow <!--\; \leftrightarrow \; -->a\in <!--\; \in \; -->Y)$$\forall a(a\in X\leftrightarrow a\in Y)$  (здесь мы не будем полностью соблюдать строгость с целью упрощения). При описании формальной системы мы могли бы пользоваться символами одного типа, при этом множества были бы классами, которые являются членами как минимум одного другого класса.

Сначала мы построим систему аксиом NBG с использованием схемы аксиом порождения классов (схема соответствует бесконечному набору аксиом). Эта схема эквивалентна 9 аксиомам. Таким образом, эти 9 аксиом могут заменить схему порождения классов. Таким образом, NBG конечно аксиоматизируема.

Система аксиом, включающая схему порождения классовПравить

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

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

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

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

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

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

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

Замена схемы порождения подклассов на ряд частных случаевПравить

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

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

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

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

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

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

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

  $\mathrm{Conv1}<!--\; \; -->(R)=\{(b,a)\mid <!--\; \mid \; -->(a,b)\in <!--\; \in \; -->R\},$$\operatorname {Conv1} (R)=\{(b,a)\mid (a,b)\in R\},$ 

  $\mathrm{Conv2}<!--\; \; -->(R)=\{(b,(a,c))|(a,(b,c))\in <!--\; \in \; -->R\}.$$\operatorname {Conv2} (R)={\big \{}{\big (}b,(a,c){\big )}\,{\big |}\,{\big (}a,(b,c){\big )}\in R{\big \}}.$ 

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

  $\mathrm{Assoc1}<!--\; \; -->(R)=\{((a,b),c)|(a,(b,c))\in <!--\; \in \; -->R\},$$\operatorname {Assoc1} (R)={\big \{}{\big (}(a,b),c)\,{\big |}\,{\big (}a,(b,c){\big )}\in R{\big \}},$ 

  $\mathrm{Assoc2}<!--\; \; -->(R)=\{(d,(a,(b,c)))|(d,((a,b),c)))\in <!--\; \in \; -->R\}.$$\operatorname {Assoc2} (R)={\Big \{}{\Big (}d,{\big (}a,(b,c){\big )}{\Big )}\,{\Big |}\,{\Big (}d,{\big (}(a,b),c){\big )}{\Big )}\in R\}.$ 

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

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

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

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

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

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

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

Вариант МендельсонаПравить

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

• B6 $\mathrm{\forall <!--\; \forall \; -->}X\mathrm{\exists <!--\; \exists \; -->}Y\mathrm{\forall <!--\; \forall \; -->}uvw[(u,v,w)\in <!--\; \in \; -->Y\leftrightarrow <!--\; \leftrightarrow \; -->(v,w,u)\in <!--\; \in \; -->X],$$\forall X\,\exists Y\,\forall uvw\,[(u,v,w)\in Y\leftrightarrow (v,w,u)\in X],$ 
• B7 $\mathrm{\forall <!--\; \forall \; -->}X\mathrm{\exists <!--\; \exists \; -->}Y\mathrm{\forall <!--\; \forall \; -->}uvw[(u,v,w)\in <!--\; \in \; -->Y\leftrightarrow <!--\; \leftrightarrow \; -->(u,w,v)\in <!--\; \in \; -->X].$$\forall X\,\exists Y\,\forall uvw\,[(u,v,w)\in Y\leftrightarrow (u,w,v)\in X].$ 

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

ДискуссииПравить

Ознакомиться с философскими и онтологическими вопросами, вызванными NBG, особенно в связи с различиями с ZFC и MK можно в приложении C книги Potter (2004).

Несмотря на то, что NBG является расширением ZFC, некоторые теоремы могут более просто элегантно доказываться в NBG, чем в ZFC (или наоборот). Для обзора известных результатов в этой области см. Pudlak (1998).

Теория моделейПравить

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

• $V_k$$V_{k}$  — это модель ZFC.
• $\mathrm{Def}<!--\; \; -->(X)$$\operatorname {Def} (X)$  — это модель NBG,
• $V_{k+1}$$V_{{k+1}}$  — это модель MK.

Теория категорийПравить

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

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

СсылкиПравить

• von Neumann, John (1928), Die Axiomatisierung der Mengenlehre, Mathematische Zeitschrift Т. 27: 669–752, doi:10.1007/bf01171122, <http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN266833020_0027&DMDID=DMDLOG_0042> .
• von Neumann, John (1929), Über eine Widerspruchsfreiheitsfrage in der axiomatischen Mengenlehre, Journal für die Reine und Angewandte Mathematik Т. 160: 227–241, <http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0160&DMDID=DMDLOG_0019> .