Konstruktywna teoria mnogości - Constructive set theory

Konstruktywna teoria mnogości to podejście do konstruktywizmu matematycznego zgodne z programem aksjomatycznej teorii mnogości . Zwykle używa się tego samego języka pierwszego rzędu z „ ” i „ ” klasycznej teorii mnogości, więc nie należy tego mylić z podejściem typu konstruktywnego . Z drugiej strony, niektóre konstruktywne teorie są rzeczywiście motywowane ich interpretowalnością w teoriach typów .

Oprócz odrzucenia Prawo wyłączonego środka ( ), konstruktywne zestaw teorie często wymagają niektóre logika kwantyfikatorów w swoich aksjomatów być ograniczony , motywowane wyników przywiązane do impredicativity .

Wstęp

Perspektywy

Logika omawianych tu teorii mnogości jest konstruktywna , ponieważ odrzuca , tj. alternatywa automatycznie obowiązuje dla wszystkich zdań. Wymaga to odrzucenia silnych zasad wyboru i przeredagowania niektórych standardowych aksjomatów. Na przykład Aksjomat wyboru implikuje formuły w przyjętym schemacie separacji na podstawie twierdzenia Diaconescu . Podobne wyniki dotyczą aksjomatu regularności w jego standardowej formie. Z reguły, aby udowodnić konkretną alternatywę , trzeba albo albo trzeba udowodnić. W takim przypadku mówi się, że alternatywa jest rozstrzygalna. Z kolei teorie konstruktywne zwykle nie dopuszczają wielu klasycznych dowodów własności, które są np . nierozstrzygalne obliczeniowo dowodem . W przeciwieństwie do bardziej konserwatywnej logiki minimalnej, logika leżąca u jej podstaw umożliwia eliminację podwójnej negacji dla rozstrzygalnych predykatów, a sformułowania twierdzeń dotyczące konstrukcji skończonych zwykle nie różnią się od swoich klasycznych odpowiedników.

Warto zauważyć, że ograniczenie do logiki konstruktywnej prowadzi do bardziej rygorystycznych wymagań dotyczących tego, które charakterystyki zbioru obejmujące kolekcje nieograniczone stanowią funkcję (matematyczną, a więc zawsze implikującą totalną ). Dzieje się tak często, ponieważ predykat w definicji przyszłej uwzględniającej wielkość liter może nie być rozstrzygalny. W porównaniu z klasycznym odpowiednikiem, generalnie mniej prawdopodobne jest udowodnienie istnienia relacji, których nie można zrealizować. Wpływa to również na dowodliwość twierdzeń o rzędach całkowitych, takich jak wszystkie liczby porządkowe , wyrażonych przez prawdę i negację terminów w alternatywie definiującej porządek . A to z kolei wpływa na teoretyczną siłę dowodu określoną w analizie porządkowej .

To powiedziawszy, konstruktywne teorie matematyczne zwykle udowadniają klasycznie równoważne przeformułowania klasycznych twierdzeń. Na przykład w analizie konstruktywnej nie można udowodnić twierdzenia o wartości pośredniej w jego podręcznikowym sformułowaniu, ale można dowieść twierdzeń o treści algorytmicznej, które, jak tylko się założy, są jednocześnie klasycznym odpowiednikiem twierdzenia klasycznego. Różnica polega na tym, że trudniej jest znaleźć konstruktywne dowody.

W modelach

Wiele teorii badanych w konstruktywnej teorii mnogości to jedynie ograniczenia teorii mnogości Zermelo-Fraenkla ( ) w odniesieniu do ich aksjomatu, jak również leżącej u ich podstaw logiki. Takie teorie można następnie interpretować w dowolnym modelu . Jeśli chodzi o konstruktywne realizacje, istnieje teoria realizowalności, a konstruktywna teoria Aczela Zermelo-Fraenkel ( ) została zinterpretowana w teoriach typu Martina-Löfa , jak opisano poniżej. W ten sposób twierdzenia teorii mnogości, które można udowodnić i słabsze teorie, są kandydatami do realizacji komputerowej. Niedawno wprowadzono modele presheaf dla konstruktywnych teorii mnogości . Są one analogiczne do niepublikowanych modeli Presheafa dla intuicjonistycznej teorii mnogości opracowanych przez Danę Scott w latach 80. XX wieku.

Przegląd

Temat konstruktywnej teorii mnogości (często „ ”) zapoczątkowany przez prace Johna Myhilla nad teorią zwaną także teorią kilku rodzajów i ograniczonej kwantyfikacji, mającą na celu zapewnienie formalnych podstaw dla programu matematyki konstruktywnej Erretta Bishopa . Poniżej znajduje się sekwencja teorii w tym samym języku co , prowadząca do dobrze przestudiowanego przez Petera Aczela , i dalej. charakteryzuje się również dwiema cechami obecnymi również w teorii Myhilla: Z jednej strony wykorzystuje Predykatywną Separację zamiast pełnego, nieograniczonego schematu Separacji, zob. też Hierarchia Lévy'ego . Ograniczenie może być traktowane jako właściwość syntaktyczna lub, alternatywnie, teorie mogą być konserwatywnie rozszerzone o predykat wyższego ograniczenia i jego aksjomaty. Po drugie, przesadny aksjomat Powerset jest odrzucany, generalnie na rzecz pokrewnych, ale słabszych aksjomatów. Silna forma jest bardzo niedbale używana w klasycznej topologii ogólnej . Dodanie do teorii jeszcze słabszej niż odzyskiwanie , jak opisano poniżej. System, który stał się znany jako intuicjonistyczna teoria mnogości Zermelo-Fraenkla ( ), jest silną teorią mnogości bez . Jest podobny do , ale mniej konserwatywny lub predykatywny . Oznaczona teoria jest konstruktywną wersją klasycznej teorii mnogości Kripkego–Platka, w której ograniczony jest nawet aksjomat kolekcji.

Podteorie ZF

Notacja

Poniżej greckie oznaczają zmienną predykatu w schematach aksjomatów i użycie lub dla poszczególnych predykatów. Unikalne istnienie np . oznacza . Kwantyfikatory wykraczają poza zestaw, a te są oznaczane małymi literami.

Jak to często bywa w badaniach nad teoriami zbiorów , używa się notacji konstruktora zbiorów dla klas , które w większości kontekstów nie są częścią języka obiektowego, ale służą do zwięzłej dyskusji. W szczególności można wprowadzić deklaracje notacji odpowiedniej klasy poprzez " ", w celu wyrażenia jako . Do wprowadzenia tej samej klasy można użyć logicznie równoważnych predykatów. Pisze się również jako skrót od .

Jak to zwykle, można skrócić przez i wyrażenia żądania podklasy , tj , przez .

Jak na nieruchomość , banalnie . I tak wynika z tego .

Wspólne aksjomaty

Punkt wyjścia aksjomatów, które praktycznie zawsze uważane są za niekontrowersyjne i stanowią część wszystkich teorii rozważanych w tym artykule.

Oznaczmy przez stwierdzenie wyrażające, że dwie klasy mają dokładnie te same elementy, czyli , lub równoważnie .

Poniższy aksjomat daje środki do udowodnienia równości " " dwóch zbiorów , tak że poprzez podstawienie każdy orzecznik około przekłada się na jeden z .

Rozszerzalność

Dzięki logicznym własnościom równości, odwrotny kierunek utrzymuje się automatycznie.

W konstruktywny interpretacji elementy podklasy z może wyposażone w więcej informacji niż te , w tym sensie, że jest w stanie ocenić, jest w stanie ocenić . I (chyba, że ​​cała alternatywa wynika z aksjomatów) w interpretacji Brouwera–Heytinga–Kolmogorova oznacza to, że udowodniono ją lub ją odrzuciłam. Ponieważ może nie być rozstrzygalne dla wszystkich elementów w , te dwie klasy muszą być a priori rozróżnione.

Rozważmy właściwość, która sprawdza się dla wszystkich elementów zbioru , tak więc i załóżmy, że klasa po lewej stronie jest zbiorem. Zauważ, że nawet jeśli ten zbiór po lewej stronie nieformalnie wiąże się również z informacją istotną dla dowodu dotyczącą ważności dla wszystkich elementów, aksjomat rozszerzalności postuluje, że w naszej teorii mnogości zbiór po lewej stronie jest oceniany jako równy jeden po prawej stronie.

Współczesne teorie typów mogą zamiast tego zmierzać do zdefiniowania żądanej równoważności " " w kategoriach funkcji, patrz np . równoważność typów . Pokrewna koncepcja ekstensjonalności funkcji często nie jest przyjmowana w teorii typów.

Inne ramy dla konstruktywnej matematyki mogą zamiast tego wymagać szczególnej zasady równości lub oddzielenia dla elementów każdego omawianego zestawu . Nawet wtedy powyższą definicję można wykorzystać do scharakteryzowania równości podzbiorów i .

Dwa inne podstawowe aksjomaty są następujące. Po pierwsze,

Łączenie w pary

mówiąc, że dla dowolnych dwóch zestawów i , istnieje co najmniej jeden zestaw , który zawiera przynajmniej te dwa zestawy ( ).

I wtedy,

Unia

mówiąc, że każdy zestaw , istnieje co najmniej jeden zestaw , który zawiera wszystkie elementy , z członków „s .

Te dwa aksjomaty mogą być również sformułowane mocniej w terminach „ ”, np. w kontekście z Separacją, nie jest to konieczne.

Razem te dwa aksjomaty implikują istnienie unii binarnej dwóch klas i kiedy zostały ustalone jako zbiory, co oznacza się lub . Zdefiniuj notację klasy dla elementów skończonych za pomocą alternatyw, np. says , i zdefiniuj następcę jako . Swoistym połączeniem parowania i zjednoczenia, aksjomatem łatwiej powiązanym z następcą jest aksjomat adjunkcji . Jest to istotne dla standardowego modelowania poszczególnych liczb porządkowych Neumanna . Ten aksjomat również byłby łatwo zaakceptowany, ale nie jest istotny w kontekście silniejszych aksjomatów poniżej. Oznaczmy za pomocą standardowego modelu zamówionej pary .

Właściwość, która jest fałszem dla dowolnego zestawu, odpowiada pustej klasie, oznaczonej przez lub zero, 0. To, że jest to zbiór łatwo wynika z innych aksjomatów, takich jak Aksjomat nieskończoności poniżej. Ale jeśli np. ktoś jest wyraźnie zainteresowany wykluczeniem ze swoich badań zbiorów nieskończonych, to może w tym miejscu przyjąć aksjomat zbioru pustego

BCST

Poniżej posługujemy się schematami aksjomatów , czyli aksjomatami dla pewnej kolekcji predykatów. Należy zauważyć, że niektóre z podanych schematów aksjomatów są często przedstawiane również z ustawionymi parametrami , tj. wariantami z dodatkowymi uniwersalnymi domknięciami, tak że 's mogą zależeć od parametrów.

Podstawowa konstruktywna teoria mnogości składa się z kilku aksjomatów, również będących częścią standardowej teorii mnogości, z wyjątkiem osłabienia aksjomatu separacji . Poza trzema powyższymi aksjomatami przyjmuje

Schemat aksjomatu separacji predykatywnej : Dla dowolnego predykatu ograniczonego z niewolnym w nim,

Aksjomat sprowadza się do postulowania istnienia zbioru otrzymanego przez przecięcie dowolnego zbioru i dowolnej klasy opisanej predykatywnie . Gdy orzeczenie jest traktowana jako dla okazały się zestaw, otrzymuje binarny przecięcie zbiorów i zapisów .

Schemat jest również nazywany Bounded Separation, tak jak w Separation tylko dla kwantyfikatorów set- bounded . To schemat aksjomatu odwołuje się do składniowych aspektów predykatów. Preparaty te Ograniczone są również oznaczone w zbiorze teoretycznej Lévy hierarchii, w sposób analogiczny do opisanego w hierarchii arytmetycznej . (Należy jednak zauważyć, że klasyfikacja arytmetyczna jest czasami wyrażana nie syntaktycznie, ale w kategoriach podklas naturalnych. Ponadto dolny poziom ma kilka wspólnych definicji, niektóre nie pozwalają na użycie niektórych funkcji całkowitych. Rozróżnienie nie jest istotne na poziomie lub wyżej.) Ograniczeniem w aksjomie jest również bramkowanie nieprecyzyjnych definicji: istnienie w najlepszym razie nie powinno być deklarowane dla obiektów, których nie można jednoznacznie opisać, lub których definicja dotyczy samych siebie lub odniesienia do właściwej klasy, na przykład gdy właściwość, która ma być sprawdzona, obejmuje uniwersalny kwantyfikator. Tak więc w konstruktywnej teorii bez aksjomatu zbioru potęgi nie należy oczekiwać klasy zdefiniowanej jako

tj

być zbiorem, gdzie oznacza jakiś orzeczenie dwuargumentowe. Zauważ, że jeśli ta podklasa jest zbiorem, który można udowodnić, to zdefiniowany w ten sposób termin również znajduje się w nieograniczonym zakresie terminu zmienna i spełnia predykat w nawiasach , używany do definiowania samego siebie. Podczas gdy separacja predykatywna prowadzi do mniejszej liczby określonych definicji klas będących zbiorami, należy podkreślić, że wiele definicji klas, które są klasycznie równoważne, nie jest takimi, gdy ograniczamy się do logiki konstruktywnej. W ten sposób otrzymuje się szerszą teorię, konstruktywnie. Ze względu na potencjalną nierozstrzygalność predykatów ogólnych pojęcie podklasy jest bardziej rozbudowane w konstruktywnych teoriach mnogości niż w klasycznych.

Jak zauważono, z Separacji i istnienia dowolnego zbioru (np. Nieskończoności poniżej) i predykatu, który jest fałszywy dla dowolnego zbioru wynikać będzie istnienie zbioru pustego.

Na mocy czysto logicznego twierdzenia , konstrukcja Russela pokazuje, że sama predykatywna separacja implikuje, że . W szczególności nie istnieje żaden uniwersalny zbiór .

W tym konserwatywnym kontekście schemat Bounded Separation jest w rzeczywistości odpowiednikiem Empty Set plus istnienie przecięcia binarnego dla dowolnych dwóch zestawów. Ten ostatni wariant aksjomatyzacji nie wykorzystuje schematu. Ponieważ podtypowanie nie jest niezbędną cechą teorii typów konstruktywnych, można powiedzieć, że konstruktywna teoria mnogości różni się od tej struktury.

Następnie rozważ

Schemat aksjomatu zamiany : dla dowolnego predykatu ,

Jest to przyznanie istnienia, jako zbiorów, zakresu predykatów funkcyj- nych, uzyskanych za pośrednictwem ich dziedzin.

W przypadku schematu zastępczego teoria ta dowodzi, że klasy równoważności lub sumy indeksowane są zbiorami. W szczególności zbiorem jest iloczyn kartezjański , zawierający wszystkie pary elementów dwóch zbiorów.

Zastąpienie i aksjomat indukcji zbiorów (przedstawiony poniżej) wystarczają do konstruktywnej aksjomatyzacji dziedzicznie skończonych zbiorów i ta teoria jest również badana bez nieskończoności. Dla porównania rozważmy bardzo słabą klasyczną teorię zwaną ogólną teorią mnogości, która interpretuje klasę liczb naturalnych i ich arytmetykę poprzez tylko Rozszerzalność, Adiunkcję i pełną Separację.

W , Zastąpienie jest przede wszystkim ważne dla udowodnienia istnienia zbiorów wysokiej rangi , a mianowicie poprzez przypadki schematu aksjomatu, gdzie odnosi się stosunkowo mały zbiór do większych, .

Konstruktywne teorie mnogości często mają schemat aksjomatu zastępowania, czasami ograniczony do formuł ograniczonych. Jednakże, gdy inne aksjomaty są odrzucane, schemat ten jest często wzmacniany - nie poza , ale tylko po to, aby odzyskać trochę siły dowodliwości.

Zastąpienie może być postrzegane jako forma zrozumienia. Tylko przy założeniu, że zastąpienie oznacza już pełną separację.

ECST

Oznaczmy właściwością indukcyjną, np . . W odniesieniu do predykatu podrzędnego pod klasą, byłoby to tłumaczone jako . Tutaj oznacza ogólną zmienną zestawu. Napisz do . Zdefiniuj klasę .

W przypadku pewnego stałego predykatu instrukcja wyraża, że jest to najmniejszy zestaw spośród wszystkich zestawów, dla których jest prawdziwe. Elementarna konstruktywna teoria mnogości ma aksjomat zarówno

Silna nieskończoność

Druga uniwersalnie skwantyfikowana koniunkcja wyraża indukcję matematyczną dla wszystkich we wszechświecie dyskursu, tj. dla zbiorów, względnie. dla predykatów, jeśli rzeczywiście definiują zbiory . W ten sposób zasady omówione w tej sekcji dają środki do udowodnienia, że ​​niektóre predykaty obowiązują przynajmniej dla wszystkich elementów . Należy mieć świadomość, że nawet dość mocny aksjomat pełnej indukcji matematycznej (indukcja dla dowolnego predykatu, omówiona poniżej) może być również przyjęty i stosowany bez postulowania, że tworzy zbiór.

Można sformułować słabe formy aksjomatów nieskończoności, wszystkie postulujące istnienie zbioru o wspólnych własnościach liczb naturalnych. Wtedy pełna Separacja może być użyta do uzyskania „rzadkiego” takiego zbioru, zbioru liczb naturalnych. W kontekście skądinąd słabszych systemów aksjomatów, aksjomat nieskończoności powinien zostać wzmocniony tak, aby sam w sobie sugerował istnienie takiego rzadkiego zbioru. Jedna słabsza forma Infinity brzmi

który można również napisać bardziej zwięźle za pomocą . Zbiór postulowany w ten sposób do istnienia jest ogólnie oznaczany przez najmniejszą nieskończoną liczbę porządkową von Neumanna . W przypadku elementów tego zestawu roszczenie jest rozstrzygalne.

Dzięki temu dowodzi indukcji dla wszystkich predykatów podanych przez ograniczone formuły. Dwa z pięciu aksjomatów Peano dotyczące zera i jeden dotyczący zamknięcia w odniesieniu do wynikają dość bezpośrednio z aksjomatów nieskończoności. Wreszcie można udowodnić, że jest to operacja iniekcyjna.

Liczby naturalne są rozróżnialne, co oznacza, że ​​ich równość (a tym samym nierówność) jest rozstrzygalna. Podstawowy porządek jest uchwycony przez członkostwo w tym modelu. Ze względu na standardową notację oznaczmy początkowy segment liczb naturalnych, dla dowolnego , w tym zbioru pustego.

Funkcje

Oczywiście logiczne znaczenie twierdzeń o istnieniu jest przedmiotem zainteresowania logiki intuicjonistycznej. Tutaj skupiamy się na całkowitych relacjach .

Rachunek dowodowy, w konstruktywnych ramach matematycznych, zdań takich jak

mogą być skonfigurowane w postaci programów na reprezentowanych domenach i ewentualnie muszą być świadkami roszczenia. Należy to rozumieć w sensie, nieformalnie mówiąc, , gdzie oznacza wartość programu, jak wspomniano, ale to prowadzi do kwestii teorii realizowalności . Dla mocniejszego kontekstu, jeśli i kiedy ta propozycja jest słuszna, to domaganie się, aby zawsze było to możliwe z realizowaną przez jakąś totalnie rekurencyjną funkcję, jest możliwym postulatem tezy Kościoła przyjętym w konsekwencji ściśle nieklasycznym rosyjskim konstruktywizmem . W poprzednim akapicie „funkcję” należy rozumieć w sensie obliczeniowym teorii rekurencji – na tę okazjonalną niejednoznaczność należy również zwrócić uwagę poniżej.

W związku z tym rozważmy arytmetykę Robinsona , która jest klasyczną teorią arytmetyczną, która zastępuje twierdzenie o istnieniu liczby poprzedników pełnym matematycznym schematem indukcji . Jest to twierdzenie, że teoria ta reprezentuje dokładnie funkcje rekurencyjne w sensie definiowania predykatów, które są dowodowo całkowitymi relacjami funkcjonalnymi ,

.

Teraz w obecnym podejściu teoretycznym zbioru zdefiniuj własność obejmującą nawiasy aplikacyjne funkcji , jak i mów o funkcji, gdy można ją udowodnić

,

tj

,

co w szczególności obejmuje kwantyfikator egzystencjalny. To, czy podklasę można uznać za funkcję, będzie zależeć od siły teorii, to znaczy od przyjętych aksjomatów.

Warto zauważyć, że klasa ogólna może spełniać powyższy predykat bez bycia podklasą produktu , tj. właściwość wyraża nie więcej lub mniej niż funkcjonalność wrt danych wejściowych z . Jeśli domena i codomena są ustawione, to powyższy predykat obejmuje tylko ograniczone kwantyfikatory. Należy zachować ostrożność z nomenklaturą „funkcja”, która jest używana w większości struktur matematycznych, również dlatego, że niektóre wiążą sam termin funkcji z konkretną kodziedziną. Zdefiniowano również warianty definicji predykatu funkcjonalnego wykorzystujące relacje odległościowe na setoidach .

Niech (również napisane ) oznacza klasę takich funkcji zbioru. Posługując się standardową terminologią klasową, można swobodnie korzystać z funkcji, ponieważ ich domena jest zbiorem. Funkcje jako całość zostaną ustawione, jeśli jest to ich domena. Gdy funkcje są rozumiane jako po prostu wykresy funkcji, jak powyżej, propozycja przynależności jest również napisana . Poniżej mogą pisać na ze względu na odróżnienie go od porządkowej potęgowania.

Separacja pozwala na użycie wyciętych podzbiorów produktów , przynajmniej jeśli są one opisane w sposób ograniczony. Napisz do . Biorąc pod uwagę , jeden jest teraz prowadzony do rozumowania o klasach takich jak

Do takich klas należą funkcje charakterystyczne o wartościach logicznych . Należy jednak mieć świadomość, że generalnie może nie być rozstrzygalne . Innymi słowy, przy braku jakichkolwiek niekonstruktywnych aksjomatów, alternatywa może nie być dowodowa, ponieważ wymaga się wyraźnego dowodu obu alternatyw. Kiedy

nie da się zaobserwować dla wszystkich lub nie dowiedziono wyjątkowości terminu , to nie można konstruktywnie oceniać rozumianego zbioru jako funkcjonalnego.

Dla i wszelkie naturalne , mają

.

Tak więc w klasycznej teorii mnogości, gdzie zdania w definicji są rozstrzygalne, podobnie jak przynależność do podklas. Jeśli zbiór nie jest skończony, sukcesywne „wyliczanie” wszystkich liczb przez po prostu pominięcie tych z klasycznie stanowi rosnący ciąg surjekcyjny . Tam można uzyskać bijective funkcji . W ten sposób klasyczna klasa funkcji jest bogata w udowodnione, ponieważ zawiera również obiekty, które wykraczają poza to, co wiemy, że są efektywnie obliczalne lub programowo listowalne w praktyce.

W przeciwieństwie do tego, dla odniesienia, w teorii obliczalności , że obliczalnymi zestawy są zakresy nie malejący funkcji (na rekurencyjnym znaczeniu), na poziomie części arytmetycznej hierarchii , a nie wyżej. Decydowanie o predykacie na tym poziomie sprowadza się do rozwiązania zadania polegającego na ostatecznym znalezieniu certyfikatu, który potwierdza lub odrzuca członkostwo. Ponieważ nie każdy predykat jest przeliczalnie rozstrzygalny, sama teoria nie będzie twierdzić (udowodnić), że wszystkie nieskończone są zakresem jakiejś funkcji bijective z dziedziną .

Być skończonym oznacza, że ​​naturalna ma funkcję bijektywną. Być podskończonym oznacza być podzbiorem zbioru skończonego. Twierdzenie, że bycie zbiorem skończonym jest równoważne byciu podskończonym, jest równoważne .

Jednak ze względu na zgodność z , rozwinięcie w tej sekcji zawsze pozwala na interpretację „funkcji na ” jako obiektu niekoniecznie podanego jako sekwencja prawnopodobna . Zastosowania można znaleźć w powszechnych modelach twierdzeń o prawdopodobieństwie, np. stwierdzenia zawierające pojęcie „otrzymania” niekończącej się losowej sekwencji rzutów monetą.

Wybór

  • Aksjomat wyboru policzalnego : Jeśli , można utworzyć zbiór relacji jeden-do-wielu . Aksjomat policzalnego wyboru zapewniałby, że kiedykolwiek można utworzyć funkcję odwzorowującą każdą liczbę na unikalną wartość. Policzalny wybór może być również dodatkowo osłabiony, np. przez ograniczenie możliwych liczności zbiorów w zakresie , lub przez ograniczenie zaangażowanej definicji do ich miejsca w hierarchiach składniowych.
  • Zrelatywizowany wybór zależny: Silniejsza zrelatywizowana zasada wyboru zależnego jest jej wariantem - schematem obejmującym dodatkową zmienną predykatową. Przyjmując to za tylko ograniczone formułach teoria już dowodzi - indukcję , omówiono poniżej.
  • Aksjomat wyboru : Aksjomat wyboru dotyczący funkcji w dziedzinach ogólnych. Oznacza to zależny wybór.

Aby podkreślić siłę pełnego wyboru i jego stosunek do spraw Intencjonalność należy rozważyć klas subfinite

Tu i są tak przypadkowe, jak predykaty zawarte w ich definicji. Przyjmijmy teraz kontekst, w którym zostały ustanowione, aby być zestawami, tak też jest. Tutaj Aksjomat wyboru zapewniłby istnienie mapy z rozróżnialnymi elementami. To teraz faktycznie oznacza, że . Zatem twierdzenie o istnieniu ogólnych funkcji wyboru jest niekonstruktywne. Aby lepiej zrozumieć to zjawisko, należy wziąć pod uwagę przypadki implikacji logicznych, takich jak , i tak dalej. Różnica między dyskretną kodziedziną niektórych liczb naturalnych a dziedziną polega na tym, że a priori niewiele wiadomo o tych ostatnich. Jest tak, że i , niezależnie od , być może pretendentem do funkcji wyboru. Ale w przypadku , jak wynika z dowodliwości z , mamy do czynienia z ekstensjonalnie tylko jedną możliwą funkcją wejściową do funkcji wyboru, teraz z tylko funkcjami wyboru mogą być lub . Zatem rozważając przypisanie funkcjonalne , to bezwarunkowe deklarowanie nie byłoby spójne. Wybór może nie być przyjęty w skądinąd silnej teorii mnogości, ponieważ samo twierdzenie o istnieniu funkcji nie realizuje określonej funkcji. Rozumienie podklas (używane do oddzielania i od , tj. ich definiowania) wiąże związane z nimi predykaty z ustalaniem równości, w opisany sposób, a to odnosi się do informacji o funkcjach.

Rozwój konstruktywny często przebiega w sposób agnostyczny wobec omawianych zasad wyboru.

Arytmetyka

Założenia niezbędne do uzyskania teorii arytmetyki są dokładnie badane w teorii dowodu . Dla kontekstu, tutaj paragraf na temat klasyfikacji w nich zawartych: Klasyczne teorie zaczynające się od arytmetyki ograniczonej przyjmują różne konserwatywne schematy indukcyjne i mogą dodawać symbole dla poszczególnych funkcji, prowadząc do teorii między arytmetykami Robinsona i Peano . Większość takich teorii jest jednak stosunkowo słaba, jeśli chodzi o dowód całości dla niektórych szybciej rozwijających się funkcji . Niektóre z najbardziej podstawowych przykładów obejmują arytmetykę funkcji elementarnych , z teoretyczną liczbą porządkową dowodu (przynajmniej nie do udowodnienia rekurencyjne uporządkowanie ) . ma liczbę porządkową , co oznacza, że ​​teoria pozwala zakodować liczby porządkowe słabszych (w tym sensie analizy porządkowej) teorii (powiedzmy , w terminach teorii mnogości) jako rekurencyjną relację tylko na naturalnych, . Schemat -Indukcja, jak na przykład wywnioskować z zrelatywizowany wybór zależny, środków wprowadzających do tych podklas kasowniki obliczeniowy przez skończoną wyszukiwania z niezwiązanego (Finite) wykonywania. Schemat jest również odpowiednikiem schematu -indukcji. Stosunkowo słaba klasyczna arytmetyka pierwszego rzędu, która przyjmuje ten schemat, jest oznaczona . -Indukcja również przyjąć klasycznego drugiego rzędu odwrotnej matematyczny systemu bazowego . Ta teoria drugiego rzędu jest -konserwatywna w stosunku do prymitywnej arytmetyki rekurencyjnej , więc dowodzi, że wszystkie prymitywne funkcje rekurencyjne są sumą. Wszystkie te ostatnie wymienione teorie arytmetyczne mają liczbę porządkową . Wspomniana arytmetyka wyższego rzędu jest istotnym punktem odniesienia w tej dyskusji, ponieważ jej język nie tylko wyraża zbiory arytmetyczne , podczas gdy wszystkie zbiory liczb naturalnych, których istnienie dowodzi teoria, są tylko zbiorami obliczalnymi .

To powiedziawszy, teoria mnogości w rzeczywistości nawet nie interpretuje pełnej pierwotnej rekurencji. Rzeczywiście, pomimo posiadania aksjomatu zastępowania, teoria nie dowodzi, że funkcja dodawania jest funkcją zbioru. Z drugiej strony, dla każdego zbioru w tej teorii można udowodnić wiele stwierdzeń (w przeciwieństwie do wyrażeń z uniwersalnym kwantyfikatorem, jak np. z zasadą indukcji), a obiekty zainteresowania matematycznego można wykorzystać na poziomie klasy na poziomie klasy. na podstawie indywidualnej. Jako takie, aksjomaty wymienione do tej pory wystarczą jako podstawowa teoria pracy dla dużej części podstawowej matematyki. Wychodząc poza arytmetykę, należy dodać aksjomat dający definicję funkcji zbioru poprzez funkcje zbioru w kroku iteracji. Niezbędny jest zestaw teoretyczny odpowiednik obiektu liczb naturalnych . To z kolei umożliwia interpretację arytmetyki Heytinga , . Dzięki temu można również zdefiniować arytmetykę liczb wymiernych i udowodnić jej własności, takie jak unikalność i przeliczalność. Teoria mnogości z tym udowodni również, że dla dowolnych naturalnych i , przestrzenie funkcyjne

są zestawy.

Odwrotnie, dowód na istnienie poszukiwanej zasady iteracji może opierać się na zbiorze funkcji, które chciałoby się zapisać, a istnienie tego wynika z założenia, że ​​poszczególne przestrzenie funkcyjne na skończonych dziedzinach w zbiory same tworzą zbiory. Ta uwaga powinna motywować przyjęcie aksjomatu o bardziej utrwalonym zabarwieniu teoretycznym, zamiast bezpośredniego wbudowywania zasad arytmetycznych w naszą teorię. Zasada iteracji uzyskana za pomocą kolejnego, bardziej ustalonego aksjomatu teoretycznego, nadal jednak nie dowodzi pełnego matematycznego schematu indukcji .

Potęgowanie

Osłabiona forma schematu Separacji została już przyjęta, a więcej standardowych aksjomatów zostanie osłabionych na rzecz bardziej predykatywnej i konstruktywnej teorii. Pierwszym z nich jest aksjomat Powerset , który w efekcie został przyjęty dla rozstrzygalnych podzbiorów teorii.

Charakterystyka klasy wszystkich podzbiorów zbioru obejmuje nieograniczoną uniwersalną kwantyfikację, a mianowicie . Zostało to tutaj zdefiniowane w kategoriach predykatu członkostwa powyżej. Oświadczenie sama jest . Tak więc w ramach matematycznej teorii mnogości klasa potęgi jest definiowana nie w konstrukcji oddolnej z jej elementów składowych (jak algorytm na liście, czyli np. map ), ale poprzez rozumienie wszystkich zbiorów.

Bogactwo klasy potęgowej w teorii bez wykluczonego środka można najlepiej zrozumieć, rozpatrując małe klasycznie skończone zbiory. Dla dowolnej formuły klasa jest równa 0, gdy można ją odrzucić, a 1, gdy można ją udowodnić, ale może też nie być w ogóle rozstrzygalna. W tym ujęciu klasa potęgowa singletona , tj. klasa , lub sugestywnie " " i zwykle oznaczana przez , nazywana jest algebrą wartości logicznych. W -valued funkcji na zbiorze wtłaczają a więc odpowiadają jego rozstrzygalnych podzbiorów.

Więc teraz rozważmy aksjomat .

Potęgowanie

Sformułowanie tutaj używa wygodnej notacji dla przestrzeni funkcyjnych. W przeciwnym razie aksjomat jest dłuższy i obejmuje kwantyfikator ograniczony przez predykat funkcji całkowitej. Mówiąc słownie, aksjomat mówi, że przy danych dwóch zbiorach klasa wszystkich funkcji jest w rzeczywistości również zbiorem. Jest to z pewnością wymagane, na przykład, aby sformalizować mapę obiektów wewnętrznego funkcji hom, takiego jak . Zastosowanie aksjomatów potęgowania wynika z faktu, że przestrzenie funkcyjne będące zbiorami oznaczają kwantyfikację nad ich funkcjami jest pojęciem ograniczonym, umożliwiającym użycie Separacji. Ma to godne uwagi implikacje: przyjęcie go oznacza, że ​​kwantyfikacja po elementach pewnych klas funkcji staje się pojęciem ograniczonym, także wtedy, gdy przestrzenie funkcji są nawet klasycznie niepoliczalne . Np. zbiór wszystkich funkcji , tj. zbiór punktów leżących u podstaw przestrzeni Cantora , jest niepoliczalny według argumentu przekątnego Cantora i można go co najwyżej przyjąć za przeliczalny . (W tej sekcji zaczniemy używać symbolu półpierścienia liczb naturalnych w wyrażeniach takich jak lub pisać tylko po to, aby uniknąć połączenia liczby kardynalnej z potęgą porządkową.)

Teoria mnogości z potęgą dowodzi teraz również istnienia dowolnej pierwotnej funkcji rekurencyjnej na naturalnych , jako funkcji mnogości w zbiorze . W związku z tym uzyskaj liczbę porządkową -wykładniczą , którą można scharakteryzować jako . Mówiąc bardziej ogólnie, Potęgowanie dowodzi, że suma wszystkich skończonych sekwencji w zbiorze policzalnym jest zbiorem policzalnym. I rzeczywiście, sumy zakresów dowolnej rodziny przeliczalnych funkcji liczących są policzalne.

Jeśli chodzi o zrozumienie, teoria dowodzi teraz, że zbiór wszystkich policzalnych podzbiorów dowolnego zbioru (zbiór jest podklasą klasy potęgowej) jest zbiorem. Również zasada dziura gołąb może być udowodnione.

Wracając do pierwotnego rozważania na temat klas potęgowych: Zakładając, że wszystkie formuły są rozstrzygalne, tj. zakładając , można pokazać nie tylko, że staje się to zbiorem, ale bardziej konkretnie, że jest to ten dwuelementowy zbiór. Zakładając dla formuł ograniczonych, Separacja pozwala wykazać, że każda klasa potęgowa jest zbiorem. Alternatywnie, pełny Powerset jest równoważny jedynie założeniu, że klasa wszystkich podzbiorów tworzy zbiór. Pełna separacja jest równoważna założeniu, że każda pojedyncza podklasa jest zbiorem.

Pojęcia teoretyczne kategorii i typów

Tak więc w tym kontekście z potęgowaniem przestrzenie funkcyjne są bardziej dostępne niż klasy podzbiorów, tak jak w przypadku obiektów wykładniczych względnie. podobiekty w teorii kategorii. W kategoriach teoretycznych , teoria zasadniczo odpowiada konstruktywnie dobrze ukierunkowanym kartezjańskim domkniętym pre toposom Heytinga z (za każdym razem, gdy przyjmuje się nieskończoność) obiektem liczb naturalnych . Istnienie powerset jest tym, co zamieniłoby pretopos Heytinga w elementarny topos . Każdy taki topos, który interpretuje, jest oczywiście modelem tych słabszych teorii, ale lokalnie zostały zdefiniowane pretozy zamknięte kartezjańskie, które np. interpretują teorie z potęgą, ale odrzucają pełną Separację i Powerset.

W teorii typów wyrażenie " " istnieje samoistnie i oznacza przestrzenie funkcyjne , pojęcie pierwotne. Te rodzaje (lub, w teorii zbiorów, klasę lub zestawy) pojawiają się w sposób naturalny, na przykład w rodzaju zmiękczania bijekcji pomiędzy i , w adjunction . Typowa teoria typów z ogólnymi możliwościami programowania - a na pewno te, które potrafią modelować , która jest uważana za konstruktywną teorię mnogości - będzie miała typ liczb całkowitych i przestrzeni funkcyjnych reprezentujących , i jako taka będzie zawierać również typy, które nie są policzalne. To po prostu implikuje i oznacza, że ​​wśród terminów funkcyjnych żaden nie ma właściwości bycia bijekcją.

Konstruktywne teorie mnogości są również badane w kontekście aksjomatów aplikacyjnych .

Analiza

W tej sekcji omówiono siłę . Dla kontekstu wymieniono możliwe dalsze zasady, które niekoniecznie są klasyczne i nie są powszechnie uważane za konstruktywne. Oto ogólne ostrzeżenie: Czytając twierdzenia o równoważności zdań w kontekście obliczeniowym, zawsze należy mieć świadomość, które zasady wyboru , indukcji i rozumienia są po cichu zakładane. Zobacz także powiązane Analiza konstruktywna i Analiza obliczeniowa .

W stronę realnych

Potęgowanie implikuje zasady rekurencji i tak w , można wnioskować o sekwencjach lub o interwałach zmniejszających się w i to również umożliwia mówienie o sekwencjach Cauchy'ego i ich arytmetyce. Każda liczba rzeczywista Cauchy'ego jest zbiorem ciągów, tj. podzbiorem zbioru funkcji na . Wymagane jest więcej aksjomatów, aby zawsze zapewniać kompletność klas równoważności takich sekwencji i należy postulować silne zasady, aby sugerować istnienie modułu zbieżności dla wszystkich sekwencji Cauchy'ego. Słaby wybór policzalny jest generalnie kontekstem dowodzenia jednoznaczności liczb rzeczywistych Cauchy'ego jako ciała pełnego (pseudo-)uporządkowanego. „Pseudo-” podkreśla tutaj, że nakaz w każdym razie nie zawsze będzie konstruktywnie rozstrzygalny.

Podobnie jak w teorii klasycznej, cięcia Dedekinda są charakteryzowane za pomocą podzbiorów struktur algebraicznych, takich jak : Właściwości bycia zamieszkałym, ograniczone numerycznie powyżej, „zamknięte w dół” i „otwarte w górę” są formułami ograniczonymi w odniesieniu do danego zbioru będącego podstawą algebraicznego Struktura. Standardowym przykładem cięcia, pierwszym elementem rzeczywiście wykazującym te właściwości, jest reprezentacja danego przez

(W zależności od konwencji cięć, jedna z dwóch części lub żadna, jak tutaj, może używać znaku .)

Teoria podana przez aksjomaty do tej pory potwierdza, że ​​pseudouporządkowane pole, które jest również zupełne Archimedesa i Dedekinda , jeśli w ogóle istnieje, jest w ten sposób charakteryzowane jednoznacznie, aż do izomorfizmu. Jednak istnienie tylko przestrzeni funkcyjnych, takich jak nie nadaje się do bycia zbiorem, a więc klasa wszystkich podzbiorów nie spełnia nazwanych własności. To, co jest wymagane, aby klasa liczb rzeczywistych Dedekinda była zbiorem, to aksjomat dotyczący istnienia zbioru podzbiorów.

W obu przypadkach mniej stwierdzeń dotyczących arytmetyki liczb rzeczywistych jest rozstrzygalnych w porównaniu z teorią klasyczną.

Konstruktywne szkoły

Twierdzenia niekonstruktywne cenne w badaniach analizy konstruktywnej są powszechnie formułowane jako odnoszące się do wszystkich ciągów binarnych, czyli funkcji . To znaczy roszczenia określone ilościowo przez .

Najbardziej widocznym przykładem jest ograniczona zasada wszechwiedzy , postulująca właściwość dysjunktywną, jak na poziomie -zdań lub funkcji. ( Przykładowe funkcje mogą być konstruowane w trybie raw tak, że jeśli są niesprzeczne, konkurujące rozłączenia są -niedowodliwe.) Zasada jest niezależna od np. przedstawionej poniżej. W tej konstruktywnej teorii mnogości implikuje jej „mniejszą” wersję, oznaczoną jako , ograniczony wariant prawa De Morgana . Co więcej, implikuje zasadę Markowa , formę dowodu przez sprzeczność i -wersję twierdzenia o wentylatorze . Wzmianka o takich zasadach trzymających się za -zdań na ogół wskazuje na równoważne sformułowania w kategoriach sekwencji, decydujące o oddzielności rzeczywistych. W konstruktywnym kontekście analizy z policzalnymi możliwościami jest to np. równoważne twierdzeniu, że każda rzeczywistość jest albo racjonalna, albo irracjonalna – znowu bez wymogu bycia świadkiem rozłączności.

Tak więc w przypadku niektórych twierdzeń stosowanych w teoriach analizy konstruktywnej, których nie można udowodnić przy użyciu tylko podstawowej logiki intuicjonistycznej, patrz lub nawet nieklasyczna teza konstruktywnego Kościoła lub niektóre jej konsekwencje po stronie matematyki rekurencyjnej ( lub ), a także schemat Kripkego (odwrócenie wszystkich podklas policzalnych), indukcję słupkową, twierdzenie o rozstrzygalnym wachlarzu czy nawet nieklasyczną zasadę ciągłości określającą funkcje na niekończących się ciągach poprzez skończone odcinki początkowe po stronie intuicjonizmu Brouwera ( ). Obie szkoły są sprzeczne , tak więc wybór przyjęcia takich praw sprawia, że ​​teoria jest niespójna z twierdzeniami analizy klasycznej.

Nieskończone drzewa

Dzięki relacji między obliczalnością a hierarchią arytmetyczną spostrzeżenia zawarte w tym klasycznym badaniu są również przydatne do konstruktywnych rozważań. Podstawowy wgląd w matematykę odwrotną dotyczy obliczalnych nieskończonych, skończenie rozgałęzionych drzew binarnych. Takie drzewo może być np. zakodowane jako nieskończony zbiór zbiorów skończonych

,

przynależność rozstrzygalna, a drzewa te zawierają wówczas elementy o dowolnie dużych, skończonych rozmiarach. Lemat Słaby Kőnigs mówi: Dla takich zawsze istnieje nieskończona ścieżka w , tj. nieskończony ciąg taki, że wszystkie jego początkowe segmenty są częścią drzewa. W matematyce odwrotnej arytmetyka drugiego rzędu nie dowodzi . Aby to zrozumieć, zauważ, że istnieją drzewa obliczalne, dla których nie istnieje żadna obliczalna taka ścieżka przez nie. Aby to udowodnić, wylicza się częściowe sekwencje obliczalne , a następnie diagonalizuje wszystkie całkowite sekwencje obliczalne w jednej częściowej sekwencji obliczalnej . Można wtedy rozwinąć pewne drzewo , dokładnie zgodne z wciąż możliwymi wartościami wszędzie, które z założenia jest niekompatybilne z jakąkolwiek całkowitą ścieżką obliczalną.

W , zasada ta implikuje niekonstruktywną, mniej ograniczoną zasadę wszechwiedzy . W bardziej konserwatywnym kontekście są one równoważne zakładając - (bardzo słaby wybór policzalny). Jest to również równoważne twierdzeniu Brouwera o punkcie stałym i innym twierdzeniom dotyczącym wartości funkcji ciągłych na liczbach rzeczywistych. Z kolei twierdzenie o punkcie stałym implikuje twierdzenie o wartości pośredniej , ale należy pamiętać, że klasyczne twierdzenia mogą przekładać się na różne warianty, gdy są wyrażone w konstruktywnym kontekście.

Te obawy nieskończony wykresy i tak jego contrapositive daje warunek skończoności. W porównaniu z klasyczną teorią arytmetyczną daje to równoważność zwartości borelowskiej w odniesieniu do skończonych podpokryć rzeczywistego przedziału jednostkowego. Ściśle spokrewnione twierdzenie o istnieniu obejmujące skończone sekwencje w nieskończonym kontekście to twierdzenie o rozstrzygalnym wachlarzu . Ponad , są w rzeczywistości równoważne. W , są one różne, ale ponownie zakładając pewien wybór, implikuje .

Ograniczanie przestrzeni funkcyjnych

W poniższej uwadze funkcja i twierdzenia na ich temat są ponownie rozumiane w sensie teorii obliczalności. Operatora μ włącza wszystkie częściowe ogólne funkcje cyklicznych (czyli programy, w tym sensie, że są one zacji obliczalną), w tym te, które na przykład nie pierwotnych, ale -Całkowita, takich jak funkcja Ackermanna . Definicja operatora obejmuje predykaty nad naturalnymi, a zatem teoretyczna analiza funkcji i ich całości zależy od dostępnych ram formalnych. Tak czy inaczej, te liczby naturalne, które w teorii obliczalności uważa się za wskaźniki funkcji obliczalnych, które są całkowite, są w hierarchii arytmetycznej . Oznacza to, że nadal jest podklasą naturalnych. I tam, totalność, jako predykat na wszystkie programy, jest słynną, obliczalnie nierozstrzygalną .

Nieklasyczna konstruktywna teza Kościoła , zgodnie z założeniem w jej poprzedniku, dotyczy definicji predykatów (a więc i tu ustalonych funkcji), które są ewidentnie całkowite i postuluje, aby odpowiadały one programom obliczalnym. Przyjęcie postulatu czyni zbiór „rzadkim”, widziany z klasycznej teorii mnogości. Zobacz podliczalność .

Postulat to wciąż konsekwentna arytmetyka intuicjonistyczna lub wybór. Ale jest to sprzeczne z klasycznie obowiązującymi zasadami, takimi jak i , które należą do najsłabszych, często dyskutowanych zasad.

Wprowadzenie

Indukcja matematyczna

W poprzednich rozdziałach separacja graniczna ustanowiła już ważność indukcji dla definicji granicznych. W języku ustalonym zasady indukcji można czytać z poprzednikiem zdefiniowanym jak powyżej. Pouczające jest obserwowanie , że zdanie będące następstwem , na przykład , wyrażone tutaj za pomocą notacji klasowej obejmującej podklasę , która może nie stanowić zbioru -- co oznacza , że wiele aksjomatów nie będzie miało zastosowania -- i proste są tylko dwa sposoby sformułowania tego samego pożądanego twierdzenia ( -indeksowana koniunkcja twierdzeń tutaj, w szczególności.) Tak więc zbiór ram teoretycznych z właśnie ograniczoną separacją może być wzmocniony poprzez arytmetyczne schematy indukcji dla nieograniczonych predykatów.

Wspomniana wcześniej zasada iteracji funkcji zbioru jest, alternatywnie do potęgowania, również implikowana przez pełny schemat indukcyjny nad swoją strukturą modelującą naturalne (np . ). Jest to również zasada arytmetyki pierwszego rzędu do udowodnienia większej liczby funkcji niż to robi. Często formułuje się ją wprost w terminach predykatów, jak następuje. Rozważ schemat - :

Schemat aksjomatu pełnej indukcji matematycznej : Dla dowolnego predykatu na ,

Tutaj 0 oznacza jak powyżej, a zestaw oznacza następcę zbioru , z . Zgodnie z powyższym Aksjomatem Nieskończoności, ponownie jest członkiem .

Jak stwierdzono w części dotyczącej wyboru, zasady indukcji są również implikowane przez różne formy zasad wyboru. Pełny schemat indukcji wynika z pełnego schematu Separacji.

Aby udowodnić istnienie przechodniego domknięcia dla każdego zbioru względem , potrzebny jest przynajmniej ograniczony schemat iteracji. Warto zauważyć, że w programie arytmetyki predykatywnej pełny schemat indukcji matematycznej został skrytykowany jako potencjalnie niepredykatywny , gdy liczby naturalne są zdefiniowane jako obiekt spełniający ten schemat.

Ustaw indukcję

Indukcja pełnego zbioru w dowodzi pełnej indukcji matematycznej nad liczbami naturalnymi. W rzeczywistości daje indukcję na liczbach porządkowych i arytmetyce porządkowej. Zastąpienie nie jest wymagane do udowodnienia indukcji na zbiorze naturalnych, ale jest to dla ich arytmetyki modelowanej w ramach teorii mnogości.

Silniejszy aksjomat - wtedy brzmi następująco:

Schemat aksjomatu indukcji zbioru : Dla dowolnego predykatu ,

Tutaj trzyma się banalnie i odpowiada „dolnej sprawie” w standardowym frameworku. Wariant aksjomatu tylko dla wzorów ograniczonych jest również badany niezależnie i może być wyprowadzony z innych aksjomatów.

Aksjomat pozwala na definiowanie funkcji klas przez rekurencję nieskończoną . Badanie różnych zasad, które nadają definicje zbiorów przez indukcję, tj. definicji indukcyjnych, jest głównym tematem w kontekście konstruktywnej teorii mnogości i ich stosunkowo słabych mocnych stron . Dotyczy to również ich odpowiedników w teorii typów.

Aksjomat regularności wraz z ograniczonym / bezgranicznej Separacja oznacza zestaw Induction ale również ograniczony / nieograniczony , tak Regularność nie jest konstruktywne. Odwrotnie, razem z indukcją zbiorów implikuje regularność.

Metalogiczny

Obejmuje to teraz warianty wszystkich ośmiu aksjomatów Zermelo-Fraenkla . Rozszerzalność, parowanie, łączenie i zastępowanie są rzeczywiście identyczne. Nieskończoność jest wyrażona w mocnym sformułowaniu i implikuje Emty Set, jak w przypadku klasycznym. Separacja, klasycznie stwierdzona zbędna, nie jest konstruktywnie implikowana przez Zastąpienie. Bez Prawa Wykluczonego Środka w tej teorii brakuje, w jej klasycznej formie, pełnej Separacji, Powersetu oraz Regularności.

Teoria nie przekracza siły spójności arytmetyki Heytinga, ale dodanie na tym etapie doprowadziłoby do powstania teorii wykraczającej poza siłę typowej teorii typów : Zakładając separację w nieograniczonej formie, a następnie dodając, aby uzyskać teorię dowodzącą tych samych twierdzeń jako minus regularność! Tak więc dodanie Separacji i Regularności do tego frameworka daje pełne, a dodanie do niego Choice daje .

Dodatkowa siła dowodowo-teoretyczna osiągnięta dzięki Indukcji w kontekście konstruktywnym jest znacząca, nawet jeśli porzucenie Regularności w kontekście nie zmniejsza siły dowodowo-teoretycznej. Aczel był także jednym z głównych twórców teorii zbiorów nieuzasadnionych , który odrzuca ten ostatni aksjomat.

Silna kolekcja

Biorąc pod uwagę wszystkie osłabione aksjomaty, a teraz wychodzące poza te aksjomaty, również widziane w typowanym podejściu Myhilla, rozważmy teorię z potęgowaniem teraz wzmocnioną przez schemat zbierania . Dotyczy to własności relacji, dając początek nieco powtarzalnemu formatowi w jego pierwszym ujmowaniu.

Schemat aksjomatu Strong Collection: Dla dowolnego predykatu ,

Stwierdza, że ​​jeśli istnieje relacja między zbiorami, która jest całkowita w pewnym zbiorze dziedzinowym (to znaczy ma co najmniej jedną wartość obrazu dla każdego elementu w domenie), to istnieje zbiór, który zawiera co najmniej jeden obraz w ramach każdego element domeny. Sformułowanie to ponadto stwierdza, że ​​tylko takie obrazy są elementami tego zbioru przeciwdziedzin. Ostatnie zdanie czyni aksjomat – w tym konstruktywnym kontekście – silniejszym niż standardowe sformułowanie Kolekcji. Gwarantuje to, że nie przekroczy przeciwdomeny, a zatem aksjomat wyraża pewną moc procedury separacji.

Aksjomat jest alternatywą dla schematu zastępczego i faktycznie go zastępuje, ponieważ nie wymaga, aby definicja relacji binarnej była funkcjonalna.

Z reguły pytania o umiarkowanej kardynalności są bardziej subtelne w konstruktywnym otoczeniu. Ponieważ arytmetyka jest tutaj dobrze dostępna, teoria ma iloczyny zależne, dowodzi, że klasa wszystkich podzbiorów liczb naturalnych nie może być przeliczalna, a także dowodzi, że przeliczalne sumy przestrzeni funkcyjnych zbiorów przeliczalnych pozostają przeliczalne.

Metalogiczny

Ta teoria bez , nieograniczonej separacji i „naiwnego” zbioru mocy posiada różne ładne właściwości. Na przykład ma Własność istnienia : Jeśli dla jakiejkolwiek własności , teoria dowodzi, że istnieje zbiór, który ma tę własność, tj. jeśli teoria dowodzi zdania , to istnieje również własność, która jednoznacznie opisuje taki przypadek zbioru. Tzn. teoria dowodzi wtedy również . Można to porównać do arytmetyki Heytinga, gdzie twierdzenia są realizowane przez konkretne liczby naturalne i mają te właściwości. W teorii zbiorów rolę odgrywają zbiory zdefiniowane. Dla kontrastu, przypomnijmy, że w , Aksjomat wyboru implikuje twierdzenie o dobrym uporządkowaniu , tak że formalnie udowodniono , że całkowite uporządkowania z najmniejszym elementem dla podzbiorów zbiorów takich jak istnieją, nawet jeśli w sposób udowodniony nie można opisać takiego uporządkowania.

Konstruktywny Zermelo-Fraenkel

Można zbliżyć się do mocy ustalonej dalej, nie tracąc przy tym interpretacji typu teoretycznego. Teoria znana jako powyższe aksjomaty plus silniejsza forma potęgowania. Dzieje się tak poprzez przyjęcie następującej alternatywy, którą można ponownie postrzegać jako konstruktywną wersję aksjomatu zbioru potęgi :

Schemat aksjomatu kolekcji podzbiorów: dla dowolnego predykatu ,

Ten schemat aksjomatu kolekcji podzbiorów jest odpowiednikiem jednego i nieco jaśniejszego alternatywnego aksjomatu pełni. W tym celu niech będzie klasą wszystkich całkowitych relacji między a i b , ta klasa jest podana jako

Dzięki temu stan alternatywa dla kolekcji podzbiorów. Gwarantuje, że istnieje przynajmniej pewien zbiór, w którym znajduje się odpowiednia ilość pożądanych relacji. Mówiąc bardziej konkretnie, pomiędzy dowolnymi dwoma zbiorami i , istnieje zbiór, który zawiera całkowitą sub-relację dla dowolnej całkowitej relacji od do .

Aksjomat Pełni:

Pełnią aksjomat z kolei jest implikowane przez tzw Presentation aksjomatu o sekcjach, które mogą być także formułowane kategorię teoretycznie .

Pełnia implikuje binarną właściwość doprecyzowania niezbędną do udowodnienia, że ​​klasa cięć Dedekinda jest zbiorem. Nie wymaga to indukcji ani zbierania.

Ani liniowości z porządkowych , ani istnienie zbiorów mocy zbiorów skończonych są wyprowadzić w tej teorii. Zakładając, że albo implikuje Moc ustawioną w tym kontekście.

Metalogiczny

Teoria ta nie ma własności istnienia ze względu na schemat, ale w 1977 Aczel wykazał, że nadal można ją interpretować w teorii typów Martina-Löfa (przy użyciu podejścia zdań jako typów ), zapewniając to, co jest obecnie postrzegane jako standardowy model teorii typów . Odbywa się to za pomocą obrazów jego funkcji oraz dość bezpośredniego uzasadnienia konstruktywnego i predykatywnego, przy zachowaniu języka teorii mnogości. Ten przeliczalny model potwierdza wiele zasad wyboru . Z typem modelu teoretycznego, ma skromną siłę teoretyczną dowodu, patrz : Bachmann-Howard ordinal .

NB: Zerwanie z ZF

Można ponadto dodać nieklasyczne twierdzenie, że wszystkie zbiory są przeliczalne jako aksjomat. Wtedy jest zbiorem (według nieskończoności i potęgowania), podczas gdy klasa lub nawet dowodem nie jest zbiorem, zgodnie z argumentem przekątnym Cantora . Więc ta teoria logicznie odrzuca Powerset i .

W 1989 roku Ingrid Lindström wykazała, że nie w pełni uzasadnione zestawy uzyskane poprzez zastąpienie odpowiednik aksjomatu Fundacji (indukcja) w z Aczél anty-fundamentowej aksjomatu ( ) można też interpretować w rodzaju teorii Martin-Löf.

Intuicjonistyczny Zermelo-Fraenkel

Teoria dotyczy standardowego zestawu Separacji i Mocy .

Tutaj, zamiast schematu Aksjomat zastępowania , można użyć

Aksjomat schematu kolekcji : Dla dowolnego predykatu ,

Podczas gdy aksjomat zastępowania wymaga, aby relacja była funkcjonalna w zbiorze (jak w przypadku, gdy każdy w tym jest powiązany dokładnie z jednym ), aksjomat kolekcji nie wymaga tego. Wymaga jedynie skojarzenia co najmniej jednego i zapewnia istnienie zbioru, który gromadzi co najmniej jeden taki dla każdego takiego . wraz ze Zbiorem oznacza Wymianę.

Jako taki może być postrzegany jako najprostszy wariant bez .

Teoria ta jest zgodna z bycia subcountable jak również z tezą Kościoła dla numeru funkcji teoretycznych. Ale, jak zasugerowano powyżej, własność podprzeliczalności nie może być przyjęta dla wszystkich zbiorów, biorąc pod uwagę, że teoria jest zbiorem.

Metalogiczny

Zmieniając schemat Aksjomatu Zastępowania na schemat Aksjomatu Kolekcji, powstała teoria ma Własność Numerycznej Własności Egzystencji .

Nawet bez , na dowód teoretycznej siły z równymi sobie, że o .

Chociaż opiera się na logice intuicjonistycznej, a nie klasycznej, jest uważana za nieprzydatną . Umożliwia tworzenie zbiorów za pomocą Aksjomatu Separacji z dowolnymi twierdzeniami, także takimi, które zawierają kwantyfikatory, które nie są ograniczone. W ten sposób można tworzyć nowe zbiory w kategoriach uniwersum wszystkich zbiorów. Dodatkowo aksjomat zbioru potęgi implikuje istnienie zbioru wartości logicznych . W obecności wykluczonego środka zestaw ten istnieje i składa się z dwóch elementów. W przypadku jego braku zbiór wartości prawdy jest również uważany za nieprzydatny.

Historia

W 1973 roku John Myhill zaproponował system teorii mnogości oparty na logice intuicjonistycznej, przyjmując najpowszechniejszy fundament , i odrzucając aksjomat wyboru i prawo wyłączonego środka , pozostawiając wszystko inne bez zmian . Jednak różne formy niektórych aksjomatów, które są równoważne w układzie klasycznym, są nierównoważne w układzie konstruktywnym, a niektóre formy implikują . W tych przypadkach do konstruktywnej teorii mnogości przyjmowano wówczas sformułowania słabsze intuicjonistycznie.

intuicjonistyczny Z

Znowu na słabszym końcu, podobnie jak w przypadku jej historycznego odpowiednika teoria mnogości Zermelo , można określić przez teorię intuicjonistyczną ustanowioną podobnie, ale bez Zastępowania, Zbierania lub Indukcji.

Intuicjonistyczny KP

Wspomnijmy jeszcze jedną bardzo słabą teorię, która została zbadana, a mianowicie intuicjonistyczną (lub konstruktywną) teorię mnogości Kripkego–Platka . Teoria ogranicza nie tylko Separację, ale także Zbieranie, tj. jest podobna do Indukcji zamiast pełnego Zastąpienia. Jest szczególnie słaby, gdy bada się go bez Infinity. Teoria nie pasuje do przedstawionej powyżej hierarchii, po prostu dlatego, że od początku posiada schemat aksjomatu Set Induction . Umożliwia to twierdzenia dotyczące klasy liczb porządkowych.

Posortowane teorie

Konstruktywna teoria mnogości

Jak to przedstawił, system Myhilla jest teorią wykorzystującą konstruktywną logikę pierwszego rzędu z tożsamością i trzema rodzajami , a mianowicie zbiorami, liczbami naturalnymi , funkcjami . Jego aksjomaty to:

  • Zwykły aksjomat rozszerzalności dla zbiorów, a także jeden dla funkcji i zwykły aksjomat sumy .
  • Aksjomat ograniczonej lub predykatywnej separacji , który jest osłabioną formą aksjomatu separacji z klasycznej teorii mnogości, wymagający, aby wszelkie kwantyfikacje były ograniczone do innego zbioru, jak omówiono.
  • Forma aksjomatu nieskończoności, twierdząca, że ​​zbiór liczb naturalnych (dla którego wprowadza stałą ) jest w rzeczywistości zbiorem.
  • Aksjomat potęgowania, zakładający, że dla dowolnych dwóch zbiorów istnieje trzeci zbiór, który zawiera wszystkie (i tylko) funkcje, których dziedziną jest pierwszy zbiór i którego zakres jest drugim zbiorem. Jest to mocno osłabiona forma aksjomatu potęgi w klasycznej teorii mnogości, której sprzeciwił się m.in. Myhill ze względu na jego nieredykatywność .

A ponadto:

Można z grubsza utożsamić siłę tej teorii z konstruktywnymi podteoriami w porównaniu z poprzednimi sekcjami.

I wreszcie teoria przyjmuje

Teoria zbiorów w stylu biskupa

Teoria mnogości w stylu konstruktywistycznej szkoły Erretta Bishopa odzwierciedla tę z Myhill, ale jest skonstruowana w taki sposób, że zestawy są wyposażone w relacje rządzące ich dyskretnością. Powszechnie przyjmuje się zależny wybór.

W tym kontekście opracowano wiele analiz i teorii modułów .

Teorie kategorii

Nie wszystkie formalne teorie logiki zbiorów muszą bezpośrednio aksjomatyzować predykat przynależności binarnej " ". A Elementarną Teorię Kategorii Zbiorów ( ), np. przechwytywanie par komponujących się odwzorowań między obiektami, można również wyrazić za pomocą konstruktywnej logiki tła ( ). Teorię kategorii można określić jako teorię strzałek i obiektów, chociaż aksjomatyzacje pierwszego rzędu są możliwe tylko w kategoriach strzałek.

Dobrymi modelami konstruktywnych teorii mnogości w teorii kategorii są pretozy wspomniane w sekcji Potęgowanie – prawdopodobnie również wymagające wystarczającej liczby rzutów , aksjomat suriektywnych „prezentacji” zbioru, implikujący policzalny zależny wybór.

Poza tym toposy mają również języki wewnętrzne, które same mogą być intuicjonistyczne i uchwycić pojęcie zbiorów .

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki