Теорія множин фон Неймана — Бернайса — Геделя
Теорія множин та класів фон Ноймана — Бернайса — Геделя (скорочено NBG) — аксіоматична теорія першого порядку, що є (консервативним) розширенням теорії множин ZF Цермело — Френкеля. На відміну від ZF, NBG є скінченно аксіоматизовною теорією, яка дозволяє вільно оперувати як множинами, так і класами. Окрім стандартних логічних зв'язок, кванторів та символу рівності, мова теорії NBG включає символ бінарного відношення , що інтерпретується як належність.
Первинними (тобто неозначуваними) поняттями теорії NBG є поняття класу та елемента. Клас може бути елементом іншого класу , це позначається як . Позначення є скороченим записом формули .
Два класи називають рівними, якщо вони складаються з однакових елементів, тобто , якщо .
Клас називається множиною, якщо він є елементом деякого класу, тобто якщо . Клас, який не є множиною, називають властивим класом (англ. proper class). Щоб розрізняти класи та множини, для позначення класів вживають великі літери, а для множин — малі. Властиві класи позначають великими товстими літерами. Прикладом такого класу є клас усіх множин.
Розрізнення класів та множин дозволяє уникнути відомого парадоксу Рассела, який у випадку NBG стає доведенням того, що клас не є множиною.
Система NBG містить 13 аксіом і може доповнюватися аксіомою (глобального) вибору або аксіомою конструктивності.
Аксіоми NBG
ред.Аксіома рівності
ред.З аксіоми рівності випливає, що рівні класи неможливо розрізними відношенням належності.
Клас називається підкласом класу , якщо кожен елемент класу є елементом класу . У цьому випадку пишемо .
Тобто, . .
Підклас класу називаємо підмножиною класу , якщо є множиною.
Аксіома пари
ред.Аксіома пари постулює, що для довільних множин існує множина , єдиними елементами якої є множини . Така множина називається невпорядкованою парою множин і позначається символом . З аксіоми рівності випливає рівність . Невпорядкована пара позначається символом і називається синґлетоном.
Впорядкованою парою множин називається множина .
З аксіоми рівності випливає
Теорема. .
Ця теорема стверджує, що впорядковані пари і рівні тоді і лише тоді, коли і .
Впорядкованою трійкою множин називається множина .
Впорядковані -ки множин означуються рекурсивною формулою: для .
Наступні 5 аксіом називають аксіомами існування класів.
Аксіома належності
ред.Аксіома належності постулює існування класу .
Аксіома Інверсії
ред.Аксіома інверсії стверджує, що для кожного класу існує клас .
Клас називається відношенням, якщо .
Клас є відношенням тоді і лише тоді, коли його елементами є впорядковані пари, тобто .
Аксіома проєкції
ред.Згідно з аксіомами проєкції та інверсії, для кожного класу існують класи та . Якщо клас є відношенням (наприклад, функцією), то класи та називають областю визначення та областю значень відношення .
З аксіом належності та проєкції випливає, що клас усіх множин існує, оскільки він збігається з областю визначення відношення належності .
Аксіома різниці
ред.Аксіома різниці стверджує, що для довільних класів , існує клас .
З аксіоми різниці випливає існування порожнього класу , що не містить жодних елементів. За означенням рівності, порожній клас єдиний.
Аксіома різниці також дозволяє нам визначити перетин класів як клас . За означенная рівності, .
Об'єднанням двох класів називають клас , який рівний класу , що існує за аксіомою різниці.
Аксіома добутку
ред.Аксіома добутку постулює, що для довільних класів існує їх декартів добуток .
Для відношення та класу клас називають образом класу при відношенні . Клас існує, оскільки він рівний класу . Клас називають прообразом класу при відношенні .
Відношення називається функцією (або відображенням), якщо для довільних пар із рівності випливає рівність . Із цього означення випливає, що для довільної функції та елемента існує єдиний елемент такий, що . Цей єдиний елемент позначається через . При цьому круглі дужки використовуються, що відрізнити елемент від класу . Для функції запис означає, що і . У цьому випадку функція ставить у відповідність кожному елементу певний елемент класу .
Функція називається ін'єктивною, якщо відношення теж є функцією.
Хоча властиві класи не можуть бути елементами інших класів, ми можемо говорити про індексовані класи класів. А саме, для довільного класу кожен підклас можна ототожнювати з індексованою сім'єю класів , де для . У цьому випадку парадокс Рассела доводить, що для класу не існує елемента з .
Аксіома циклу
ред.Аксіома циклу постулює, що для довільного класу існує клас , який далі позначатиметься через або .
Для довільного класу клас називають об'єднанням класу .
Клас існує, оскільки він рівний класу .
Для довільного класу клас називають перетином .
Клас існує, оскільки він рівний класу .
Із означень випливає, що і
Для довільного класу клас називають експонентою класу .
Клас існує, оскільки він рівний класу . Зокрема, .
Аксіома регулярності
ред.- .
Аксіома регулярності стверджує, що довільна непорожня множина містить елемент , який не має з множиною спільних елементів. Аксіома регулярності забороняє існування нескінченних спадних ланцюгів виду . Аксіома регулярності часто використовується в індуктивних конструкціях.
Використовуючи аксіому регулярності та аксіоми існування класів, Гедель довів (індукцією по складності формули ) наступну важливу теорему, обмежена форма якої приймається за аксіому вирізання[прояснити] в аксіоматиці Цермело — Френкеля.
Теорема Геделя про існування класів: Нехай є формулою, у якій квантори пробігають лише по множинах, а вільні змінні містяться серед змінних . Тоді для довільних класів клас існує.
Доступне доведення цієї теореми можна знайти в англійській версії статті про аксіоматику NBG, або в монографії Мендельсона[en].[1]
Наступні 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), якщо для кожної множини клас є множиною і кожна непорожня підмножина містить такий елемент , що . Такий елемент називають -мінімальним елементом множини .
- цілковитим порядком, якщо відношення є ґрунтовним лінійним порядком.
Зауважимо, що аксіома регулярності є еквівалентною ґрунтовності відношення належності .
Теорема Рекурсії. Якщо — ґрунтовний частковий порядок, тоді для довільної функції , існує єдина функція така, що для кожного
Для доведення теореми рекурсії розглядають клас , елементами якого є функції , для яких існує такий елемент , що і для кожного . Тоді об'єднання є шуканою функцією .
Означення. Відношення називають ізоморфними, якщо існує ін'єктивна функція , яка має такі властивості:
- ;
- .
Із теореми рекурсії випливає такий фундаментальний факт.
Теорема про ізоморфізм. Кожен цілковитий порядок є ізоморфним єдиному ординальному класу. Цей ординальний клас є ординалом, якщо — множина, і рівним класу , якщо є властивим класом.
Щоб довести теорему про ізоморфізм, достатньо застосувати теорему рекурсії до функції
Історія створення аксіоматики 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.
Див. також
ред.Примітки
ред.- ↑ а б Mendelson, 1997.
- ↑ Conway, 1976.
- ↑ Knuth, 1974.
Джерела
ред.Ця стаття містить перелік посилань, але походження окремих тверджень залишається незрозумілим через брак внутрішньотекстових джерел-виносок. (квітень 2020) |
- 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[en], 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[de], 154: 219—240
- von Neumann, John (1928), Die Axiomatisierung der Mengenlehre, Mathematische Zeitschrift[de], 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.