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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Клас називається множиною, якщо він є елементом деякого класу, тобто якщо . Клас, який не є множиною, називають властивим класом (англ. proper class). Щоб розрізняти класи та множини, для позначення класів вживають великі літери, а для множин — малі. Властиві класи позначають великими товстими літерами. Прикладом такого класу є клас усіх множин.

Розрізнення класів та множин дозволяє уникнути відомого парадоксу Рассела, який у випадку NBG стає доведенням того, що клас не є множиною.

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

Аксіоми NBG[ред. | ред. код]

Аксіома Рівності: 

Аксіома рівності постулює, що два класи є рівними тоді і лише тоді, коли вони мають одні і ті ж елементи.

Клас називається підкласом класу , якщо кожен елемент класу є елементом класу . У цьому випадку пишемо . Тобто, . Аксіома рівності стверджує, що ).

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

Аксіома Пари: 

Аксіома пари постулює, що для довільних множин існує множина , єдиними елементами якої є множини . Така множина називається невпорядкованою парою[en] множин і позначається символом . З аксіоми рівності випливає рівність . Невпорядкована пара позначається символом і називається синґлетоном.

Впорядкованою парою множин називається множина .

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

Теорема. .

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

Впорядкованою трійкою множин називається множина .

Впорядковані -ки множин означуються рекурсивною формулою: для .

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

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

Аксіома належності постулює існування класу .

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

Аксіома інверсії стверджує, що для кожного класу існує клас .

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

Клас є відношенням тоді і лише тоді, коли його елементами є впорядковані пари, тобто .

Аксіома Проекції: 

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

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

Аксіома Різниці: 

Аксіома різниці стверджує, що для довільних класів , існує клас .

З аксіоми різниці випливає існування порожнього класу , що не містить жодних елементів. За аксіомою рівності, порожній клас єдиний.

Аксіома різниці також дозволяє нам визначити перетин класів як клас . За аксіомою рівності, .

Об'єднанням двох класів називають клас , який рівний класу , що існує за аксіомою різниці.

Аксіома Добутку: 

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

Для відношення та класу клас називають образом класу при відношенні . Клас існує, оскільки він рівний класу . Клас називають прообразом класу при відношенні .

Відношення називається функцією (або відображенням), якщо для довільних пар із рівності випливає рівність . Із цього означення випливає, що для довільної функції та елемента існує єдиний елемент такий, що . Цей єдиний елемент позначається через . При цьому круглі дужки використовуються, що відрізнити елемент від класу . Для функції запис означає, що і . У цьому випадку функція ставить у відповідність кожному елементу певний елемент класу .

Функція називається ін'єктивною, якщо відношення теж є функцією.

Хоча властиві класи не можуть бути елементами інших класів, ми можемо говорити про індексовані класи класів. А саме, для довільного класу кожен підклас можна ототожнювати з індексованою сім'єю класів , де для . У цьому випадку парадокс Рассела доводить, що для класу не існує елемента з .

Аксіома Циклу:  

Аксіома циклу постулює, що для довільного класу існує клас , який далі позначатиметься через або .

Аксіома циклу, разом з іншими аксіомами існування класів, дозволяє означити об'єднання та перетин множин, що належать даному класу.

Для довільного класу клас називають об'єднанням класу .

Клас існує, оскільки він рівний класу .

Для довільного класу клас називають перетином .

Клас існує, оскільки він рівний класу .

Із означень випливає, що і

Для довільного класу клас називають експонентою класу .

Клас існує, оскільки він рівний класу . Зокрема, .

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

Аксіома регулярності стверджує, що довільна множина містить елемент , який не має з множиною спільних елементів. Аксіома регулярності забороняє існування нескінченних спадних ланцюгів виду . Аксіома регулярності часто використовується в індуктивних конструкціях.

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

Теорема Геделя про існування класів: Нехай  є формулою, у якій квантори пробігають лише по множинах, а вільні змінні містяться серед змінних . Тоді для довільних класів  клас існує.

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

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

Аксіома Заміни: Для довільної функції  та множини , образ  є множиною.
Аксіома Об'єднання: Для довільної множини  її об'єднання  є множиною.
Аксіома Експоненти: Для довільної множини  її експонента  є множиною.

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

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

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

Аксіома нескінченності постулює існування індуктивної множини. Клас називається індуктивним, якщо порожній клас є його елементом, і для кожного елемента множина є елементом . З теореми Геделя про існування класів випливає, що клас усіх індуктивних множин існує, а аксіома нескінченності постулює, що цей клас є непорожнім. Перетин усіх індуктивних множин позначають через і називають множиною натуральних чисел. Елементи множини називають натуральними числами, або скінченними ординалами.

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

Аксіома Глобального Вибору: Існує функція , що ставить у відповідність кожній непорожній множині  деякий елемент .

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

Аксіома Вибору: Для кожної множини  існує функція , що ставить у відповідність кожній непорожній множині  деякий елемент .

З іншого боку, аксіома глобального вибору випливає з аксіоми конструктивності , для формулювання якої необхідно означити клас конструктивних множин. У свою чергу, клас означується за допомогою класу ординалів .

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

  • транзитивним, якщо ;
  • лінійно -впорядкованим, якщо для довільних множин справедлива трихотомія ;
  • ординальним, якщо є транзитивним і лінійно -впорядкованим;
  • ординалом, якщо є ординальною множиною.

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

Означення. Клас називається внутрішньою моделлю, якщо транзитивний, містить усі ординали, і для довільних множин множини є елементами класу .

Найменша внутрішня модель називається класом конструктивних множин і позначається через . Клас рівний об'єднанню множин , що означаються рекурсивною формулою для . Існування класу конструктивних множин забезпечує теорема рекурсії, про яку мова нижче.

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

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

Узагальнена Гіпотеза Континуума: Для кожної нескінченної множини  та підмножини  існує ін'єктивна функція  така, що  або .

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


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

  1. Аксіома Рівності: Два класи рівні тоді і лише тоді, коли вони складаються з однакових елементів.
  2. Аксіома Пари: Для довільних множин існує невпорядкована пара .
  3. Аксіома Належності: Клас існує.
  4. Аксіома Інверсії: Для довільного класу , клас існує.
  5. Аксіома Проекції: Для довільного класу , клас існує.
  6. Аксіома Добутку: Для довільних класів , клас існує.
  7. Аксіома Різниці: Для довільних класів , клас існує.
  8. Аксіома Циклу: Для довільного класу клас існує.
  9. Аксіома Регулярності: Довільна непорожня множина містить такий елемент , що .
  10. Аксіома Заміни: Для довільної функції і довільної множини , клас є множиною.
  11. Аксіома Суми: Для довільної множини , клас є множиною.
  12. Аксіома Експоненти: Для довільної множини , її експонента є множиною.
  13. Аксіома Нескінченності: Існує множина натуральних чисел .
  14. Аксіома Глобального Вибору: Існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .

Зв'язок аксіоматики NBG з аксіоматикою ZFC[ред. | ред. код]

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

  1. Аксіома рівності: .
  2. Аксіома пари: .
  3. Аксіома суми: .
  4. Аксіома експоненти: .
  5. Аксіома Регулярності: .
  6. Аксіома Нескінченності: .
  7. Схема Аксіом Вирізання: Нехай  — формула в мові ZFC, усі вільні змінні якої містяться серед змінних , а змінна не вільна для формули . Тоді .
  8. Схема Аксіом Заміни: Нехай  — формула в мові ZFC, усі вільні змінні якої містяться серед змінних , а змінна не є вільною для формули . Тоді .
  9. Аксіома Вибору: Для кожної множини існує функція , що ставить у відповідність кожній непорожній множині деякий елемент .

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

Теорема рекурсії[ред. | ред. код]

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

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

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

  • рефлексивним, якщо ;
  • антисиметричним, якщо ;
  • транзитивним, якщо ;
  • частковим порядком, якщо є рефлексивним, транзитивним, антисиметричним відношенням;
  • лінійним порядком, якщо є частковим порядком з ;
  • ґрунтовним (англ., well-founded), якщо для кожної множини клас є множиною і кожна непорожня підмножина містить такий елемент , що . Такий елемент називають -мінімальним елементом множини .
  • цілковитим порядком, якщо відношення є ґрунтовним лінійним порядком.

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

Теорема Рекурсії. Якщо  — ґрунтовний частковий порядок, тоді для довільної функції , існує єдина функція  така, що   для кожного  

Для доведення теореми рекурсії розглядають клас , елементами якого є функції , для яких існує такий елемент , що і для кожного . Тоді об'єднання є шуканою функцією .

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

  • ;
  • .

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

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

Щоб довести теорему про ізоморфізм, достатньо застосувати теорему рекурсії до функції

Історія створення аксіоматики NBG[ред. | ред. код]

Аксіоматика фон Ноймана — Бернайса — Геделя є результатом тривалої еволюції. У роботах 1925, 1928 та 1929 років Джон фон Нойман опублікував свою аксіоматичну систему, у якій первинними поняттями були функція та аргумент. Поль Бернайс[en] у працях 1931, 1937, 1941 років дошліфував теорію фон Ноймана до належного блиску; він означив функції як класи бінарних відношень та вибрав первинними поняттями теорії поняття класу та множини, причому Бернайс використовував різні символи і для позначення множини до іншої множини чи до класу . Також він вважав, що множина зображає клас , якщо . Аксіоматика Бернайса (яку він виклав у своєму листі Геделю у 1931) складалася з 20 аксіом, які включали 9 аксіом існування класів, зокрема аксіоми інверсії на асоціативності. Аксіома асоціативності Бернайса стверджує, що для кожного класу клас існує. Курт Гедель, після знайомства з теорією Бернайса, запропонував спростити понятійну систему теорії: звести поняття множини до поняття класу і використовувати єдине відношення належності для класів та множин. Він також замінив аксіоми інверсії та асоціативності Бернайса на аксіоми транспозиції та циклічної перестановки, які постулюють існування класів та для кожного класу . Гедель використав таким чином модифіковану версію аксіоматики Бернайса у своєму знаменитому доведенні несуперечливості аксіоми вибору та гіпотези континуума, довівши, що вони є чинними в конструктивному універсумі . Більше того, він зауважив, що в конструктивному універсумі справджується аксіома глобального вибору, що дало змогу долучити її до списку аксіом NBG без небезпеки отримати суперечність. Абревіатуру NBG у математичний вжиток увів великий адепт цієї теорії Еліотт Мендельсон[en], про що він пише у своїй класичній книзі з Математичної Логіки,[1] де також згадує, що Paul Halmos, який віддавав перевагу аксіоматиці ZFC, жартома розшифровував NBG як сленгове «No Bloody Good». Про роль фон Ноймана, Бернайса та Геделя у створенні аксіоматики NBG можна почитати у статті Kanamori, 2009.

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

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

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

Означення категорії. Категорією називаємо п'ятірку , де:
 — клас, елементи якого називаються морфізмами категорії;
 — підклас класу , елементи якого називаються об'єктами категорії
(таким чином ми ототожнюємо об'єкти з тотожніми морфізмами цих об'єктів);  — два класи, які є функціями з Mor в Ob; значення і на морфізмі називають початком і кінцем морфізму ;
для довільних об'єктів підклас називається класом морфізмів з в ;  — функція з областю визначення і областю значень , яка ставить у відповідність кожній парі морфізмів морфізм , що має і ; морфізм називається композицією морфізмів . При цьому повинні задовольнятися такі аксіоми: (Об'єктність): для довільного об'єкта ; (Нейтральність): для довільного морфізма ; (Асоціативність): Для довільних морфізмів з i справджується рівність ;
Категорія  називається 
 локально малою категорією, якщо для довільних об'єктів , клас морфізмів є множиною;
 малою категорією, якщо її клас морфізмів  є множиною. 

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

Означення функтора. Функтором  між категоріями  та  називаємо функцію , яка зберігає структуру категорії у тому сенсі, що :
  і  для довільного морфізма ;
  для довільних морфізмів  з .

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

Означення природного перетворення. Нехай  — два функтори між категоріями   та . Природним перетворенням функтора  у функтор  називаємо довільну функцію , що ставить у відповідність кожному об'єкту  морфізм  категорії  таким чином, що задовольняється 
(Умова природності): Для довільного морфізму   категорії  справедлива рівність .


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

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

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

Перерізом лінійного порядку називається впорядкована пара множин , яка задовольняє умови:

  • i ;
  • .

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

Сюрреальна пряма є областю визначення лінійного порядку , що є об'єднанням лінійних порядків , які задаються рекурсивною формулою:

Існування класу забезпечує теорема рекурсії. Нескладно переконатися, що сюрреальна пряма містить усі ординали.

Конвей[2] та Кнут[3] довели, що звичайні операції додавання і множення натуральних чисел продовжуються до операцій додавання і множення сюрреальних чисел. Ці операції перетворюють сюрреальну пряму, наділену лінійним порядком , на впорядковане поле, що містить ізоморфні копії всіх інших впорядкованих полів. Використовуючи ці алгебраїчні операції над сюрреальними числами, можна цілком законно застосовувати їх до ординалів і говорити, наприклад, про частки чи квадратні корені з ординалів. Ці дивовижні властивості сюрреальної прямої свідчать про її фундаментальну роль у теорії NBG.

Примітки[ред. | ред. код]

Джерела[ред. | ред. код]