Теорія множин та класів фон Ноймана — Бернайса — Геделя (скорочено NBG) — аксіоматична теорія першого порядку, що є (консервативним) розширенням теорії множин ZF Цермело — Френкеля. На відміну від ZF, NBG є скінченно аксіоматизовною теорією, яка дозволяє вільно оперувати як множинами, так і класами. Окрім стандартних логічних зв'язок, кванторів та символу рівності, мова теорії NBG включає символ бінарного відношення , що інтерпретується як належність.
Первинними (тобто неозначуваними) поняттями теорії NBG є поняття класу та елемента. Клас може бути елементом іншого класу , це позначається як . Позначення є скороченим записом формули .
Два класи називають рівними, якщо вони складаються з однакових елементів, тобто , якщо .
Клас називається множиною, якщо він є елементом деякого класу, тобто якщо . Клас, який не є множиною, називають властивим класом (). Щоб розрізняти класи та множини, для позначення класів вживають великі літери, а для множин — малі. Властиві класи позначають великими товстими літерами. Прикладом такого класу є клас усіх множин.
Розрізнення класів та множин дозволяє уникнути відомого парадоксу Рассела, який у випадку NBG стає доведенням того, що клас не є множиною.
Система NBG містить 13 аксіом і може доповнюватися аксіомою (глобального) вибору або аксіомою конструктивності.
Аксіоми NBG
Аксіома рівності
З аксіоми рівності випливає, що рівні класи неможливо розрізними відношенням належності.
Клас називається підкласом класу , якщо кожен елемент класу є елементом класу . У цьому випадку пишемо .
Тобто, . .
Підклас класу називаємо підмножиною класу , якщо є множиною.
Аксіома пари
Аксіома пари постулює, що для довільних множин існує множина , єдиними елементами якої є множини . Така множина називається невпорядкованою парою множин і позначається символом . З аксіоми рівності випливає рівність . Невпорядкована пара позначається символом і називається синґлетоном.
Впорядкованою парою множин називається множина .
З аксіоми рівності випливає
Теорема. .
Ця теорема стверджує, що впорядковані пари і рівні тоді і лише тоді, коли і .
Впорядкованою трійкою множин називається множина .
Впорядковані -ки множин означуються рекурсивною формулою: для .
Наступні 5 аксіом називають аксіомами існування класів.
Аксіома належності
Аксіома належності постулює існування класу .
Аксіома Інверсії
Аксіома інверсії стверджує, що для кожного класу існує клас .
Клас називається відношенням, якщо .
Клас є відношенням тоді і лише тоді, коли його елементами є впорядковані пари, тобто .
Аксіома проєкції
Згідно з аксіомами проєкції та інверсії, для кожного класу існують класи та . Якщо клас є відношенням (наприклад, функцією), то класи та називають областю визначення та областю значень відношення .
З аксіом належності та проєкції випливає, що клас усіх множин існує, оскільки він збігається з областю визначення відношення належності .
Аксіома різниці
Аксіома різниці стверджує, що для довільних класів , існує клас .
З аксіоми різниці випливає існування порожнього класу , що не містить жодних елементів. За означенням рівності, порожній клас єдиний.
Аксіома різниці також дозволяє нам визначити перетин класів як клас . За означенная рівності, .
Об'єднанням двох класів називають клас , який рівний класу , що існує за аксіомою різниці.
Аксіома добутку
Аксіома добутку постулює, що для довільних класів існує їх декартів добуток .
Для відношення та класу клас називають образом класу при відношенні . Клас існує, оскільки він рівний класу . Клас називають прообразом класу при відношенні .
Відношення називається функцією (або відображенням), якщо для довільних пар із рівності випливає рівність . Із цього означення випливає, що для довільної функції та елемента існує єдиний елемент такий, що . Цей єдиний елемент позначається через . При цьому круглі дужки використовуються, що відрізнити елемент від класу . Для функції запис означає, що і . У цьому випадку функція ставить у відповідність кожному елементу певний елемент класу .
Функція називається ін'єктивною, якщо відношення теж є функцією.
Хоча властиві класи не можуть бути елементами інших класів, ми можемо говорити про індексовані класи класів. А саме, для довільного класу кожен підклас можна ототожнювати з індексованою сім'єю класів , де для . У цьому випадку парадокс Рассела доводить, що для класу не існує елемента з .
Аксіома циклу
Аксіома циклу постулює, що для довільного класу існує клас , який далі позначатиметься через або .
Для довільного класу клас називають об'єднанням класу .
Клас існує, оскільки він рівний класу .
Для довільного класу клас називають перетином .
Клас існує, оскільки він рівний класу .
Із означень випливає, що і
Для довільного класу клас називають експонентою класу .
Клас існує, оскільки він рівний класу . Зокрема, .
Аксіома регулярності .
Аксіома регулярності стверджує, що довільна непорожня множина містить елемент , який не має з множиною спільних елементів. Аксіома регулярності забороняє існування нескінченних спадних ланцюгів виду . Аксіома регулярності часто використовується в індуктивних конструкціях.
Використовуючи аксіому регулярності та аксіоми існування класів, Гедель довів (індукцією по складності формули ) наступну важливу теорему, обмежена форма якої приймається за аксіому вирізання в аксіоматиці Цермело — Френкеля.
Теорема Геделя про існування класів: Нехай є формулою, у якій квантори пробігають лише по множинах, а вільні змінні містяться серед змінних . Тоді для довільних класів клас існує.
Доступне доведення цієї теореми можна знайти в англійській версії статті про аксіоматику NBG, або в монографії .
Наступні 4 аксіоми називають аксіомами існування множин.
Аксіома заміни Для довільної функції та множини , образ є множиною.
Аксіома об'єднання Для довільної множини її об'єднання є множиною.
Аксіома експоненти Для довільної множини її експонента є множиною.
З аксіоми заміни (застосованої до тотожнього відображення класу в себе) випливає, що перетин множини та класу є множиною; тому для довільної множини усі її підкласи є множинами.
Проте з усіх наведених вище аксіом ще не випливає, що хоча б одна множина існує. Існування множин (навіть нескінченних) забезпечує
Аксіома нескінченності
Аксіома нескінченності постулює існування індуктивної множини. Клас називається індуктивним, якщо порожній клас є його елементом, і для кожного елемента множина є елементом . З теореми Геделя про існування класів випливає, що клас усіх індуктивних множин існує, а аксіома нескінченності постулює, що цей клас є непорожнім. Перетин усіх індуктивних множин позначають через і називають множиною натуральних чисел. Елементи множини називають натуральними числами, або скінченними ординалами.
Систему аксіом NBG часто доповнюють однією з аксіом вибору:
Аксіома глобального вибору Існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .
З аксіоми глобального вибору випливає звичайна аксіома вибору, яка є однією з аксіом ZFC.
Аксіома вибору Для кожної множини існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .
З іншого боку, аксіома глобального вибору випливає з аксіоми конструктивності , для формулювання якої необхідно означити клас конструктивних множин. У свою чергу, клас означується за допомогою класу ординалів .
Означення. Клас X називають
транзитивним, якщо ; лінійно -впорядкованим, якщо для довільних множин справедлива трихотомія ; ординальним, якщо є транзитивним і лінійно -впорядкованим; ординалом, якщо є ординальною множиною.
Із теореми Геделя про існування класів випливає, що клас ординалів існує. Клас ординалів можна охарактеризувати як єдиний ординальний властивий клас.
Означення. Клас називається внутрішньою моделлю, якщо транзитивний, містить усі ординали, і для довільних множин множини є елементами класу .
Найменша внутрішня модель називається класом конструктивних множин і позначається через . Клас рівний об'єднанню множин , що означаються рекурсивною формулою для . Існування класу конструктивних множин забезпечує теорема рекурсії, про яку мова нижче.
Аксіома конструктивності .
Аксіома конструктивності є дуже сильною аксіомою, з якої випливає аксіома глобального вибору, а також
Узагальнена Гіпотеза Континуума: Для кожної нескінченної множини та підмножини існує ін'єктивна функція така, що або .
Згідно з теоремою Серпінського (1947), із узагальненої гіпотези континуума випливає аксіома вибору.
Таким чином, аксіоматика NBG включає 14 аксіом, яких вистачає для розбудови усієї теорії множин та класів:
Аксіома рівності: Рівні класи неможливо розрізнити відношенням належності. Аксіома пари: Для довільних множин існує невпорядкована пара . Аксіома належності: Клас існує. Аксіома інверсії: Для довільного класу , клас існує. Аксіома проєкції: Для довільного класу , клас існує. Аксіома добутку: Для довільних класів , клас існує. Аксіома різниці: Для довільних класів , клас існує. Аксіома циклу: Для довільного класу клас існує. Аксіома регулярності: Довільна непорожня множина містить такий елемент , що . Аксіома заміни: Для довільної функції і довільної множини , клас є множиною. Аксіома суми: Для довільної множини , клас є множиною. Аксіома експоненти: Для довільної множини , її експонента є множиною. Аксіома нескінченності: Існує множина натуральних чисел . Аксіома глобального вибору: Існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .
Зв'язок аксіоматики NBG з аксіоматикою ZFC Теорія множин Цермело — Френкеля ZFC є частиною теорії NBG і описує властивості множин, уникаючи вживання класів. Для цього низку аксіом NBG доводиться заміняти нескінченними схемами аксіом (а саме виділення та підстановки). Для порівняння з аксіомами NB наведемо список аксіом ZFC.
Аксіома рівності: . Аксіома пари: . Аксіома суми: . Аксіома експоненти: . Аксіома регулярності: . Аксіома нескінченності: . Аксіомна схема виділення: Нехай — формула в мові ZFC, усі вільні змінні якої містяться серед змінних , а змінна не вільна для формули . Тоді . Аксіомна схема підстановки: Нехай — формула в мові ZFC, усі вільні змінні якої містяться серед змінних , а змінна не є вільною для формули . Тоді . Аксіома вибору: Для кожної множини існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .
Теорії ZFC та NBG допускають моделі одна в іншій. Моделями ZFC в NBG є клас усіх множин чи клас конструктивних множин. Моделлю NBG в ZFC є сім'я усіх класів, що виражаються формулами з параметрами у мові ZFC. Тому все що можна довести про множини у теорії ZFC доводиться також у теорії NBG і навпаки. Це означає, що теорія NBG є консервативним розширенням теорії ZFC.
Теорема рекурсії Кантор визначав ординали як класи еквівалентності цілком впорядкованих множин. Усі ці класи еквівалентності (за винятком одного) є властивими класами. За такого підходу до ординалів неможливо говорити про множини чи класи ординалів. Щоб обійти цю проблему, фон Нойман запропонував означення ординала як транзитивної -лінійно впорядкованої множини і довів, що кожна цілком впорядкована множина є ізоморфною деякому ординалові. Цей важливий факт доводиться за теоремою рекурсії. Для формулювання цієї теореми нам необхідно спершу означити деякі стандартні поняття теорії порядку.
Нагадаємо, що відношенням називається клас, елементами якого є впорядковані пари.
Означення. Відношення L називають
рефлексивним, якщо ; антисиметричним, якщо ; транзитивним, якщо ; частковим порядком, якщо є рефлексивним, транзитивним, антисиметричним відношенням; лінійним порядком, якщо є частковим порядком з ; ґрунтовним (англ., well-founded), якщо для кожної множини клас є множиною і кожна непорожня підмножина містить такий елемент , що . Такий елемент називають -мінімальним елементом множини . цілковитим порядком, якщо відношення є ґрунтовним лінійним порядком.
Зауважимо, що аксіома регулярності є еквівалентною ґрунтовності відношення належності .