Теорія множин та класів фон Ноймана Бернайса Геделя скорочено NBG аксіоматична теорія першого порядку що є консервативни

Теорія множин та класів фон Ноймана — Бернайса — Геделя (скорочено 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, або в монографії ^[en].

Наступні 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 аксіом, яких вистачає для розбудови усієї теорії множин та класів:

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

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

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

Аксіома рівності: $\forall x\;\forall y\;(x=y\;\Leftrightarrow \;\forall z\;(z\in x\;\Leftrightarrow \;z\in y))$ .
Аксіома пари: $\forall x\;\forall y\;\exists z\;\forall u\;(u\in z\;\Leftrightarrow \;(u=x\;\vee \;u=y))$ .
Аксіома суми: $\forall x\;\exists u\;\forall z\;(z\in u\;\Leftrightarrow \;\exists y\;(z\in y\;\wedge \;y\in x))$ .
Аксіома експоненти: $\forall x\;\exists y\;\forall z\;(z\in y\;\Leftrightarrow \;z\subseteq x)$ .
Аксіома регулярності: $\forall x\;(\exists y\;(y\in x))\;\Rightarrow \;\exists y\;(y\in x\;\wedge \;\forall z\;(z\in y\;\Rightarrow \;z\notin x))$ .
Аксіома нескінченності: $\exists x\;(\emptyset \in x\;\wedge \;\forall n\;(n\in x\;\Rightarrow \;n\cup \{n\}\in x))$ .
Аксіомна схема виділення: Нехай $\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})))$ .
Аксіомна схема підстановки: Нехай $\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})))$ .
Аксіома вибору: Для кожної множини $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 років Джон фон Нойман опублікував свою аксіоматичну систему, у якій первинними поняттями були функція та аргумент. ^[en] у працях 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 у математичний вжиток увів великий адепт цієї теорії ^[en], про що він пише у своїй класичній книзі з Математичної Логіки, де також згадує, що 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$