Teoria mnogości von Neumanna-Bernaysa-Gödla - Von Neumann–Bernays–Gödel set theory

W podstaw matematyki , von Neumann-Bernays-Gödel teoria mnogości ( NBG ) to aksjomat zestaw teoria , że jest konserwatywny rozszerzenie z Zermelo-Fraenkel wyboru teorii mnogości (ZFC). NBG przedstawia koncepcję z grupy , który to zbiór zestawów zdefiniowanych przez wzorze której kwantyfikatorów w zakresie tylko na zestawach. NBG może definiować klasy, które są większe niż zbiory, takie jak klasa wszystkich zbiorów i klasa wszystkich liczb porządkowych . Teoria mnogości Morse'a-Kelley'a (MK) pozwala na definiowanie klas za pomocą formuł, których kwantyfikatory są w zakresie klas. NBG jest skończenie aksjomatyzowalne, podczas gdy ZFC i MK nie.

Kluczowym twierdzeniem NBG jest twierdzenie o istnieniu klasy, które mówi, że dla każdej formuły, której kwantyfikatory obejmują tylko zbiory, istnieje klasa składająca się ze zbiorów spełniających formułę. Ta klasa jest tworzona przez dublowanie krok po kroku konstrukcji formuły z klasami. Ponieważ wszystkie formuły teorii mnogości są konstruowane z dwóch rodzajów formuł atomowych ( przynależność i równość ) i skończenie wielu symboli logicznych , tylko skończenie wiele aksjomatów jest potrzebnych do zbudowania klas je spełniających. Dlatego NBG jest skończenie aksjomatyzowalne. Klasy są również używane do innych konstrukcji, do obsługi paradoksów teorii mnogości , oraz do określania aksjomatu globalnego wyboru , który jest silniejszy niż aksjomat wyboru ZFC .

John von Neumann wprowadził zajęcia do teorii mnogości w 1925 roku. Pierwotnymi pojęciami jego teorii były funkcja i argument . Używając tych pojęć zdefiniował klasę i zbiór. Paul Bernays przeformułował teorię von Neumanna, przyjmując klasę i zestaw jako pojęcia pierwotne. Kurt Gödel uprościł teorię Bernaysa dla jego względnego dowodu spójności aksjomatu wyboru i uogólnionej hipotezy continuum .

Zajęcia z teorii mnogości

Zastosowania zajęć

Klasy mają kilka zastosowań w NBG:

  • Tworzą skończoną aksjomatyzację teorii mnogości.
  • Są one używane do stwierdzenia „bardzo silnej formy aksjomatu wyboru ” – mianowicie aksjomatu wyboru globalnego : Istnieje funkcja globalnego wyboru zdefiniowana w klasie wszystkich niepustych zbiorów tak, że dla każdego niepustego zbioru jest to silniejsze niż w ZFC aksjomat wyboru: dla każdego zbioru niepustych zbiorów istnieje funkcja wyboru zdefiniowana w taki sposób, że dla wszystkich
  • Te paradoksy set-teoretyczny są obsługiwane przez uznanie, że niektóre klasy nie mogą być zestawy. Na przykład załóżmy, że klasa wszystkich liczb porządkowych jest zbiorem. Wtedy jest zbiorem przechodnim dobrze uporządkowanym przez . Tak więc z definicji jest porządkiem. Zatem , co przeczy byciu dobrym uporządkowaniem Dlatego nie jest zbiorem. Ponieważ klasa, która nie jest zbiorem nazywana jest klasą właściwą , jest klasą właściwą.
  • W konstrukcjach przydatne są odpowiednie klasy. W swoim dowodzie na względną spójność aksjomatu globalnego wyboru i uogólnionej hipotezy continuum , Gödel użył odpowiednich klas do zbudowania dającego się zbudować wszechświata . Skonstruował funkcję na klasie wszystkich liczb porządkowych, która dla każdej liczby porządkowej buduje zbiór konstruowalny przez zastosowanie operacji budowania zbioru do wcześniej skonstruowanych zbiorów. Konstrukcyjny wszechświat jest obrazem tej funkcji.

Schemat aksjomatu a twierdzenie o istnieniu klasy

Po dodaniu klas do języka ZFC, łatwo jest przekształcić ZFC w teorię mnogości z klasami. Najpierw dodawany jest schemat aksjomatu rozumienia klas. Aksjomat ten stany schematu: Dla każdego wzoru , który określa tylko ponad zestawów istnieje klasę składającą się z - krotki spełniające wzór, to znaczy wtedy aksjomat zastępowania jest zastąpiony przez pojedynczego aksjomatu , że używa klasy. Wreszcie, aksjomat ekstensjonalnosci ZFC został zmodyfikowany do obsługi klas: Jeśli dwie klasy mają te same elementy, to są one identyczne. Pozostałe aksjomaty ZFC nie są modyfikowane.

Teoria ta nie jest skończenie zaksjomatyzowana. Schemat zastępczy ZFC został zastąpiony pojedynczym aksjomatem, ale wprowadzono schemat aksjomatu rozumienia klas.

Aby stworzyć teorię ze skończoną liczbą aksjomatów, schemat aksjomatów rozumienia klas zostaje najpierw zastąpiony skończoną liczbą aksjomatów istnienia klas . Następnie te aksjomaty są używane do udowodnienia twierdzenia o istnieniu klasy, które implikuje każdą instancję schematu aksjomatu. Dowód tego twierdzenia wymaga tylko siedem axioms klasy istnienie, które są wykorzystywane do przeliczenia budowę wzorze w budowie klasy zgodnej z formuły.

Aksjomatyzacja NBG

Zajęcia i zestawy

NBG ma dwa rodzaje obiektów: klasy i zbiory. Intuicyjnie każdy zestaw to także klasa. Są dwa sposoby na aksjomatyzację tego. Bernays zastosował logikę o wielu sortowaniach z dwoma rodzajami: klasami i zbiorami. Gödel unikał sortowania, wprowadzając predykaty prymitywne: for " jest klasą" i dla " jest zbiorem" (po niemiecku "zbiór" to Menge ). Wprowadził również aksjomaty mówiące, że każdy zbiór jest klasą i że jeśli klasa jest członkiem klasy, to jest zbiorem. Używanie predykatów to standardowy sposób na wyeliminowanie sortowań. Elliott Mendelson zmodyfikował podejście Gödla poprzez ustawienie wszystkiego jako klasy i zdefiniowanie predykatu zbioru jako Ta modyfikacja eliminuje predykat klasy Gödla i jego dwa aksjomaty.

Dwustronne podejście Bernaysa może początkowo wydawać się bardziej naturalne, ale tworzy bardziej złożoną teorię. W teorii Bernaysa każdy zbiór ma dwie reprezentacje: jedną jako zbiór, a drugą jako klasę. Ponadto istnieją dwie relacje przynależności : pierwsza, oznaczona literą „∈”, zachodzi między dwoma zestawami; drugi, oznaczony przez „η”, znajduje się między zestawem a klasą. Ta nadmiarowość jest wymagana przez logikę o wielu sortowaniach, ponieważ zmienne różnego rodzaju rozciągają się na rozłącznych poddziedzinach domeny dyskursu .

Różnice między tymi dwoma podejściami nie wpływają na to, co można udowodnić, ale wpływają na sposób pisania oświadczeń. W podejściu Gödla gdzie i są klasami jest poprawnym stwierdzeniem. W ujęciu Bernaysa to stwierdzenie nie ma znaczenia. Jednakże, jeśli jest zbiorem, istnieje równoważna instrukcja: Zdefiniuj „zbiór reprezentuje klasę ”, jeśli mają takie same zbiory jak składowe — to znaczy, Wyrażenie gdzie zbiór reprezentuje klasę jest równoważne ze zbiorem Gödla

Podejście przyjęte w tym artykule to podejście Gödla z modyfikacją Mendelsona. Oznacza to, że NBG jest systemem aksjomatycznym w logice predykatów pierwszego rzędu z równością , a jego jedynymi pojęciami pierwotnymi są klasa i relacja przynależności.

Definicje i aksjomaty ekstensjalności i parowania

Zbiór to klasa, która należy do co najmniej jednej klasy: jest zbiorem wtedy i tylko wtedy, gdy . Klasa, która nie jest zbiorem, nazywana jest klasą właściwą: jest klasą właściwą wtedy i tylko wtedy, gdy . Dlatego każda klasa jest albo zbiorem, albo klasą właściwą, a żadna klasa nie jest obydwoma (jeśli teoria jest spójna ).

Gödel wprowadził konwencję, że zmienne pisane dużymi literami obejmują zakresy klas, podczas gdy zmienne pisane małymi literami obejmują zakresy zestawów. Gödel używał również nazw zaczynających się od wielkiej litery do oznaczenia poszczególnych klas, w tym funkcji i relacji zdefiniowanych w klasie wszystkich zbiorów. W tym artykule zastosowano konwencję Gödla. Pozwala nam napisać:

Do udowodnienia twierdzenia o istnieniu klasy potrzebne są następujące aksjomaty i definicje.

Aksjomat rozszerzalności. Jeśli dwie klasy mają te same elementy, to są one identyczne.

Aksjomat ten uogólnia ZFC za aksjomat ekstensjonalności do klas.

Aksjomat parowania . Jeśliisą zbiorami, to istnieje zbiór,którego jedynymi członkami sąi.

Podobnie jak w ZFC, aksjomat ekstensjonalnosci implikuje jednoznacznosc zbioru , co pozwala nam na wprowadzenie notacji

Zamówione pary są definiowane przez:

Krotki definiuje się indukcyjnie za pomocą uporządkowanych par:

Aksjomaty istnienia klasy i aksjomat regularności

Aksjomaty istnienia klasy zostaną użyte do udowodnienia twierdzenia o istnieniu klasy: Dla każdej formuły w zmiennych zbioru swobodnego, która kwantyfikuje się tylko po zbiorach, istnieje klasa krotek, które ją spełniają. Poniższy przykład zaczyna się od dwóch klas, które są funkcjami i buduje funkcję złożoną . Ten przykład ilustruje techniki potrzebne do udowodnienia twierdzenia o istnieniu klasy, które prowadzą do potrzebnych aksjomatów o istnieniu klasy.

Przykład 1: Jeśli klasy i są funkcjami, to funkcja złożona jest zdefiniowana przez formułę: Ponieważ formuła ta ma dwie wolne zmienne zbioru, a twierdzenie o istnieniu klasy konstruuje klasę par uporządkowanych:

Ponieważ formuła ta jest zbudowana z prostszych formuł przy użyciu koniunkcji i kwantyfikacji egzystencjalnej , potrzebne są operacje klas , które pobierają klasy reprezentujące prostsze formuły i tworzą klasy reprezentujące formuły za pomocą i . Aby utworzyć klasę reprezentującą formułę z , przecięcie używane od Aby utworzyć klasę reprezentującą formułę z , domena jest używana od

Przed wykonaniem skrzyżowania krotki są potrzebne i potrzebują dodatkowego komponentu, aby miały te same zmienne. Składnik jest dodawany do krotek i jest dodawany do krotek :

oraz

W definicji zmienna nie jest ograniczona przez stwierdzenie, więc obejmuje klasę wszystkich zbiorów. Podobnie w definicji zmiennej obejmuje zakres powyżej Tak potrzebny jest aksjomat, który dodaje dodatkowy składnik (którego wartości mieszczą się w zakresie powyżej ) do krotek danej klasy.

Następnie zmienne są umieszczane w tej samej kolejności, aby przygotować się do skrzyżowania:

oraz

Przejście od do i od do wymaga dwóch różnych permutacji , więc potrzebne są aksjomaty, które obsługują permutacje składowych krotek.

Przecięcie i uchwyty :

Ponieważ jest zdefiniowany jako , biorąc dziedzinę uchwytów i tworzy funkcję złożoną:

Potrzebne są więc aksjomaty przecięcia i dziedziny.

Aksjomaty istnienia klasy dzielą się na dwie grupy: aksjomaty obsługujące prymitywy językowe i aksjomaty obsługujące krotki. W pierwszej grupie są cztery aksjomaty, a w drugiej trzy aksjomaty.

Aksjomaty do obsługi prymitywów językowych:

Członkostwo. Istnieje klasa zawierająca wszystkie uporządkowane pary, których pierwszy składnik należy do drugiego składnika.

Skrzyżowanie (koniunkcja). Dla dowolnych dwóch klas i istnieje klasa składająca się właśnie ze zbiorów należących do obu i .

Uzupełnienie (negacja). Dla każdej klasyistnieje klasaskładająca się właśnie ze zbiorów nie należących do.

Dziedzina (kwantyfikator egzystencjalny). Dla każdej klasy istnieje klasa składająca się właśnie z pierwszych składowych uporządkowanych par .

Zgodnie z aksjomatem ekstensjonalności, klasa w aksjomatach przecięcia i klasa w aksjomatach dopełnienia i dziedziny są unikalne. Będą one oznaczone odpowiednio: i . Z drugiej strony ekstensjalność nie ma zastosowania do aksjomatu przynależności, ponieważ określa on tylko te zbiory, które są parami uporządkowanymi.

Pierwsze trzy aksjomaty implikują istnienie pustej klasy i klasy wszystkich zbiorów: Aksjomat przynależności implikuje istnienie klasy Aksjomaty przecięcia i dopełnienia implikują istnienie , który jest pusty. Zgodnie z aksjomatem ekstensjonalnosci ta klasa jest unikalna; jest oznaczony przez Dopełnienie jest klasą wszystkich zbiorów, która jest również unikalna przez rozszerzalność. Predykat zestawu , który został zdefiniowany jako , jest teraz przedefiniowany, aby uniknąć kwantyfikacji po klasach.

Aksjomaty obsługi krotek:

Produkt wg . Dla każdej klasyistnieje klasaskładająca się z uporządkowanych par, do których należy pierwszy składnik.

Permutacja kołowa . Dla każdej klasyistnieje klasa,której 3 krotki uzyskuje się przez zastosowanie permutacji kołowejdo 3 krotek.

Transpozycja . Dla każdej klasyistnieje klasa,której 3-krotki uzyskuje się przez transpozycję dwóch ostatnich składników 3-krotnych.

Przez ekstensjonalnosc iloczyn przez aksjomat implikuje istnienie unikalnej klasy, która jest oznaczona przez Ten aksjomat jest używany do zdefiniowania klasy wszystkich -krotek : a Jeśli jest klasą, ekstensjalność implikuje, że jest to unikalna klasa składająca się z krotek - of Na przykład aksjomat przynależności tworzy klasę, która może zawierać elementy, które nie są uporządkowanymi parami, podczas gdy przecięcie zawiera tylko uporządkowane pary .

Aksjomaty permutacji kołowej i transpozycji nie implikują istnienia unikalnych klas, ponieważ określają one tylko krotki klasy 3 Określając krotki 3, aksjomaty te określają również krotki dla ponieważ: Aksjomaty dotyczące obsługi krotek i aksjomat dziedziny implikują następujący lemat, który jest używany w dowodzie twierdzenia o istnieniu klasy.

Lemat krotki.

Dowód:   Klasa : Zastosuj produkt przez to, aby wytworzyć Klasa : Zastosuj transpozycję, aby wytworzyć Klasa : Zastosuj permutację kołową, aby wytworzyć Klasa : Zastosuj permutację kołową do , a następnie zastosuj domenę, aby wyprodukować
            
            
            

Do udowodnienia twierdzenia o istnieniu klas potrzebny jest jeszcze jeden aksjomat: aksjomat regularności . Ponieważ udowodniono istnienie pustej klasy, podano zwykłe stwierdzenie tego aksjomatu.

Aksjomat prawidłowości . Każdy niepusty zbiór ma przynajmniej jeden element, z którym nie ma wspólnego elementu.

Ten aksjomat implikuje, że zbiór nie może należeć do samego siebie: Załóżmy to i niech Wtedy ponieważ To jest sprzeczne z aksjomatem regularności, ponieważ jest jedynym elementem w Dlatego Aksjomat regularności zabrania również nieskończenie malejących sekwencji przynależności zbiorów:

Gödel stwierdził regularność dla klas, a nie dla zbiorów w swojej monografii z 1940 roku, opartej na wykładach z 1938 roku. W 1939 roku udowodnił, że regularność dla zbiorów implikuje regularność dla klas.

Twierdzenie o istnieniu klasy

Twierdzenie o istnieniu klasy. Niech będzie formułą, która określa ilościowo tylko dla zbiorów i nie zawiera żadnych wolnych zmiennych innych niż (niekoniecznie wszystkie z nich). Wtedy dla wszystkich , istnieje unikalną klasę z -tuples takie, że: Klasa oznaczamy

Dowód twierdzenia zostanie wykonany w dwóch krokach:

  1. Reguły transformacji służą do przekształcenia podanej formuły w równoważną formułę, która upraszcza indukcyjną część dowodu. Na przykład, symbole logiczne w transformowanych wzorze są takie , i tak indukcja uchwyty symboli logicznego za pomocą trzech przypadkach.
  2. Twierdzenie o istnieniu klasy jest udowadniane indukcyjnie dla formuł przekształconych. Kierując się strukturą przekształconej formuły, aksjomaty istnienia klasy służą do stworzenia unikalnej klasy krotek spełniających formułę.

Zasady transformacji. W regułach 1 i 2 poniżej oraz oznaczają zmienne zestawu lub klasy. Te dwie reguły eliminują wszystkie wystąpienia zmiennych klas przed wystąpieniem równości. Za każdym razem, gdy reguła 1 lub 2 jest stosowana do podformuły, jest wybierana tak, aby różniła się od innych zmiennych w bieżącej formule. Te trzy zasady są powtarzane do momentu, gdy nie ma podformuł, do których można by je zastosować. Daje to formułę zbudowaną tylko z , , , , zmiennymi zestawu i zmiennymi klas, gdzie nie występuje przed .

  1. przekształca się w
  2. Rozszerzalność służy do przekształcenia w
  3. Tożsamości logiczne są używane do przekształcania podformuł zawierających i do podformuł, które używają tylko i

Reguły transformacji: zmienne powiązane . Rozważmy formułę funkcji złożonej z przykładu 1 z jej zmiennymi swobodnymi zastąpionymi przez i : Dowód indukcyjny usunie , który daje formułę Jednak ponieważ twierdzenie o istnieniu klasy jest podane dla zmiennych z indeksem dolnym, formuła ta nie ma postaci oczekiwanej przez hipoteza indukcji . Ten problem jest rozwiązany przez zastąpienie zmiennej z Związane zmiennych w zagnieżdżonych kwantyfikatorów są obsługiwane zwiększając indeks o jeden dla każdego rzędu kwantyfikatora. Prowadzi to do reguły 4, którą należy zastosować po innych regułach, ponieważ reguły 1 i 2 dają zmienne ilościowe.

  1. Jeśli formuła nie zawiera żadnych wolnych zmiennych zestawów innych niż zmienne powiązane, które są zagnieżdżone w kwantyfikatorach, są zastępowane przez . Te zmienne mają (kwantyfikator) głębokość zagnieżdżenia .

Przykład 2: Reguła 4 jest zastosowana do formuły, która definiuje klasę składającą się ze wszystkich zestawów postaci To znaczy zestawów zawierających co najmniej i zestaw zawierający — na przykład gdzie i są zestawami.

Ponieważ jest jedyną wolną zmienną, Zmienna kwantyfikowana pojawia się dwukrotnie na głębokości zagnieżdżenia 2. Jej indeks dolny wynosi 3, ponieważ Jeśli dwa zakresy kwantyfikatora są na tej samej głębokości zagnieżdżenia, są albo identyczne, albo rozłączne. Te dwa wystąpienia znajdują się w rozłącznych zakresach kwantyfikatorów, więc nie wchodzą ze sobą w interakcje.

Dowód twierdzenia o istnieniu klas. Dowód rozpoczyna się od zastosowania reguł transformacji do danej formuły w celu uzyskania przekształconej formuły. Ponieważ ta formuła jest równoważna podanej formule, dowód jest uzupełniany poprzez udowodnienie twierdzenia o istnieniu klasy dla formuł przekształconych.

Gödel wskazał, że twierdzenie o istnieniu klasy „jest metateoremem , czyli twierdzeniem o systemie [NBG], a nie o systemie…” Jest to twierdzenie o NBG, ponieważ jest udowodnione w metateorii przez indukcję na formułach NBG. Ponadto jego dowód — zamiast wywoływać skończoną liczbę aksjomatów NBG — indukcyjnie opisuje, jak użyć aksjomatów NBG do skonstruowania klasy spełniającej daną formułę. Dla każdej formuły opis ten można przekształcić w konstruktywny dowód istnienia, który znajduje się w NBG. Dlatego to metatwierdzenie może generować dowody NBG, które zastępują użycie twierdzenia o istnieniu klasy NBG.

Rekurencyjne program komputerowy zwięźle oddaje budowę klasie z danego wzoru. Definicja tego programu nie zależy od dowodu twierdzenia o istnieniu klasy. Jednak dowód jest potrzebny, aby udowodnić, że klasa konstruowana przez program spełnia zadany wzór i jest budowana z wykorzystaniem aksjomatów. Ten program jest napisany w pseudokodzie, który używa instrukcji case w stylu Pascala .



Niech będzie formuła z przykładu 2 . Wywołanie funkcji generuje klasę która jest porównywana poniżej To pokazujeże konstrukcja klasy odzwierciedla konstrukcjęjej formuły definiującej

Rozszerzenie twierdzenia o istnieniu klas

Gödel rozszerzył twierdzenie o istnieniu klas na formuły zawierające relacje nad klasami (takie jak i jednoargumentowa relacja ), klasy specjalne (takie jak ) i operacje (takie jak i ). Aby rozszerzyć twierdzenie o istnieniu klas, formuły definiujące relacje, klasy specjalne i operacje muszą być kwantyfikowane tylko na zbiorach. Następnie można go przekształcić w równoważną formułę spełniającą hipotezę twierdzenia o istnieniu klasy .

Poniższe definicje określają, w jaki sposób formuły definiują relacje, klasy specjalne i operacje:

  1. Relację definiuje:
  2. Klasę specjalną definiuje:
  3. Operacja jest określona przez:

Okres jest określony przez:

  1. Zmienne i klasy specjalne to terminy.
  2. Jeśli jest operacją z argumentami i są terminami, to jest terminem.

Poniższe reguły transformacji eliminują relacje, klasy specjalne i operacje. Za każdym razem, gdy reguła 2b, 3b lub 4 jest stosowana do podformuły, jest wybierana tak, aby różniła się od innych zmiennych w bieżącej formule. Reguły są powtarzane do momentu, gdy nie ma podformuł, do których można by je zastosować. i oznaczają terminy.

  1. Relację zastępuje jej definiująca formuła
  2. Niech będzie formułą definiującą klasę specjalną
    1. jest zastąpiony przez
    2. jest zastąpiony przez
  3. Niech będzie formułą definiującą operację
    1. jest zastąpiony przez
    2. jest zastąpiony przez
  4. Rozszerzalność służy do przekształcenia w
Przykład 3: Transformacja

Przykład 4: Transformacja

Ten przykład ilustruje, jak reguły transformacji współpracują ze sobą w celu wyeliminowania operacji.

Twierdzenie o istnieniu klasy (wersja rozszerzona). Niech będzie formułą, która określa ilościowo tylko na zestawach, nie zawiera wolnych zmiennych innych niż i może zawierać relacje, specjalne klasy i operacje zdefiniowane przez formuły, które określają ilościowo tylko na zestawach. Wtedy dla wszystkich istnieje unikalną klasę z -tuples takie, że

Dowód: Zastosuj reguły transformacji, aby utworzyć równoważną formułę, która nie zawiera relacji, klas specjalnych ani operacji. Formuła ta spełnia hipotezę twierdzenia o istnieniu klasy. Dlatego też, dla wszystkich jest wyjątkowa klasa z -tuples zaspokajania

Ustaw aksjomaty

Powyżej podano aksjomaty parowania i regularności, które były potrzebne do dowodu twierdzenia o istnieniu klasy. NBG zawiera cztery inne aksjomaty zbioru. Trzy z tych aksjomatów dotyczą operacji na klasach stosowanych na zbiorach.

Definicja. jest funkcją, jeśli

W teorii mnogości definicja funkcji nie wymaga określania dziedziny lub kodziedziny funkcji (patrz Funkcja (teoria mnogości) ). Definicja funkcji NBG uogólnia definicję ZFC ze zbioru uporządkowanych par do klasy uporządkowanych par.

Definicje ZFC dotyczące operacji na zbiorach obrazów , union i power set są również uogólniane na operacje na klasach . Obraz klasy w funkcji is Ta definicja nie wymaga, aby Unia klasy to Potęga klasy to Rozszerzona wersja twierdzenia o istnieniu klasy implikuje istnienie tych klas. Aksjomaty zastępowania, sumy i potęgi zbioru sugerują, że kiedy te operacje są stosowane na zbiorach, tworzą zbiory.

Aksjomat zastępowania. Jeśli jest to funkcja i jest zbiorem, a potem The obraz z niedostatecznie , to zestaw.

Brak wymogu w definicji tworzy silniejszy aksjomat zastępowania, który jest używany w poniższym dowodzie.

Twierdzenie ( aksjomat separacji NBG ). Jeśli jest zbiorem i jest podklasą tego, to jest zbiorem. Dowód: Istnienie klasy twierdzenie konstruuje ograniczenie z funkcją tożsamości do : Ponieważ obraz Under jest , aksjomat zastępowania sugeruje, że jest to zestaw. Dowód ten zależy od definicji obrazu, który nie ma wymogu, ponieważ zamiast

Aksjomat unii. Jeśli jest zbiorem, to istnieje zbiór zawierający

Aksjomat zbioru potęgowego. Jeśli jest zbiorem, to istnieje zbiór zawierający

Twierdzenie. Jeśli jest zbiorem, to i są zbiorami. Dowód: Aksjomat związku stanowi, że jest podklasą zbioru , więc aksjomat separacji implikuje jest zbiorem. Podobnie aksjomat zbioru potęgowego stwierdza, że jest podklasą zbioru , więc aksjomat separacji implikuje, że jest zbiorem.

Aksjomat nieskończoności. Istnieje zbiór niepusty takie, że dla wszystkich w , istnieje w taki sposób, że jest podzbiorem .

Aksjomaty nieskończoności i zastępowania dowodzą istnienia zbioru pustego . W omówieniu aksjomatów istnienia klasy udowodniono istnienie klasy pustej . Teraz udowadniamy, że to zestaw. Niech funkcjonować i niech będzie zbiorem określonym przez aksjomat nieskończoności. Zastępując, obraz under , który jest równy , jest zbiorem.

Aksjomat nieskończoności NBG jest implikowany przez aksjomat nieskończoności ZFC : Pierwsza koniunkcja aksjomatu ZFC, , implikuje pierwszą koniunkcję aksjomatu NBG. Druga koniunkcja aksjomatu ZFC, , implikuje drugą koniunkcję aksjomatu NBG, ponieważ Aby udowodnić aksjomat nieskończoności ZFC z aksjomatu nieskończoności NBG wymaga niektórych innych aksjomatów NBG (patrz Słaby aksjomat nieskończoności ).

Aksjomat globalnego wyboru

Koncepcja klasowa pozwala NBG mieć silniejszy aksjomat wyboru niż ZFC. Funkcja wyboru jest funkcją zdefiniowaną na zbiorze niepustych zbiorów tak, że dla wszystkich aksjomatów wyboru ZFC stwierdza się, że istnieje funkcja wyboru dla każdego zbioru niepustych zbiorów. Funkcja globalnego wyboru jest funkcją zdefiniowaną w klasie wszystkich niepustych zbiorów tak, że dla każdego niepustego zbioru Aksjomat globalnego wyboru stwierdza, że ​​istnieje globalna funkcja wyboru. Aksjomat ten zakłada aksjomat ZFC z wyboru, ponieważ dla każdego zestawu z niepustych zbiorów, (The restrykcyjnym od do ) jest funkcją wybór w 1964 roku, William B. Easton udowodnił, że globalny wybór jest silniejsza niż aksjomatu wyboru za pomocą zmuszając skonstruować model, który spełnia aksjomat wyboru i wszystkie aksjomaty NBG z wyjątkiem aksjomatu wyboru globalnego. Aksjomat globalnego wyboru jest równoważny każdej klasie mającej dobre uporządkowanie, podczas gdy aksjomat wyboru ZFC jest równoważny każdemu zbiorowi posiadającemu dobre uporządkowanie.

Aksjomat wyboru globalnego. Istnieje funkcja, która wybiera element z każdego niepustego zestawu.

Historia

patrz podpis
Historia podejść, które doprowadziły do ​​powstania teorii zbiorów NBG

System aksjomatów von Neumanna z 1925 r.

Von Neumann opublikował artykuł wprowadzający na temat swojego systemu aksjomatów w 1925. W 1928 przedstawił szczegółową analizę swojego systemu. Von Neumann oparł swój system aksjomatów na dwóch domenach obiektów pierwotnych : funkcjach i argumentach. Domeny te nakładają się na siebie — obiekty znajdujące się w obu domenach nazywane są funkcjami argumentów. Funkcje odpowiadają klasom w NBG, a funkcje-argumentów odpowiadają zestawom. Prymitywną operacją von Neumanna jest zastosowanie funkcji , oznaczana przez [ ax ] zamiast a ( x ), gdzie a jest funkcją, a x jest argumentem. Ta operacja generuje argument. Von Neumann zdefiniował klasy i zbiory za pomocą funkcji i funkcji argumentów, które przyjmują tylko dwie wartości, A i B . Zdefiniował x  ∈  a jeśli [ ax ] ≠  A .

Na prace von Neumanna nad teorią mnogości wpłynęły artykuły Georga Cantora , aksjomaty Ernsta Zermelo dotyczące teorii mnogości z 1908 r. oraz krytyka teorii mnogości Zermelo z 1922 r., która została podana niezależnie przez Abrahama Fraenkla i Thoralfa Skolema . Zarówno Fraenkel i Skolem wskazał, że aksjomaty Zermelo nie może udowodnić istnienie zbioru { Z 0Z 1Z 2 , ...}, gdzie Z 0 jest zbiorem liczb naturalnych i Z n +1 jest zestaw zasilający z Z n . Następnie wprowadzili aksjomat zastępowania, który gwarantowałby istnienie takich zbiorów. Jednak byli niechętni przyjęciu tego aksjomatu: Fraenkel stwierdził, że „zastąpienie było zbyt silnym aksjomatem dla „ogólnej teorii mnogości”, podczas gdy „Skolem napisał tylko, że „możemy wprowadzić” zastąpienie”.

Von Neumann pracował nad problemami teorii mnogości Zermelo i dostarczył rozwiązania dla niektórych z nich:

  • Teoria liczb porządkowych
    • Problem: Teoria liczb porządkowych Cantora nie może być rozwinięta w teorii mnogości Zermelo, ponieważ brakuje jej aksjomatu zastępowania.
    • Rozwiązanie: Von Neumann odzyskał teorię Cantora, definiując liczby porządkowe za pomocą zbiorów, które są dobrze uporządkowane przez relację ∈, i używając aksjomatu zastępowania do udowodnienia kluczowych twierdzeń o liczbach porządkowych, na przykład każdy dobrze uporządkowany zbiór jest porządkiem izomorficznym z porządkiem. W przeciwieństwie do Fraenkla i Skolema, von Neumann podkreślał, jak ważny jest aksjomat zastępowania dla teorii mnogości: „W rzeczywistości uważam, że żadna teoria liczb porządkowych nie jest w ogóle możliwa bez tego aksjomatu”.
  • Kryterium identyfikujące klasy, które są zbyt duże, aby można je było ustawić
    • Problem: Zermelo nie podało takiego kryterium. Jego teoria zbiorów unika wielkich klas, które prowadzą do paradoksów , ale pomija wiele zbiorów, takich jak wspomniany przez Fraenkla i Skolema.
    • Rozwiązanie: Von Neumann wprowadził kryterium: klasa jest zbyt duża, aby być zbiorem wtedy i tylko wtedy, gdy można ją odwzorować na klasę V wszystkich zbiorów. Von Neumann zdał sobie sprawę, że paradoksów teorii mnogości można uniknąć, nie pozwalając, aby tak duże klasy były członkami żadnej klasy. Łącząc to ograniczenie ze swoim kryterium, uzyskał swój aksjomat ograniczenia rozmiaru : klasa C nie jest członkiem żadnej klasy wtedy i tylko wtedy, gdy C może być odwzorowane na V .
  • Skończona aksjomatyzacja
    • Problem: Zermelo użył nieprecyzyjnego pojęcia „określonej funkcji zdaniowej ” w swoim aksjomacie separacji .
    • Rozwiązania: Skolem wprowadził schemat aksjomatu separacji, który został później użyty w ZFC, a Fraenkel wprowadził równoważne rozwiązanie. Jednak Zermelo odrzucił oba podejścia „zwłaszcza dlatego, że domyślnie zawierają koncepcję liczby naturalnej, która, zdaniem Zermelo, powinna opierać się na teorii mnogości”. Von Neumann unikał schematów aksjomatów , formalizując pojęcie „określonej funkcji zdaniowej” swoimi funkcjami, których konstrukcja wymaga jedynie skończenie wielu aksjomatów. Doprowadziło to do tego, że jego teoria mnogości miała skończenie wiele aksjomatów. W 1961 Richard Montague udowodnił, że ZFC nie może być skończenie zaksjomatyzowane.
  • Aksjomat prawidłowości
    • Problem: Teoria mnogości Zermelo zaczyna się od zbioru pustego i zbioru nieskończonego i iteruje aksjomaty parowania, łączenia, zbioru potęgowego, separacji i wyboru w celu wygenerowania nowych zbiorów. Jednak nie ogranicza zestawów do nich. Na przykład dopuszcza zbiory, które nie są dobrze ugruntowane , takie jak zbiór x spełniający x  ∈  x .
    • Rozwiązania: Fraenkel wprowadził aksjomat wykluczenia tych zbiorów. Von Neumann przeanalizował aksjomat Fraenkla i stwierdził, że nie jest on „precyzyjnie sformułowany”, ale w przybliżeniu powiedziałby: „Oprócz zbiorów… których istnienie jest absolutnie wymagane przez aksjomaty, nie ma dalszych zbiorów”. Von Neumann zaproponował aksjomat regularności jako sposób na wykluczenie zbiorów nieuzasadnionych, ale nie uwzględnił go w swoim systemie aksjomatów. W 1930 Zermelo jako pierwszy opublikował system aksjomatów, który zawierał regularność.

System aksjomatów von Neumanna z 1929 r.

patrz podpis
Jana von Neumanna

W 1929 roku von Neumann opublikował artykuł zawierający aksjomaty prowadzące do NBG. Artykuł ten był motywowany troską o spójność aksjomatu ograniczenia wielkości. Stwierdził, że ten aksjomat „robi dużo, właściwie za dużo”. Oprócz implikowania aksjomatów separacji i zastępowania oraz twierdzenia o dobrym porządku , oznacza to również, że każda klasa, której kardynalność jest mniejsza niż V, jest zbiorem. Von Neumann sądził, że ta ostatnia implikacja wykracza poza kantorowską teorię mnogości i doszedł do wniosku: „Musimy zatem przedyskutować, czy jej spójność [aksjomatu] nie jest nawet bardziej problematyczna niż aksjomatyzacja teorii mnogości, która nie wykracza poza niezbędne ramy kantora”.

Von Neumann rozpoczął badanie spójności, wprowadzając swój system aksjomatów z 1929 r., który zawiera wszystkie aksjomaty jego systemu aksjomatów z 1925 r. z wyjątkiem aksjomatu ograniczenia rozmiaru. Zastąpił ten aksjomat dwoma jego konsekwencjami, aksjomatem zastępowania i aksjomatem wyboru. Aksjomat wyboru von Neumanna mówi: „Każda relacja R ma podklasę, która jest funkcją z tej samej dziedziny co R ”.

Niech S będzie systemem aksjomatów von Neumanna z 1929 roku. Von Neumann przedstawił aksjomatykę S + regularność (który składa się z S i aksjomat regularności), aby wykazać, że jego system 1925 jest zgodny stosunku do S . Udowodnił:

  1. Jeśli S jest niesprzeczne, to S + Regularność jest niesprzeczne.
  2. S + Regularność implikuje aksjomat ograniczenia wielkości. Ponieważ jest to jedyny aksjomat jego 1925 aksjomatyce że S + Regularność nie ma, S + Regularność implikuje wszystkie aksjomaty swojego systemu 1925.

Wyniki te implikują: Jeśli S jest niesprzeczny, to system aksjomatów von Neumanna z 1925 r. jest niesprzeczny. Dowód: Jeśli S jest spójne, to S + Regularność jest spójne (wynik 1). Używając dowodu przez sprzeczność , załóżmy, że system aksjomatów z 1925 r. jest niespójny lub równoważny: system aksjomatów z 1925 r. implikuje sprzeczność. Ponieważ S + Regularność implikuje aksjomaty systemu z 1925 r. (wynik 2), S + Regularność implikuje również sprzeczność. Przeczy to jednak spójności S + Regularność. Dlatego jeśli S jest niesprzeczne, to system aksjomatów von Neumanna z 1925 r. jest niesprzeczny.

Ponieważ S jest jego systemem aksjomatów z 1929 r., system aksjomatów von Neumanna z 1925 r. jest zgodny z jego systemem aksjomatów z 1929 r., który jest bliższy teorii mnogości Cantoriana. Główne różnice między teorią mnogości Cantora a systemem aksjomatów z 1929 roku to klasy i aksjomat wyboru von Neumanna. System aksjomatów S + Regularność został zmodyfikowany przez Bernaysa i Gödla w celu uzyskania równoważnego systemu aksjomatów NBG.

System aksjomatów Bernaysa

Paul Bernays

W 1929 roku Paul Bernays zaczął modyfikować nowy system aksjomatów von Neumanna, przyjmując klasy i zbiory jako prymitywne. Opublikował swoją pracę w serii artykułów ukazujących się od 1937 do 1954. Bernays stwierdził, że:

Celem modyfikacji systemu von Neumanna jest zbliżenie się do struktury pierwotnego systemu Zermelo i jednoczesne wykorzystanie niektórych pojęć teorii mnogości logiki Schrödera i Principia Mathematica, które stały się znane logikom. Jak widać, z tego układu wynika znaczne uproszczenie.

Bernays obsługiwał zbiory i klasy w logice dwojakiego rodzaju i wprowadził dwa prymitywy przynależności: jeden dla przynależności do zbiorów i jeden dla przynależności do klas. Za pomocą tych prymitywów przepisał i uprościł aksjomaty von Neumanna z 1929 roku. Bernays włączył również aksjomat regularności do swojego systemu aksjomatów.

System aksjomatów Gödla (NBG)

patrz podpis
Kurt Gödel, ok. 1930 r . 1926    

W 1931 Bernays wysłał list zawierający swoją teorię mnogości do Kurta Gödla . Gödel uprościł teorię Bernaysa, czyniąc każdy zbiór klasą, co pozwoliło mu na użycie tylko jednego rodzaju i jednego prymitywu przynależności. Osłabił także niektóre aksjomaty Bernaysa i zastąpił aksjomat wyboru von Neumanna równoważnym aksjomatem wyboru globalnego. Gödel wykorzystał swoje aksjomaty w swojej monografii z 1940 r. na temat względnej spójności globalnego wyboru i uogólnionej hipotezy kontinuum.

Podano kilka powodów, dla których Gödel wybrał NBG do swojej monografii:

  • Gödel podał matematyczny powód – globalny wybór NBG daje silniejsze twierdzenie o spójności: „Ta silniejsza forma aksjomatu [wyboru], jeśli jest zgodna z innymi aksjomatami, implikuje oczywiście, że słabsza forma jest również niesprzeczna”.
  • Robert Solovay przypuszczał: „Domyślam się, że [Gödel] chciał uniknąć dyskusji na temat szczegółów technicznych związanych z rozwijaniem podstaw teorii modeli w aksjomatycznej teorii mnogości”.
  • Kenneth Kunen podał powód, dla którego Gödel unikał tej dyskusji: „Istnieje również znacznie bardziej kombinatoryczne podejście do L [ konstruktywnego wszechświata ], opracowane przez ... [Gödel w jego monografii z 1940 r.] w celu wyjaśnienia jego pracy nie- logicy. ... Takie podejście ma tę zaletę, usuwając wszelkie ślady logiki od leczenia L „.
  • Charles Parsons przedstawił filozoficzną przyczynę wyboru Gödla: „Ten pogląd [że 'własność zbioru' jest prymitywem teorii mnogości] może być odzwierciedlony w wyborze przez Gödla teorii ze zmiennymi klasowymi jako ramą dla ... [jego monografia] ”.

Osiągnięcie Gödla wraz ze szczegółami jego prezentacji sprawiły, że NBG będzie się cieszyło rozgłosem przez następne dwie dekady. W 1963 roku Paul Cohen udowodnił swoje dowody niezależności dla ZF za pomocą niektórych narzędzi, które Gödel opracował dla swoich dowodów względnej spójności dla NBG. Później ZFC stało się bardziej popularne niż NBG. Było to spowodowane kilkoma czynnikami, w tym dodatkową pracą wymaganą do obsługi forsowania w NBG, prezentacją Cohena z 1966 roku dotyczącą forsowania, w której wykorzystano ZF, oraz dowodem, że NBG jest konserwatywnym rozszerzeniem ZFC.

NBG, ZFC i MK

NBG nie jest logicznie odpowiednikiem ZFC, ponieważ jego język jest bardziej ekspresyjny: może wypowiadać stwierdzenia dotyczące klas, których nie można sformułować w ZFC. Jednak NBG i ZFC sugerują te same stwierdzenia o zestawach. Dlatego NBG jest konserwatywnym rozszerzeniem ZFC. NBG implikuje twierdzenia, których ZFC nie implikuje, ale ponieważ NBG jest konserwatywnym rozszerzeniem, twierdzenia te muszą obejmować odpowiednie klasy. Na przykład jest to twierdzenie NBG, że globalny aksjomat wyboru implikuje, że właściwa klasa V może być dobrze uporządkowana i że każda właściwa klasa może być umieszczona w korespondencji jeden do jednego z V .

Jedną z konsekwencji konserwatywnego rozszerzenia jest to, że ZFC i NBG są jednakowo spójne . Udowodnienie tego wykorzystuje zasadę eksplozji : ze sprzeczności wszystko można udowodnić. Załóżmy, że ZFC lub NBG są niespójne. Wtedy niespójna teoria implikuje sprzeczne zdania ∅ = ∅ i ∅ ≠ ∅, które są zdaniami o zbiorach. Poprzez konserwatywną własność rozszerzenia, inna teoria również implikuje te stwierdzenia. Dlatego też jest niespójny. Więc chociaż NBG jest bardziej wyrazisty, jest zgodny z ZFC. Ten wynik wraz z dowodem względnej niesprzeczności von Neumanna z 1929 r. implikuje, że jego system aksjomatów z 1925 r. z aksjomatem ograniczenia wielkości jest zgodny z ZFC. To całkowicie rozwiązuje troskę von Neumanna o względną spójność tego potężnego aksjomatu, ponieważ ZFC mieści się w ramach kantora.

Chociaż NBG jest konserwatywnym rozszerzeniem ZFC, twierdzenie może mieć krótszy i bardziej elegancki dowód w NBG niż w ZFC (lub odwrotnie). Przegląd znanych wyników tego rodzaju można znaleźć w Pudlák 1998 .

Teoria mnogości Morse'a-Kelley'a ma schemat aksjomatu rozumienia klas, który obejmuje formuły, których kwantyfikatory obejmują klasy. MK jest silniejszą teorią niż NBG, ponieważ MK dowodzi spójności NBG, podczas gdy drugie twierdzenie Gödla o niezupełności sugeruje, że NBG nie może udowodnić spójności NBG.

Omówienie niektórych kwestii ontologicznych i innych filozoficznych postawionych przez NBG, zwłaszcza w zestawieniu z ZFC i MK, znajduje się w Dodatku C Pottera 2004 .

Modele

ZFC, NBG i MK posiadają modele, które można opisać w kategoriach skumulowanej hierarchii V α i konstruowalnej hierarchii L α . Niech V to liczba nieosiągalna k, niech xV κ i pozwolić std ( X ) oznacza klasę pierwszego rzędu definiowanych podzbiory o X z parametrów. W symbolach gdzie " " oznacza model z dziedziną i relacją , a " " oznacza relację satysfakcji :

Następnie:

  • ( V κ , ∈ ) i ( L κ , ∈ ) są modelami ZFC .
  • ( V κV κ+1 , ∈) jest modelem MK, gdzie V κ składa się ze zbiorów modelu, a V κ+1 z klas modelu. Ponieważ model MK jest modelem NBG, ten model jest również modelem NBG.
  • ( V κ , Def( V κ ), ∈) to model Mendelsona w wersji NBG, który zastępuje aksjomat globalnego wyboru NBG aksjomatem wyboru ZFC. Aksjomaty ZFC są prawdziwe w tym modelu, ponieważ ( V κ , ∈) jest modelem ZFC. W szczególności obowiązuje aksjomat wyboru ZFC, ale globalny wybór NBG może się nie powieść. Aksjomaty NBG dotyczące istnienia klas są prawdziwe w tym modelu, ponieważ klasy, których istnienie stwierdzają, mogą być zdefiniowane przez definicje pierwszego rzędu. Na przykład aksjomat przynależności obowiązuje, ponieważ klasa jest zdefiniowana przez:
  • ( L κ , L κ + , ∈), gdzie κ + jest następcą kardynalnym κ, jest modelem NBG. Aksjomaty istnienia klasy NBG są prawdziwe w ( L κL κ + , ∈). Na przykład aksjomat przynależności obowiązuje, ponieważ klasa jest zdefiniowana przez:
Więc E  ∈ ( L κ ). W swoim dowodzie, że GCH jest prawdziwe w L , Gödel udowodnił, że 𝒫( L κ ) ⊆  L κ + . Zatem E  ∈  L κ + , więc aksjomat przynależności jest prawdziwy w ( L κL κ + , ∈). Podobnie inne aksjomaty istnienia klasowego są prawdziwe. Aksjomat globalnego wyboru jest prawdziwy, ponieważ L κ jest dobrze uporządkowany przez ograniczenie funkcji Gödla (która odwzorowuje klasę liczb porządkowych na zbiory konstruowalne) do liczb porządkowych mniejszych niż κ. Dlatego ( L κL κ + , ∈) jest modelem NBG.

Teoria kategorii

Ontologia NBG zapewnia rusztowanie do mówienia o „dużych obiektach” bez ryzyka paradoksu. Na przykład w niektórych opracowaniach teorii kategoriiduża kategoria ” jest definiowana jako taka, której obiekty i morfizmy tworzą właściwą klasę. Z drugiej strony „mała kategoria” to taka, której obiekty i morfizmy należą do zbioru. W ten sposób możemy mówić o „ kategorii wszystkich zestawów ” lub „ kategorii wszystkich małych kategorii ” bez ryzyka paradoksu, ponieważ NBG obsługuje duże kategorie.

Jednak NBG nie obsługuje „kategorii wszystkich kategorii”, ponieważ duże kategorie byłyby jej członkami, a NBG nie zezwala na członkostwo odpowiednich klas. Rozszerzeniem ontologicznym pozwalającym formalnie mówić o takiej „kategorii” jest konglomerat , czyli zbiór klas. Wtedy „kategoria wszystkich kategorii” jest definiowana przez jej przedmioty: konglomerat wszystkich kategorii; i jego morfizmy: konglomerat wszystkich morfizmów od A do B, gdzie A i B są obiektami. O tym, czy ontologia zawierająca klasy i zbiory jest adekwatna dla teorii kategorii, patrz Muller 2001 .

Uwagi

Bibliografia

Bibliografia

Zewnętrzne linki