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

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

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

Система понятий

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

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

$\operatorname {Rp} (A,a):=\forall x(x\in A\leftrightarrow x\in a).$

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

История

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

Аксиоматизация NBG

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\operatorname {Conv2} (R)={\big \{}{\big (}b,(a,c){\big )}\,{\big |}\,{\big (}a,(b,c){\big )}\in R{\big \}}.$
Ассоциативность. Для любого класса $R$ существуют классы
$\operatorname {Assoc1} (R)={\big \{}{\big (}(a,b),c)\,{\big |}\,{\big (}a,(b,c){\big )}\in R{\big \}},$

$\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},\ldots ,x_{n})$ как ${\big (}x_{1},(x_{2},\ldots ,x_{n}){\big )}$ (то есть как пару голова (первый аргумент) и хвост (остальные аргументы)). Идея состоит в том, чтобы применять $\operatorname {Assoc1}$ пока интересующий нас аргумент не станет вторым, затем применить $\operatorname {Assoc1}$ или $\operatorname {Assoc2}$ , а затем применять $\operatorname {Assoc2}$ пока не нивелируется использование $\operatorname {Assoc1}$ .

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

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

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

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

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

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

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

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

B6 $\forall X\,\exists Y\,\forall uvw\,[(u,v,w)\in Y\leftrightarrow (v,w,u)\in X],$
B7 $\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$ (стандартная модель в ZFC и универсум в NBG). Теперь пусть $V$ включает недостижимое кардинальное число $k$ . Обозначим $\operatorname {Def} (x)$ $\Delta _{0}$ определяемые подмножества $X$ . Тогда

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

Теория категорий

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

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

Примечания

↑ Термин англ. proper class переведён как собственный класс согласно переводной книге С. Маклейна «Категории для работающего математика».
↑ Mendelson (1997), с. 232, Предложение 4.4 доказывает, что схема порождения классов эквивалентна аксиомам B1—B7 описанных на с. 230.
↑ Mendelson (1997), p. 239, Ex. 4.22(b).
↑ Mendelson (1997), p. 239, axiom R.
↑ Данная статья — перевод с английской Wikipedia.

Литература

Adámek, Jiří; Herrlich, Horst; Strecker, George E. (1990), Abstract and Concrete Categories (The Joy of Cats) (1st ed.), New York: Wiley & Sons, ISBN 978-0-471-60922-3
Bernays, Paul (1937), "A System of Axiomatic Set Theory—Part I", The Journal of Symbolic Logic, 2 (1): 65—77, doi:10.2307/2268862, JSTOR 2268862
Bernays, Paul (1941), "A System of Axiomatic Set Theory—Part II", The Journal of Symbolic Logic, 6 (1): 1—17, doi:10.2307/2267281, JSTOR 2267281
Bernays, Paul (1991), Axiomatic Set Theory (2nd Revised ed.), Dover Publications, ISBN 978-0-486-66637-2
Bourbaki, Nicolas (2004), Elements of Mathematics: Theory of Sets, Springer, ISBN 978-3-540-22525-6
Chuaqui, Rolando (1981), Axiomatic Set Theory: Impredicative Theories of Classes, North-Holland, ISBN 0-444-86178-5
Cohen, Paul (1963), "The Independence of the Continuum Hypothesis", Proceedings of the National Academy of Sciences of the United States of America, 50 (6): 1143—1148, Bibcode:1963PNAS...50.1143C, doi:10.1073/pnas.50.6.1143, PMC 221287, PMID 16578557
Cohen, Paul (1966), Set Theory and the Continuum Hypothesis, W. A. Benjamin
Dawson, John W. (1997), Logical dilemmas: The life and work of Kurt Gödel, Wellesley, MA: AK Peters
Easton, William B. (1964), Powers of Regular Cardinals (PhD thesis), Princeton University
Felgner, Ulrich (1971), "Comparison of the axioms of local and universal choice" (PDF), Fundamenta Mathematicae, 71: 43—62, doi:10.4064/fm-71-1-43-62
Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised ed.), Basel, Switzerland: Birkhäuser, ISBN 978-3-7643-8349-7
Gödel, Kurt (1940), The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory (Revised ed.), Princeton University Press, ISBN 978-0-691-07927-1
Gödel, Kurt (1986), Collected Works, Volume 1: Publications 1929–1936, Oxford University Press, ISBN 978-0-19-514720-9
Gödel, Kurt (1990), Collected Works, Volume 2: Publications 1938–1974, Oxford University Press, ISBN 978-0-19-514721-6
Gödel, Kurt (2003), Collected Works, Volume 4: Correspondence A–G, Oxford University Press, ISBN 978-0-19-850073-5
Gray, Robert (1991), "Computer programs and mathematical proofs", The Mathematical Intelligencer, 13 (4): 45—48, doi:10.1007/BF03028342, S2CID 121229549
Hallett, Michael (1984), Cantorian Set Theory and Limitation of Size (Hardcover ed.), Oxford: Clarendon Press, ISBN 978-0-19-853179-1
Kanamori, Akihiro (2009b), The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings, Springer, ISBN 978-3-540-88867-3
Kanamori, Akihiro (2009), "Bernays and Set Theory" (PDF), Bulletin of Symbolic Logic, 15 (1): 43—69, doi:10.2178/bsl/1231081769, JSTOR 25470304, S2CID 15567244
Kanamori, Akihiro (2012), "In Praise of Replacement" (PDF), Bulletin of Symbolic Logic, 18 (1): 46—90, doi:10.2178/bsl/1327328439, JSTOR 41472440, S2CID 18951854
Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs (Hardcover ed.), North-Holland, ISBN 978-0-444-86839-8
Mendelson, Elliott (1997), An Introduction to Mathematical Logic (4th ed.), London: Chapman and Hall/CRC, ISBN 978-0-412-80830-2 — pp. 225–86 contain the classic textbook treatment of NBG, showing how it does what we expect of set theory, by grounding relations, order theory, ordinal numbers, transfinite numbers, etc.
Mirimanoff, Dmitry (1917), "Les antinomies de Russell et de Burali-Forti et le problème fondamental de la théorie des ensembles", L'Enseignement Mathématique, 19: 37—52
Montague, Richard (1961), "Semantic Closure and Non-Finite Axiomatizability I", in Buss, Samuel R. (ed.), Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Pergamon Press, pp. 45—69
Mostowski, Andrzej (1950), "Some impredicative definitions in the axiomatic set theory" (PDF), Fundamenta Mathematicae, 37: 111—124, doi:10.4064/fm-37-1-111-124
Muller, F. A. (1 September 2001), "Sets, classes, and categories" (PDF), British Journal for the Philosophy of Science, 52 (3): 539—73, doi:10.1093/bjps/52.3.539
Müller, Gurt, ed. (1976), Sets and Classes: On the Work of Paul Bernays, Studies in Logic and the Foundations of Mathematics Volume 84, Amsterdam: North Holland, ISBN 978-0-7204-2284-9
Potter, Michael (2004), Set Theory and Its Philosophy: A Critical Introduction (Hardcover ed.), Oxford University Press, ISBN 978-0-19-926973-0
Pudlák, Pavel (1998), "The Lengths of Proofs" (PDF), in Buss, Samuel R. (ed.), Handbook of Proof Theory, Elsevier, pp. 547—637, ISBN 978-0-444-89840-1
Smullyan, Raymond M.; Fitting, Melvin (2010) [Revised and corrected edition: first published in 1996 by Oxford University Press], Set Theory and the Continuum Problem, Dover, ISBN 978-0-486-47484-7
Solovay, Robert M. (1990), "Introductory note to 1938, 1939, 1939a and 1940", Kurt Gödel Collected Works, Volume 2: Publications 1938–1974, Oxford University Press, pp. 1—25, ISBN 978-0-19-514721-6
von Neumann, John (1923), "Zur Einführung der transfiniten Zahlen", Acta Litt. Acad. Sc. Szeged X., 1: 199—208
von Neumann, John (1925), "Eine Axiomatisierung der Mengenlehre", Journal für die Reine und Angewandte Mathematik, 154: 219—240

Ссылки

von Neumann, John (1928), "Die Axiomatisierung der Mengenlehre", Mathematische Zeitschrift, 27: 669—752, doi:10.1007/bf01171122, S2CID 123492324.
von Neumann, John (1929), "Über eine Widerspruchsfreiheitsfrage in der axiomatischen Mengenlehre", Journal für die Reine und Angewandte Mathematik, 160: 227—241.

[1] Термин англ. proper class переведён как собственный класс согласно переводной книге С. Маклейна «Категории для работающего математика».

[2] Mendelson (1997), с. 232, Предложение 4.4 доказывает, что схема порождения классов эквивалентна аксиомам B1—B7 описанных на с. 230.

[3] Mendelson (1997), p. 239, Ex. 4.22(b).

[4] Mendelson (1997), p. 239, axiom R.

[5] Данная статья — перевод с английской Wikipedia.

[1]

[2]

[3]

[4]

[5]