Теорія множин фон Неймана — Бернайса — Геделя

Теорія множин та класів фон Ноймана — Бернайса — Геделя (скорочено NBG) — аксіоматична теорія першого порядку, що є (консервативним) розширенням теорії множин ZF Цермело — Френкеля. На відміну від ZF, NBG є скінченно аксіоматизовною теорією, яка дозволяє вільно оперувати як множинами, так і класами. Окрім стандартних логічних зв'язок, кванторів та символу рівності, мова теорії NBG включає символ бінарного відношення $\in$ , що інтерпретується як належність.

Первинними (тобто неозначуваними) поняттями теорії NBG є поняття класу та елемента. Клас $X$ може бути елементом іншого класу $Y$, це позначається як $X\in Y$. Позначення $X\notin Y$ є скороченим записом формули $\neg (X\in Y)$.

Два класи $X,Y$ називають рівними, якщо вони складаються з однакових елементів, тобто $X=Y$, якщо $\forall z\;(z\in X\Leftrightarrow z\in Y)$.

Клас $X$ називається множиною, якщо він є елементом деякого класу, тобто якщо $\exists Y\;(X\in Y)$. Клас, який не є множиною, називають властивим класом (англ. proper class). Щоб розрізняти класи та множини, для позначення класів вживають великі літери, а для множин — малі. Властиві класи позначають великими товстими літерами. Прикладом такого класу є клас $\mathbf {V}$ усіх множин.

Розрізнення класів та множин дозволяє уникнути відомого парадоксу Рассела, який у випадку NBG стає доведенням того, що клас $\mathbf {A} =\{x:x\notin x\}$ не є множиною.

Система NBG містить 13 аксіом і може доповнюватися аксіомою (глобального) вибору або аксіомою конструктивності.

Аксіоми NBG

Аксіома рівності

$\forall X\;\forall Y\;(X=Y\;\Rightarrow \;\forall Z\;(X\in Z\;\Leftrightarrow \;Y\in Z))$

З аксіоми рівності випливає, що рівні класи неможливо розрізними відношенням належності.

Клас $X$ називається підкласом класу $Y$, якщо кожен елемент класу $X$ є елементом класу $Y$. У цьому випадку пишемо $X\subseteq Y$.

Тобто, $X\subseteq Y\;\Leftrightarrow \;\forall z\;(z\in X\;\Rightarrow \;z\in Y)$. .

Підклас $X$ класу $Y$ називаємо підмножиною класу $Y$, якщо $X$ є множиною.

Аксіома пари

$\forall x\;\forall y\;\exists z\;\forall u\;(u\in z\;\Leftrightarrow \;(u=x\;\vee \;u=y))$

Аксіома пари постулює, що для довільних множин $x,y$ існує множина $z$, єдиними елементами якої є множини $x,y$. Така множина $z$ називається невпорядкованою парою множин $x,y$ і позначається символом $\{x,y\}$. З аксіоми рівності випливає рівність $\{x,y\}=\{y,x\}$. Невпорядкована пара $\{x,x\}$ позначається символом $\{x\}$ і називається синґлетоном.

Впорядкованою парою $\langle x,y\rangle$ множин $x,y$ називається множина $\{\{x\},\{x,y\}\}$.

З аксіоми рівності випливає

Теорема. $\forall x\;\forall y\;\forall a\;\forall b\;\;(\langle x,y\rangle =\langle a,b\rangle \;\Leftrightarrow \;(x=a\;\wedge \;y=b))$.

Ця теорема стверджує, що впорядковані пари $\langle x,y\rangle$ і $\langle a,b\rangle$ рівні тоді і лише тоді, коли $x=a$ і $y=b$.

Впорядкованою трійкою множин $x,y,z$ називається множина $\langle \langle x,y\rangle ,z\rangle$.

Впорядковані $n$-ки $\langle x_{1},\dots ,x_{n}\rangle$ множин $x_{1},\dots ,x_{n}$ означуються рекурсивною формулою: $\langle x_{1},\dots ,x_{n}\rangle =\langle \langle x_{1},\dots ,x_{n-1}\rangle ,x_{n}\rangle$ для $n\geq 3$.

Наступні 5 аксіом називають аксіомами існування класів.

Аксіома належності

$\exists \mathbf {E} \;\forall x\;\forall y\;(\langle x,y\rangle \in \mathbf {E} \;\Leftrightarrow \;x\in y)$

Аксіома належності постулює існування класу $\mathbf {E} =\{\langle x,y\rangle :x\in y\}$.

Аксіома Інверсії

$\forall X\;\exists Y\;\forall u\;\forall v\;\;(\langle u,v\rangle \in X\;\Leftrightarrow \;\langle v,u\rangle \in Y)$

Аксіома інверсії стверджує, що для кожного класу $X$ існує клас $X^{-1}=\{\langle x,y\rangle :\langle y,x\rangle \in X\}$.

Клас $X$ називається відношенням, якщо $X=(X^{-1})^{-1}$.

Клас є відношенням тоді і лише тоді, коли його елементами є впорядковані пари, тобто $\forall y\;(y\in X\;\Rightarrow \;\exists u\exists v\;(y=\langle u,v\rangle ))$.

Аксіома проєкції

$\forall F\;\exists D\;\forall x\;(x\in D\;\Leftrightarrow \;(\exists y\;\langle x,y\rangle \in F))$

Згідно з аксіомами проєкції та інверсії, для кожного класу $F$ існують класи ${\mathsf {dom}}(F)=\{x:\exists y\;\langle x,y\rangle \in F\}$ та ${\mathsf {rng}}(F)={\mathsf {dom}}(F^{-1})$. Якщо клас $F$ є відношенням (наприклад, функцією), то класи ${\mathsf {dom}}(F)$ та ${\mathsf {rng}}(F)$ називають областю визначення та областю значень відношення $F$.

З аксіом належності та проєкції випливає, що клас усіх множин $\mathbf {V} =\{x:\exists y\;(x\in y)\}$ існує, оскільки він збігається з областю визначення відношення належності $\mathbf {E}$.

Аксіома різниці

$\forall X\;\forall Y\;\exists Z\;\forall u\;(u\in Z\;\Leftrightarrow \;(u\in X\;\wedge \;u\notin Y))$

Аксіома різниці стверджує, що для довільних класів $X$, $Y$ існує клас $X\setminus Y=\{x:x\in X\;\wedge \;x\notin Y\}$.

З аксіоми різниці випливає існування порожнього класу $\emptyset =\mathbf {V} \setminus \mathbf {V}$, що не містить жодних елементів. За означенням рівності, порожній клас єдиний.

Аксіома різниці також дозволяє нам визначити перетин $X\cap Y$ класів $X,Y$ як клас $X\setminus (X\setminus Y)$. За означенная рівності, $X\cap Y=\{x:x\in X\;\wedge \;x\in Y\}$.

Об'єднанням $X\cup Y$ двох класів $X,Y$ називають клас $\{x:x\in X\;\vee \;y\in Y\}$, який рівний класу $\mathbf {V} \setminus ((\mathbf {V} \setminus X)\cap (\mathbf {V} \setminus Y))$, що існує за аксіомою різниці.

Аксіома добутку

$\forall X\;\forall Y\;\exists Z\;\forall u\;\forall v\;(\langle u,v\rangle \in Z\;\Leftrightarrow \;(u\in X\;\wedge \;v\in Y))$

Аксіома добутку постулює, що для довільних класів $X,Y$ існує їх декартів добуток $X\times Y=\{\langle x,y\rangle :x\in X,\;y\in Y\}$.

Для відношення $F$ та класу $X$ клас $F[X]=\{y:\exists x\in X\;\langle x,y\rangle \in F\}$ називають образом класу $X$ при відношенні $F$. Клас $F[X]$ існує, оскільки він рівний класу ${\mathsf {rng}}[F\cap (X\times V)]$. Клас $F^{-1}[X]$ називають прообразом класу $X$ при відношенні $F$.

Відношення $F$ називається функцією (або відображенням), якщо для довільних пар $\langle x,y\rangle ,\langle a,b\rangle \in F$ із рівності $x=a$ випливає рівність $y=b$. Із цього означення випливає, що для довільної функції $F$ та елемента $x\in {\mathsf {dom}}[F]$ існує єдиний елемент $y\in {\mathsf {rng}}[F]$ такий, що $\langle x,y\rangle \in F$. Цей єдиний елемент $y$ позначається через $F(x)$. При цьому круглі дужки використовуються, що відрізнити елемент $F(x)$ від класу $F[x]={\mathsf {rng}}[F\cap (x\times \mathbf {V} )]=\{F(y):y\in x\}$. Для функції $F$ запис $F:X\to Y$ означає, що ${\mathsf {dom}}[F]=X$ і ${\mathsf {rng}}[F]\subseteq Y$. У цьому випадку функція $F$ ставить у відповідність кожному елементу $x\in X$ певний елемент $F(x)$ класу $Y$.

Функція $F$ називається ін'єктивною, якщо відношення $F^{-1}$ теж є функцією.

Хоча властиві класи не можуть бути елементами інших класів, ми можемо говорити про індексовані класи класів. А саме, для довільного класу $A$ кожен підклас $X\subseteq A\times \mathbf {V}$ можна ототожнювати з індексованою сім'єю класів $(X(\alpha ))_{\alpha \in A}$, де $X(\alpha )=\{x:\langle \alpha ,x\rangle \in X\}$ для $\alpha \in A$. У цьому випадку парадокс Рассела доводить, що для класу $B=\{\alpha \in A:\langle \alpha ,\alpha \rangle \notin X\}$ не існує елемента $\alpha \in A$ з $B=X_{\alpha }$.

Аксіома циклу

$\forall X\;\exists Y\;\forall u\;\forall v\;\forall w\;\;(\langle u,v,w\rangle \in X\;\Leftrightarrow \;\langle w,u,v\rangle \in Y)$

Аксіома циклу постулює, що для довільного класу $X$ існує клас $\{\langle w,u,v\rangle :\langle u,v,w\rangle \in X\}$, який далі позначатиметься через $X^{\circlearrowright }$ або $[X]^{\circlearrowright }$.

Для довільного класу $X$ клас $\cup X=\{z:\exists y\;(z\in y\;\wedge \;y\in X)\}$ називають об'єднанням класу $X$.

Клас $\cup X$ існує, оскільки він рівний класу ${\mathsf {dom}}[\mathbf {E} \cap (\mathbf {V} \times X)]$.

Для довільного класу $X$ клас $\cap X=\{z:\forall y\;(y\in X\;\Rightarrow \;z\in y)\}$ називають перетином $X$.

Клас $\cap X$ існує, оскільки він рівний класу $\mathbf {V} \setminus {\mathsf {dom}}[(\mathbf {V} ^{2}\setminus \mathbf {E} )\cap (\mathbf {V} \times X)]$.

Із означень випливає, що $\cup \emptyset =\emptyset$ і $\cap \emptyset =\mathbf {V} .$

Для довільного класу $X$ клас $2^{X}=\{y:y\subseteq X\}$ називають експонентою класу $X$.

Клас $2^{X}$ існує, оскільки він рівний класу $\mathbf {V} \setminus {\mathsf {dom}}[\mathbf {E} ^{-1}\cap (\mathbf {V} \times (\mathbf {V} \setminus X))]$. Зокрема, $2^{\mathbf {V} }=\mathbf {V}$.

Аксіома регулярності

$\forall x\;(\exists y\;(y\in x))\;\Rightarrow \;\exists y\;(y\in x\;\wedge \;\forall z\;(z\in y\;\Rightarrow \;z\notin x))$.

Аксіома регулярності стверджує, що довільна непорожня множина $x$ містить елемент $y\in x$, який не має з множиною $x$ спільних елементів. Аксіома регулярності забороняє існування нескінченних спадних ланцюгів виду $x_{1}\ni x_{2}\ni x_{3}\dots$. Аксіома регулярності часто використовується в індуктивних конструкціях.

Використовуючи аксіому регулярності та аксіоми існування класів, Гедель довів (індукцією по складності формули $\phi$) наступну важливу теорему, обмежена форма якої приймається за аксіому вирізання^{[прояснити]} в аксіоматиці Цермело — Френкеля.

Теорема Геделя про існування класів: Нехай $\phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})$ є формулою, у якій квантори пробігають лише по множинах, а вільні змінні містяться серед змінних $x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m}$. Тоді для довільних класів $Y_{1},\dots ,Y_{m}$ клас $\{\langle x_{1},\dots ,x_{n}\rangle :\phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})\}$ існує.

Доступне доведення цієї теореми можна знайти в англійській версії статті про аксіоматику NBG, або в монографії Мендельсона.

Наступні 4 аксіоми називають аксіомами існування множин.

Аксіома заміни

Для довільної функції $F$ та множини $x$, образ $F[x]=\{y:\exists z\;(z\in x\;\wedge \;\langle z,y\rangle \in F)\}$ є множиною.

Аксіома об'єднання

Для довільної множини $x$ її об'єднання $\cup x$ є множиною.

Аксіома експоненти

Для довільної множини $x$ її експонента $2^{x}$ є множиною.

З аксіоми заміни (застосованої до тотожнього відображення класу в себе) випливає, що перетин множини та класу є множиною; тому для довільної множини усі її підкласи є множинами.

Проте з усіх наведених вище аксіом ще не випливає, що хоча б одна множина існує. Існування множин (навіть нескінченних) забезпечує

Аксіома нескінченності

$\exists x\;(\emptyset \in x\;\wedge \;\forall n\;(n\in x\;\Rightarrow \;n\cup \{n\}\in x))$

Аксіома нескінченності постулює існування індуктивної множини. Клас $x$ називається індуктивним, якщо порожній клас є його елементом, і для кожного елемента $n\in I$ множина $n\cup \{n\}$ є елементом $I$. З теореми Геделя про існування класів випливає, що клас $I$ усіх індуктивних множин існує, а аксіома нескінченності постулює, що цей клас є непорожнім. Перетин $\cap {\mathcal {I}}$ усіх індуктивних множин позначають через $\omega$ і називають множиною натуральних чисел. Елементи множини $\omega$ називають натуральними числами, або скінченними ординалами.

Систему аксіом NBG часто доповнюють однією з аксіом вибору:

Аксіома глобального вибору

Існує функція $\mathbf {F}$, що ставить у відповідність кожній непорожній множині $x$ деякий елемент $\mathbf {F} (x)\in x$.

З аксіоми глобального вибору випливає звичайна аксіома вибору, яка є однією з аксіом ZFC.

Аксіома вибору

Для кожної множини $a$ існує функція $f$, що ставить у відповідність кожній непорожній множині $x\in a$ деякий елемент $f(x)\in x$.

З іншого боку, аксіома глобального вибору випливає з аксіоми конструктивності $\mathbf {V} =\mathbf {L}$, для формулювання якої необхідно означити клас $\mathbf {L}$ конструктивних множин. У свою чергу, клас $\mathbf {L}$ означується за допомогою класу ординалів $\mathbf {On}$.

Означення. Клас X називають

• транзитивним, якщо $\cup X\subseteq X$;
• лінійно $\in$-впорядкованим, якщо для довільних множин $x,y\in X$ справедлива трихотомія $(x\in y)\;\vee \;(x=y)\;\vee \;(y\in x)$;
• ординальним, якщо $X$ є транзитивним і лінійно $\in$-впорядкованим;
• ординалом, якщо $X$ є ординальною множиною.

Із теореми Геделя про існування класів випливає, що клас $\mathbf {On}$ ординалів існує. Клас ординалів $\mathbf {On}$ можна охарактеризувати як єдиний ординальний властивий клас.

Означення. Клас $\mathbf {X}$ називається внутрішньою моделлю, якщо $\mathbf {X}$ транзитивний, містить усі ординали, і для довільних множин $x,y\in \mathbf {X}$ множини $\{x,y\},\;x\times y,\;x\setminus y,\;\mathbf {E} \cap (x\times y),\;x^{-1},\;{\mathsf {dom}}[x],\;\cup x,\;x^{\circlearrowright }$ є елементами класу $\mathbf {X}$.

Найменша внутрішня модель називається класом конструктивних множин і позначається через $\mathbf {L}$. Клас $\mathbf {L}$ рівний об'єднанню $\bigcup _{\alpha \in \mathbf {On} }L_{\alpha }$ множин $L_{\alpha }$, що означаються рекурсивною формулою $L_{\alpha }=\bigcup _{\beta <\alpha }L_{\beta }\cup \{\alpha \}\cup \{\{x,y\},\;x\times y,\;x\setminus y,\;\mathbf {E} \cap (x\times y),\;x^{-1},\;{\mathsf {dom}}[x],\;\cup x,\;x^{\circlearrowright }:x\in L_{\beta }\}$ для $\alpha \in \mathbf {On}$. Існування класу конструктивних множин забезпечує теорема рекурсії, про яку мова нижче.

Аксіома конструктивності

$\mathbf {V} =\mathbf {L}$.

Аксіома конструктивності є дуже сильною аксіомою, з якої випливає аксіома глобального вибору, а також

Узагальнена Гіпотеза Континуума: Для кожної нескінченної множини $x$ та підмножини $y\subseteq 2^{x}$ існує ін'єктивна функція $f$ така, що $f[y]\subseteq x$ або $f[2^{x}]\subseteq y$.

Згідно з теоремою Серпінського (1947), із узагальненої гіпотези континуума випливає аксіома вибору.

---

Таким чином, аксіоматика NBG включає 14 аксіом, яких вистачає для розбудови усієї теорії множин та класів:

1. Аксіома рівності: Рівні класи неможливо розрізнити відношенням належності.
2. Аксіома пари: Для довільних множин $x,y$ існує невпорядкована пара $\{x,y\}$.
3. Аксіома належності: Клас $\mathbf {E} =\{(x,y):x\in y\}$ існує.
4. Аксіома інверсії: Для довільного класу $X$, клас $X^{-1}=\{\langle y,x\rangle :\langle x,y\rangle \in X\}$ існує.
5. Аксіома проєкції: Для довільного класу $X$, клас ${\mathsf {dom}}[X]=\{x:\exists y\;\langle x,y\rangle \in X\}$ існує.
6. Аксіома добутку: Для довільних класів $X,Y$, клас $X\times Y=\{\langle x,y\rangle :x\in X,\;y\in Y\}$ існує.
7. Аксіома різниці: Для довільних класів $X,Y$, клас $X\setminus Y$ існує.
8. Аксіома циклу: Для довільного класу $X$ клас $X^{\circlearrowright }=\{\langle z,x,y\rangle :\langle x,y,z\rangle \in X\}$ існує.
9. Аксіома регулярності: Довільна непорожня множина $x$ містить такий елемент $y\in x$, що $y\cap x=\emptyset$.
10. Аксіома заміни: Для довільної функції $F$ і довільної множини $x$, клас $F[x]=\{F(y):y\in x\}$ є множиною.
11. Аксіома суми: Для довільної множини $x$, клас $\cup x=\{z:\exists y\;(z\in y\;\wedge \;y\in x)\}$ є множиною.
12. Аксіома експоненти: Для довільної множини $x$, її експонента $2^{x}=\{y:y\subseteq x\}$ є множиною.
13. Аксіома нескінченності: Існує множина натуральних чисел $\omega$.
14. Аксіома глобального вибору: Існує функція $\mathbf {F}$, що ставить у відповідність кожній непорожній множині $x$ деякий елемент $\mathbf {F} (x)\in x$.

Зв'язок аксіоматики NBG з аксіоматикою ZFC

Теорія множин Цермело — Френкеля ZFC є частиною теорії NBG і описує властивості множин, уникаючи вживання класів. Для цього низку аксіом NBG доводиться заміняти нескінченними схемами аксіом (а саме виділення та підстановки). Для порівняння з аксіомами NB наведемо список аксіом ZFC.

1. Аксіома рівності: $\forall x\;\forall y\;(x=y\;\Leftrightarrow \;\forall z\;(z\in x\;\Leftrightarrow \;z\in y))$.
2. Аксіома пари: $\forall x\;\forall y\;\exists z\;\forall u\;(u\in z\;\Leftrightarrow \;(u=x\;\vee \;u=y))$.
3. Аксіома суми: $\forall x\;\exists u\;\forall z\;(z\in u\;\Leftrightarrow \;\exists y\;(z\in y\;\wedge \;y\in x))$.
4. Аксіома експоненти: $\forall x\;\exists y\;\forall z\;(z\in y\;\Leftrightarrow \;z\subseteq x)$.
5. Аксіома регулярності: $\forall x\;(\exists y\;(y\in x))\;\Rightarrow \;\exists y\;(y\in x\;\wedge \;\forall z\;(z\in y\;\Rightarrow \;z\notin x))$.
6. Аксіома нескінченності: $\exists x\;(\emptyset \in x\;\wedge \;\forall n\;(n\in x\;\Rightarrow \;n\cup \{n\}\in x))$.
7. Аксіомна схема виділення: Нехай $\phi (x,a,c_{1},\dots ,c_{n})$ — формула в мові ZFC, усі вільні змінні якої містяться серед змінних $x,a,c_{1},\dots ,c_{n}$, а змінна $b$ не вільна для формули $\phi$. Тоді $\forall a\;\forall c_{1}\;\dots \forall c_{n}\;\exists b\;\forall x\;(x\in b\;\Leftrightarrow \;(x\in a\;\wedge \;\phi (x,a,c_{1},\dots ,c_{n})))$.
8. Аксіомна схема підстановки: Нехай $\phi (x,y,a,c_{1},\dots ,c_{n})$ — формула в мові ZFC, усі вільні змінні якої містяться серед змінних $x,y,a,c_{1},\dots ,c_{n}$, а змінна $b$ не є вільною для формули $\phi$. Тоді $\forall a\;\forall c_{1}\dots \forall c_{n}\;(\forall x\;(x\in a\;\Rightarrow \;\exists !y\;\phi (x,y,a,c_{1},\dots ,c_{n})))\;\Rightarrow \;\exists b\;\forall y\;(y\in b\;\Leftrightarrow \;\exists x\;(x\in a\;\wedge \;\phi (x,y,a,c_{1},\dots ,c_{n})))$.
9. Аксіома вибору: Для кожної множини $a$ існує функція $f$, що ставить у відповідність кожній непорожній множині $x\in a$ деякий елемент $f(x)\in x$.

Теорії ZFC та NBG допускають моделі одна в іншій. Моделями ZFC в NBG є клас $\mathbf {V}$ усіх множин чи клас $\mathbf {L}$ конструктивних множин. Моделлю NBG в ZFC є сім'я усіх класів, що виражаються формулами з параметрами у мові ZFC. Тому все що можна довести про множини у теорії ZFC доводиться також у теорії NBG і навпаки. Це означає, що теорія NBG є консервативним розширенням теорії ZFC.

Теорема рекурсії

Кантор визначав ординали як класи еквівалентності цілком впорядкованих множин. Усі ці класи еквівалентності (за винятком одного) є властивими класами. За такого підходу до ординалів неможливо говорити про множини чи класи ординалів. Щоб обійти цю проблему, фон Нойман запропонував означення ординала як транзитивної $\in$-лінійно впорядкованої множини і довів, що кожна цілком впорядкована множина є ізоморфною деякому ординалові. Цей важливий факт доводиться за теоремою рекурсії. Для формулювання цієї теореми нам необхідно спершу означити деякі стандартні поняття теорії порядку.

Нагадаємо, що відношенням називається клас, елементами якого є впорядковані пари.

Означення. Відношення L називають

• рефлексивним, якщо $\{\langle x,x\rangle :x\in {\mathsf {dom}}[L\cup L^{-1}]\}\subseteq L$;
• антисиметричним, якщо $L\cap L^{-1}\subseteq \{\langle x,x\rangle :x\in {\mathsf {dom}}[L\cup L^{-1}]\}$;
• транзитивним, якщо $\{\langle x,z\rangle :\exists y\;(\langle x,y\rangle \in L\;\wedge \;\langle y,z\rangle \in L)\}\subseteq L$;
• частковим порядком, якщо $L$ є рефлексивним, транзитивним, антисиметричним відношенням;
• лінійним порядком, якщо $L$ є частковим порядком з $L\cup L^{-1}={\mathsf {dom}}[L]\times {\mathsf {rng}}[L]$;
• ґрунтовним (англ., well-founded), якщо для кожної множини $x$ клас ${\downarrow }x=\{y:\langle y,x\rangle \in L\}\setminus \{x\}$ є множиною і кожна непорожня підмножина $a\subseteq {\mathsf {dom}}[L\cup L^{-1}]$ містить такий елемент $x\in a$, що $a\cap {\downarrow }x=\emptyset$. Такий елемент $x$ називають $L$-мінімальним елементом множини $a$.
• цілковитим порядком, якщо відношення є ґрунтовним лінійним порядком.

Зауважимо, що аксіома регулярності є еквівалентною ґрунтовності відношення належності $\mathbf {E}$.

Теорема Рекурсії. Якщо $L$ — ґрунтовний частковий порядок, тоді для довільної функції $G:{\mathsf {dom}}[L]\times \mathbf {V} \to \mathbf {V}$, існує єдина функція $F:{\mathsf {dom}}[L]\to \mathbf {V}$ така, що  $F(x)=G(\langle x,F[{\downarrow }x]\rangle )$ для кожного $x\in {\mathsf {dom}}[L].$

Для доведення теореми рекурсії розглядають клас ${\mathsf {F}}$, елементами якого є функції $f$, для яких існує такий елемент $x\in L$, що ${\mathsf {dom}}[f]={\downarrow }x$ і $f(y)=G(\langle x,f[{\downarrow }y]\rangle )$ для кожного $y\in {\downarrow }x$. Тоді об'єднання $\cup {\mathsf {F}}$ є шуканою функцією $F$. $\quad \square$

Означення. Відношення $X,Y$ називають ізоморфними, якщо існує ін'єктивна функція $F$, яка має такі властивості:

• $\forall \langle x,x'\rangle \in X\;\exists \langle y,y'\rangle \in Y\;(\langle x,y\rangle \in F\;\wedge \;\langle x',y'\rangle \in F)$;
• $\forall \langle y,y'\rangle \in Y\;\exists \langle x,x'\rangle \in X\;(\langle x,y\rangle \in F\;\wedge \;\langle x',y'\rangle \in F)$.

Із теореми рекурсії випливає такий фундаментальний факт.

Теорема про ізоморфізм. Кожен цілковитий порядок $L$ є ізоморфним єдиному ординальному класу. Цей ординальний клас є ординалом, якщо $L$ — множина, і рівним класу $\mathbf {On}$, якщо $L$ є властивим класом.

Щоб довести теорему про ізоморфізм, достатньо застосувати теорему рекурсії до функції $\mathbf {G} :{\mathsf {dom}}[L]\times \mathbf {V} \to \mathbf {V} ,\;\mathbf {G} :\langle x,y\rangle \mapsto \min(\mathbf {On} \setminus y).$

Історія створення аксіоматики NBG

Аксіоматика фон Ноймана — Бернайса — Геделя є результатом тривалої еволюції. У роботах 1925, 1928 та 1929 років Джон фон Нойман опублікував свою аксіоматичну систему, у якій первинними поняттями були функція та аргумент. Поль Бернайс у працях 1931, 1937, 1941 років дошліфував теорію фон Ноймана до належного блиску; він означив функції як класи бінарних відношень та вибрав первинними поняттями теорії поняття класу та множини, причому Бернайс використовував різні символи $x\in y$ і $x\,\eta \,Y$ для позначення множини $x$ до іншої множини $y$ чи до класу $Y$. Також він вважав, що множина $x$ зображає клас $Y$, якщо $\forall x\;(x\in y\;\Leftrightarrow \;x\,\eta \,Y)$. Аксіоматика Бернайса (яку він виклав у своєму листі Геделю у 1931) складалася з 20 аксіом, які включали 9 аксіом існування класів, зокрема аксіоми інверсії на асоціативності. Аксіома асоціативності Бернайса стверджує, що для кожного класу $X$ клас $\{\langle \langle x,y\rangle ,z\rangle :\langle x,\langle y,z\rangle \rangle \in X\}$ існує. Курт Гедель, після знайомства з теорією Бернайса, запропонував спростити понятійну систему теорії: звести поняття множини до поняття класу і використовувати єдине відношення належності для класів та множин. Він також замінив аксіоми інверсії та асоціативності Бернайса на аксіоми транспозиції та циклічної перестановки, які постулюють існування класів $\{\langle x,z,y\rangle :\langle x,y,z\rangle \in X\}$ та $\{\langle y,z,x\rangle :\langle x,y,z\rangle \in X\}$ для кожного класу $X$. Гедель використав таким чином модифіковану версію аксіоматики Бернайса у своєму знаменитому доведенні несуперечливості аксіоми вибору та гіпотези континуума, довівши, що вони є чинними в конструктивному універсумі $\mathbf {L}$. Більше того, він зауважив, що в конструктивному універсумі справджується аксіома глобального вибору, що дало змогу долучити її до списку аксіом NBG без небезпеки отримати суперечність. Абревіатуру NBG у математичний вжиток увів великий адепт цієї теорії Еліотт Мендельсон, про що він пише у своїй класичній книзі з Математичної Логіки, де також згадує, що Paul Halmos, який віддавав перевагу аксіоматиці ZFC, жартома розшифровував NBG як сленгове «No Bloody Good». Про роль фон Ноймана, Бернайса та Геделя у створенні аксіоматики NBG можна почитати у статті (Kanamori, 2009).

Застосування теорії множин та класів NBG у теорії категорій

Аксіоматика NBG має дві суттєві переваги порівняно з іншими аксіоматичними системами теорії множин. По-перше, вона є скінченно аксіоматизовною, а по-друге, дозволяє оперувати з класами. Останнє є критично важливим для теоретико-множинного обґрунтування теорії категорій.

У теорії NBG такі важливі поняття як категорія, функтор, природне перетворення означуються цілком строго і стають типовими алгебраїчними структурами (в розумінні Бурбакі). В означенні категорії використовуються впорядковані п'ятірки класів, які слід розуміти як підкласи класу $\mathbf {V} \times 5$ (це цілком законний об'єкт у теорії NBG).

Означення категорії. Категорією називаємо п'ятірку $(Mor,Ob,{\mathsf {d}},{\mathsf {r}},\circ )$, де:
$Mor$ — клас, елементи якого називаються морфізмами категорії;
$Ob$ — підклас класу $Mor$, елементи якого називаються об'єктами категорії
 (таким чином ми ототожнюємо об'єкти з тотожніми морфізмами цих об'єктів);
${\mathsf {d}},{\mathsf {r}}$ — два класи, які є функціями з Mor в Ob; значення ${\mathsf {d}}(f)$ і ${\mathsf {r}}(f)$ на морфізмі $f\in Mor$ називають початком і кінцем морфізму $f$;
 для довільних об'єктів $a,b\in Ob$ підклас $Mor(a,b)=\{f\in Mor:{\mathsf {d}}(f)=a,\;{\mathsf {r}}(f)=b\}$ називається класом морфізмів з $a$ в $b$;
$\circ$ — функція з областю визначення ${\mathsf {dom}}[\circ ]={\big \{}\langle f,g\rangle \in Mor\times Mor:{\mathsf {d}}(f)={\mathsf {r}}(g)\}$ і областю значень $Mor$, яка ставить у відповідність кожній парі морфізмів $\langle f,g\rangle \in {\mathsf {dom}}[\circ ]$ морфізм $f\circ g$, що  має ${\mathsf {d}}(f\circ g)={\mathsf {d}}(g)$ і ${\mathsf {r}}(f\circ g)={\mathsf {r}}(f)$; морфізм $f\circ g$ називається композицією морфізмів $f,g$. 
При цьому повинні задовольнятися такі аксіоми:
(Об'єктність): ${\mathsf {r}}(a)=a={\mathsf {d}}(a)$ для довільного об'єкта $a\in Ob\subseteq Mor$;
(Нейтральність): ${\mathsf {r}}(f)\circ f=f=f\circ {\mathsf {d}}(f)$ для довільного морфізма $f\in Mor$;
(Асоціативність): Для довільних морфізмів $f,g,h\in Mor$ з ${\mathsf {r}}(f)={\mathsf {d}}(g)$ i ${\mathsf {r}}(g)={\mathsf {d}}(h)$ справджується рівність $f\circ (g\circ h)=(f\circ g)\circ h$;

Категорія $(Mor,Ob,{\mathsf {d}},{\mathsf {r}},\circ )$ називається 
$\bullet$ локально малою категорією, якщо для довільних об'єктів $a,b\in Ob$, клас морфізмів $Mor(a,b)=\{f\in Mor:{\mathsf {d}}(f)=a,\;{\mathsf {r}}(f)=b\}$є множиною;
$\bullet$ малою категорією, якщо її клас морфізмів $Mor$ є множиною.

Поняття функтора між категоріями теж можна означити цілком строго.

Означення функтора. Функтором $F:{\mathcal {A}}\to {\mathcal {A}}'$ між категоріями ${\mathcal {A}}=(Mor,Ob,{\mathsf {d}},{\mathsf {r}},\circ )$ та ${\mathcal {A}}'=(Mor',Ob',{\mathsf {d}}',{\mathsf {r}}',\circ ')$ називаємо функцію $F:Mor\to Mor'$, яка зберігає структуру категорії у тому сенсі, що :
$\bullet$ ${\mathsf {d}}'(F(f))=F({\mathsf {d}}(f))$ і ${\mathsf {r}}'(F(f))=F({\mathsf {r}}(f))$ для довільного морфізма $f\in Mor$;
$\bullet$ $F(f\circ g)=F(f)\circ 'F(g)$ для довільних морфізмів $f,g\in Mor$ з ${\mathsf {d}}(f)={\mathsf {r}}(g)$.

Нарешті, подамо строге

Означення природного перетворення. Нехай $F,G:{\mathcal {A}}\to {\mathcal {A}}'$ — два функтори між категоріями  ${\mathcal {A}}=(Mor,Ob,{\mathsf {d}},{\mathsf {r}},\circ )$ та ${\mathcal {A}}'=(Mor',Ob',{\mathsf {d}}',{\mathsf {r}}',\circ ')$. Природним перетворенням функтора $F$ у функтор $G$ називаємо довільну функцію $\eta :Ob\to Mor'$, що ставить у відповідність кожному об'єкту $a\in Ob$ морфізм $\eta (a)\in Mor'(F(a),G(a))$ категорії ${\mathcal {A}}'$ таким чином, що задовольняється 
(Умова природності): Для довільного морфізму  $f\in Mor$ категорії ${\mathcal {A}}$ справедлива рівність $G(f)\circ '\eta ({\mathsf {d}}(a))=\eta ({\mathsf {r}}(b))\circ 'F(f)$.

Застосування теорії NBG до сюрреальних чисел

Теорія множин та класів NBG є природною мовою при дослідженні сюрреальних чисел Конвея — цікавого об'єкта на стику теорії ігор, логіки, алгебри та (нестандартного) аналізу.

Сюрреальні числа утворюють властивий клас $\mathbf {R}$, який називається сюрреальною прямою і є максимальним нестандартним розширенням класичної дійсної прямої $\mathbb {R}$. Для повноти подамо строге означення сюрреальної прямої. Це означення використовує поняття перерізу лінійного порядку.

Перерізом лінійного порядку $L$ називається впорядкована пара множин $\langle a,b\rangle$, яка задовольняє умови:

• $a\cap b=\emptyset$ i $a\cup b={\mathsf {dom}}[L]={\mathsf {ran}}[L]$;
• $\forall x\in a\;\forall y\in b\;(\langle x,y\rangle \in L)$.

Через ${\mathsf {cut}}(L)$ позначаємо множину усіх перерізів лінійного порядку $L$ (зауважимо, що лінійний порядок є множиною, якщо він має хоча б один переріз).

Сюрреальна пряма $\mathbf {R}$ є областю визначення лінійного порядку $\mathbf {R} _{\leq }=\bigcup _{\alpha \in \mathbf {On} }R_{\alpha }$, що є об'єднанням лінійних порядків $R_{\alpha }$, які задаються рекурсивною формулою: $R_{\alpha }=\bigcup _{\beta \in \alpha }R_{\beta }\cup \{\langle \langle a,b\rangle ,\langle a',b'\rangle \rangle \in {\mathsf {cut}}(R_{\beta })\times {\mathsf {cut}}(R_{\beta }):a\subseteq a'\}\cup \{\langle x,\langle a,b\rangle \rangle \in R_{\beta }\times {\mathsf {cut}}(R_{\beta }):x\in a\}\cup \{\langle \langle a,b\rangle ,y\rangle \in {\mathsf {cut}}(R_{\beta })\times R_{\beta }:y\in b\}.$

Існування класу $\mathbf {R} _{\leq }$забезпечує теорема рекурсії. Нескладно переконатися, що сюрреальна пряма містить усі ординали.

Конвей та Кнут довели, що звичайні операції додавання і множення натуральних чисел продовжуються до операцій додавання і множення сюрреальних чисел. Ці операції перетворюють сюрреальну пряму, наділену лінійним порядком $\mathbf {R} _{\leq }$, на впорядковане поле, що містить ізоморфні копії всіх інших впорядкованих полів. Використовуючи ці алгебраїчні операції над сюрреальними числами, можна цілком законно застосовувати їх до ординалів і говорити, наприклад, про частки чи квадратні корені з ординалів. Ці дивовижні властивості сюрреальної прямої свідчать про її фундаментальну роль у теорії NBG.

Див. також

• Універсум фон Неймана

Джерела

• Banakh, Taras (2020), Classical Set Theory: Theory of Sets and Classes
• 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), Dover Publications, ISBN 978-0-486-66637-2
• Conway, John (1976). On numbers and games. London, New York, San Francisco: Academic Press. с. 238.
• Gödel, Kurt (1940), The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory (вид. Revised), Princeton University Press, ISBN 978-0-691-07927-1
• Kanamori, Akihiro (2009). Bernays and set theory. Bull. Symbolic Logic 15 (1): 43–69.
• Knuth, Donald (1974). Surreal numbers. Massachusetts: Addison-Wesley, Reading. с. 19.
• Gödel, Kurt (2008), The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory, with a foreword by Laver, Richard (вид. Paperback), Ishi Press, ISBN 978-0-923891-53-4
• 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
• Mendelson, Elliott (1997). An Introduction to Mathematical Logic (вид. 4th). London: Chapman & Hall. ISBN 0-412-80830-7.
• 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
• von Neumann, John (1929), Über eine Widerspruchsfreiheitsfrage in der axiomatischen Mengenlehre, Journal für die Reine und Angewandte Mathematik, 160: 227—241
• Sierpiński W., L'hypothèse généralisée du continu et l'axiome du choix [Архівовано 8 вересня 2020 у Wayback Machine.], Fund. Math. 34 (1947) 1-5.
• Kanamori, Akihiro (2009). Bernays and Set Theory. Bulletin of Symbolic Logic. 15: 43—69. doi:10.2178/bsl/1231081769.