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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Система аксиом фон Неймана — Бернайса — Гёделя (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. Определим Rp(A,a) (множество a представляет класс A) — бинарное отношение, определяемое так:

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; а 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 \exist z \forall w (w \in z \leftrightarrow (w=x \or w=y)). Для каждого множества x и для каждого множества y существует множество {x,y}, элементами которого являются только x и y). Из аксиомы существования пары (полагая x=y) следует, что для каждого множества x существует множество, состоящее только из одного элемента: {x}. Далее, можно определить упорядоченную пару множеств (a,b) как, например, \{\{a\},\{a,b\}\}. Используя схему порождения класса подклассов (см. ниже) получаем, что любое отношение также является классом. Некоторые из этих отношений являются функциями одной или нескольких переменных, инъекциями, биекциями из одного класса в другой. Аксиома существования пары является аксиомой в теории множеств Цермело и теоремой в ZFC.
  • Аксиома объединения. Для каждого множества x существует множество состоящее в точности из всех элементов элементов x.
  • Аксиома множества подмножеств. Для каждого множества x существует множество состоящее в точности из всех подмножеств x.
  • Аксиома бесконечности. Существует множество x, которое удовлетворяет двум условиям: пустое множество принадлежит x; для каждого y, принадлежащего x, множество \{y,\{y\}\} также принадлежит 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]
  • Схема аксиом порождения подклассов. Для каждой формулы \phi, не содержащей кванторов для переменных-классов (формула может содержать переменные-классы как параметры) существует класс A такой, что \forall x (x \in A \leftrightarrow \phi (x)). Эта аксиома утверждает принцип неограниченного выделения (подмножеств) наивной теории множеств. Однако, классы предпочтительнее множеств, так как исключаются парадоксы из теории множеств.

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

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

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

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

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

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

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

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

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


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


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

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


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


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

Эти аксиомы позволяют добавлять фиктивные аргументы, а также изменять порядок аргументов в отношениях любой арности. Особая форма ассоциативности разработана специально для того, чтобы можно было переносить любое выражение из списка в начало списка (разумеется также с использованием перестановок). Мы представляем список аргументов (x_1,x_2,\dots,x_n) как (x_1,(x_2,\dots,x_n) (то есть как пару голова (первый аргумент) и хвост (остальные аргументы)). Идея состоит в том, чтобы применять \mathrm{Assoc1} пока интересующий нас аргумент не станет вторым, затем применить \mathrm{Assoc1} или \mathrm{Assoc2}, а затем применять \mathrm{Assoc2} пока не нивелируется использование \mathrm{Assoc1}.

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

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

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

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

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

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

Вариант Мендельсона[править | править исходный текст]

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

  • B6 \forall X \exist Y \forall uvw [(u,v,w)\in  Y \leftrightarrow (v,w,u)\in X]
  • B7 \forall X \exist 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. Обозначим \mathrm{Def}\ (x) \Delta_0 определяемые подмножества X. Тогда

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

Теория категорий[править | править исходный текст]

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

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

Примечания[править | править исходный текст]

  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

Литература[править | править исходный текст]

  • Adámek Jiří Abstract and Concrete Categories (The Joy of Cats). — New York: Wiley & Sons, 2004. — ISBN 0-471-60922-6
  • Bernays, Paul Axiomatic Set Theory. — Dover Publications, 1991. — ISBN 0-486-66637-9
  • Mendelson, Elliott, 1997. An Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall. ISBN 0-412-80830-7. 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.
  • Richard Montague, 1961, «Semantic Closure and Non-Finite Axiomatizability I,» in Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, (Warsaw, 2-9 September 1959). Pergamon: 45-69.
  • Muller, F. A., 2001, "Sets, classes, and categories, " British Journal of the Philosophy of Science 52: 539-73.
  • Potter, Michael, 2004. Set Theory and Its Philosophy. Oxford Univ. Press.
  • Pudlak, P., 1998, «The lengths of proofs» in Buss, S., ed., Handbook of Proof Theory. North-Holland: 547—637.
  • John von Neumann, 1925, «An Axiomatization of Set Theory.» English translation in Jean van Heijenoort, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879—1931. Harvard University Press. 393—413