Duża policzalna liczba porządkowa

W matematycznej dyscyplinie teorii mnogości istnieje wiele sposobów opisywania określonych policzalnych liczb porządkowych . Najmniejsze mogą być użytecznie i niekoliście wyrażone w postaci ich normalnych postaci Cantora . Poza tym wiele liczb porządkowych mających znaczenie dla teorii dowodu nadal ma obliczalne notacje porządkowe (patrz analiza porządkowa ). Nie można jednak skutecznie rozstrzygnąć, czy dana domniemana notacja porządkowa jest notacją, czy nie (z powodów nieco analogicznych do nierozwiązywalności problem z zatrzymaniem ); dostępne są różne bardziej konkretne sposoby definiowania liczb porządkowych, które zdecydowanie mają notacje.

Ponieważ notacji jest tylko policzalnie wiele, wszystkie liczby porządkowe z notacjami są wyczerpane znacznie poniżej pierwszej nieprzeliczalnej liczby porządkowej ω ₁ ; ich supremum nazywa się Church-Kleene ω ₁ lub ω
^CK₁ (nie mylić z pierwszą niepoliczalną liczbą porządkową ω ₁ ), opisaną poniżej . Liczby porządkowe poniżej ω
^CK₁ to liczby porządkowe rekurencyjne (patrz poniżej ). Policzalne liczby porządkowe większe niż to nadal mogą być definiowane, ale nie mają notacji.

Ze względu na skupienie się na policzalnych liczbach porządkowych, w całym tekście używana jest arytmetyka porządkowa , chyba że zaznaczono inaczej. Opisane tutaj liczby porządkowe nie są tak duże, jak te opisane w dużych liczbach głównych , ale są duże wśród tych, które mają konstruktywne zapisy (opisy). Można zdefiniować większe i większe liczby porządkowe, ale stają się one coraz trudniejsze do opisania.

Ogólne informacje o rekurencyjnych liczbach porządkowych

Notacje porządkowe

Liczby porządkowe rekurencyjne (lub policzalne) to pewne policzalne liczby porządkowe: luźno mówiąc reprezentowane przez funkcję obliczalną . Istnieje kilka równoważnych definicji tego zjawiska: najprościej można powiedzieć, że obliczalna liczba porządkowa jest typem porządku pewnego rekurencyjnego (tj. obliczalnego) dobrego uporządkowania liczb naturalnych; więc zasadniczo liczba porządkowa jest rekurencyjna, kiedy możemy przedstawić zbiór mniejszych liczb porządkowych w taki sposób, że komputer (na maszyna Turinga ) może nimi manipulować (i zasadniczo je porównywać).

Inna definicja wykorzystuje system notacji porządkowej Kleene'a . W skrócie, notacja porządkowa to albo nazwa zero (opisująca porządkową 0), albo następca notacji porządkowej (opisujący następnik porządkowej opisanej przez tę notację), albo maszyna Turinga (funkcja obliczalna), która tworzy rosnącą sekwencję notacji porządkowych (które opisują liczbę porządkową, która jest granicą ciągu), a notacje porządkowe są (częściowo) uporządkowane tak, aby następnik o był większy niż o i uczynić granicę większą niż jakikolwiek wyraz ciągu (ta kolejność jest obliczalna; jednak sam zbiór O notacji porządkowych jest wysoce nierekurencyjny, ze względu na niemożność podjęcia decyzji, czy dana maszyna Turinga rzeczywiście tworzy sekwencję notacje); rekurencyjna liczba porządkowa jest zatem liczbą porządkową opisaną w jakiejś notacji porządkowej.

Każda liczba porządkowa mniejsza niż rekurencyjna liczba porządkowa sama jest rekurencyjna, więc zbiór wszystkich rekurencyjnych liczb porządkowych tworzy pewną (przeliczalną) liczbę porządkową, porządkową Church -Kleene (patrz poniżej).

Kuszące jest zapomnienie o notacjach porządkowych i mówienie tylko o samych rekurencyjnych liczbach porządkowych: a niektóre stwierdzenia dotyczą rekurencyjnych liczb porządkowych, które w rzeczywistości dotyczą notacji dla tych liczb porządkowych. Prowadzi to jednak do trudności, ponieważ nawet najmniejsza nieskończona liczba porządkowa ω ma wiele zapisów, z których niektórych nie można udowodnić, że są równoważne z oczywistym zapisem (najprostszy program wyliczający wszystkie liczby naturalne).

Stosunek do systemów arytmetycznych

Istnieje związek między policzalnymi liczbami porządkowymi a pewnymi systemami formalnymi (zawierającymi arytmetykę , czyli przynajmniej rozsądny fragment arytmetyki Peano ).

Pewne obliczalne liczby porządkowe są tak duże, że chociaż można je podać za pomocą pewnej notacji porządkowej o , dany system formalny może nie być wystarczająco potężny, aby pokazać, że o jest rzeczywiście notacją porządkową: system nie pokazuje indukcji pozaskończonej dla tak dużych porządkowe.

₀₀ Na przykład zwykłe aksjomaty Peano pierwszego rzędu nie dowodzą indukcji pozaskończonej dla (lub poza) ε ₀ : podczas gdy porządkowe ε można łatwo opisać arytmetycznie (jest policzalne), aksjomaty Peano nie są wystarczająco mocne, aby pokazać, że tak jest porządkowy; w rzeczywistości indukcja pozaskończona na ε dowodzi spójności aksjomatów Peano (twierdzenie Gentzena ), więc na mocy drugiego twierdzenia Gödla o niezupełności aksjomaty Peano nie mogą sformalizować tego rozumowania. (Jest to podstawą twierdzenia Kirby-Parisa o ₀₀ Sekwencje Goodsteina .) Ponieważ arytmetyka Peano może udowodnić, że każda liczba porządkowa mniejsza niż ε jest dobrze uporządkowana, mówimy, że ε mierzy teoretyczną siłę dowodu aksjomatów Peano.

Ale możemy to zrobić dla systemów daleko wykraczających poza aksjomaty Peano. Na przykład mocą teorii mnogości Kripkego – Plateka w teorii mnogości jest liczba porządkowa Bachmanna – Howarda iw rzeczywistości samo dodanie do aksjomatów Peano aksjomatów, które stwierdzają dobre uporządkowanie wszystkich liczb porządkowych poniżej liczby porządkowej Bachmanna – Howarda jest wystarczające otrzymać wszystkie konsekwencje arytmetyczne teorii mnogości Kripkego-Płatka.

Konkretne rekurencyjne liczby porządkowe

Definicje predykatywne i hierarchia Veblena

Wspomnieliśmy już (patrz $,$ normalna Cantora o liczbie porządkowej ε , która ₀ spełniającą równanie , więc jest to granica ciągu 0 1, ${\ Displaystyle \ omega}$ , ${\ Displaystyle \ omega ^ {\ omega}}$ , ${\ Displaystyle \ omega ^ {\ omega ^ {\ omega}}}$ ... Następna liczba porządkowa spełnienie tego równania nazywa się ε ₁ : jest to granica ciągu

\ Displaystyle \ varepsilon _ {0} + 1, \ qquad \ omega ^ {\ varepsilon _ {0} +1}=\varepsilon _{0}\cdot \omega ,\qquad \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega}, \qquad {\text{etc.}}}

Bardziej ogólnie, ${$ $jota$ \ \ $\$ . Moglibyśmy zdefiniować jako najmniejszą liczbę porządkową, taką, że $\ varepsilon _ {\ alfa} = \ alfa} ,$ $Displaystyle$ ponieważ alfabet grecki nie ma nieskończenie wielu liter lepiej jest użyć solidniejszej notacji: zdefiniuj liczby porządkowe ${\ Displaystyle \ varphi _ {\ gamma} (\ beta)}$ przez indukcję pozaskończoną w następujący sposób: niech $}$ ${\ Displaystyle \ varphi _ {0} (\ beta) = \ omega$ $^ {\ beta$ $}$ $displaystyle \varphi _{\gamma }}$ niech będzie -tym stałym punktem ${\ Displaystyle \ varphi _ {\ gamma + 1} (\ beta$ (tzn ${\ Displaystyle \ beta}$ -ta liczba porządkowa taka, że ${\ Displaystyle \ varphi _ {\ gamma} (\ alfa) = \ alfa}$ ; więc na przykład , a kiedy jest liczbą porządkową graniczną , ${\ Displaystyle \ varphi _ {1} (\ beta) = \ varepsilon _ {\ beta$ $}$ zdefiniuj jako ${\ Displaystyle \ varphi _ {\ delta} (\ alfa)}$ ${\ Displaystyle \ alpha}$ -ty wspólny stały punkt dla wszystkich ${\ Displaystyle \ varphi _ {\ gamma}}$ ${\ Displaystyle \ gamma <\ delta$ } $\ Displaystyle \ varphi _ {\ delta} (\alpha )}$ rodzina funkcji jest znana jako hierarchia Veblena (istnieją nieistotne różnice w definicji, takie jak dopuszczanie, dla granicznej liczby porządkowej, $φ$ będzie granicą ${\ Displaystyle \ varphi _ {\ gamma} (\ alfa)}$ dla ${\ Displaystyle \ gamma <\ delta}$ : zasadniczo przesuwa indeksy o 1, co jest nieszkodliwe). $_ {\ gamma}}$ $varphi$ $się$ funkcją Veblen (do .

Porządkowanie: ${\ Displaystyle \ varphi _ {\ alfa} (\ beta) <\ varphi _ {\ gamma} (\ delta)}$ wtedy i tylko wtedy, gdy albo ( ${ \ Displaystyle \ alfa = \ gamma}$ i ${\ Displaystyle \ beta <\ delta}$ ) lub ( ${\ Displaystyle \ alfa <\ gamma}$ i ${\ Displaystyle \ beta <\ varphi _ {\ gamma} (\ delta)}$ ) lub ( ${\ Displaystyle \ alfa > \ gamma}$ i ${\ Displaystyle \ varphi _ {\ alfa }(\beta )<\delta }$ ).

Porządkowa Feferman-Schütte i nie tylko

Najmniejsza liczba porządkowa taka, że $i$ porządkowa – Schütte ogólnie zapisywana $Displaystyle \ Gamma _ {0}}$ . Można go opisać jako zbiór wszystkich liczb porządkowych, które można zapisać jako wyrażenia skończone, zaczynając od zera, używając tylko hierarchii i dodawania Veblena. Liczba porządkowa Fefermana – Schütte jest ważna, ponieważ w pewnym sensie, którego precyzyjne określenie jest skomplikowane, jest to najmniejsza (nieskończona) liczba porządkowa, której nie można („ predykatywnie ") opisana mniejszymi liczbami porządkowymi. Mierzy siłę takich systemów jak " arytmetyczna rekurencja pozaskończona ".

Mówiąc bardziej ogólnie, Γ _α wylicza liczby porządkowe, których nie można uzyskać z mniejszych liczb porządkowych za pomocą dodawania i funkcji Veblena.

Oczywiście możliwe jest opisanie liczb porządkowych poza liczbą porządkową Fefermana – Schütte. Można $by$ nadal szukać stałych punktów w coraz bardziej skomplikowany sposób: wyliczać stałe punkty tego wyliczać stałe punkty tego tak na, a następnie poszukaj pierwszej porządkowej α takiej, że α uzyskuje się w krokach α tego procesu, i kontynuuj diagonalizację w ten sposób ad hoc . Prowadzi to do określenia „ małe „i” duże „liczniki porządkowe Veblena.

Impredicative porządkowe

Aby wyjść daleko poza porządki Fefermana-Schütte, trzeba wprowadzić nowe metody. Niestety nie ma jeszcze żadnego standardowego sposobu, aby to zrobić: wydaje się, że każdy autor w temacie wynalazł swój własny system notacji, a tłumaczenie między różnymi systemami jest dość trudne. Pierwszy taki system wprowadził Bachmann w 1950 roku (w ad hoc ), a różne jego rozszerzenia i odmiany opisali Buchholz, Takeuti (diagramy porządkowe), Feferman (układy θ), Aczel , Bridge, Schütte i Pohlers. Jednak większość systemów wykorzystuje tę samą podstawową ideę konstruowania nowych policzalnych liczb porządkowych, wykorzystując istnienie pewnych niepoliczalnych liczb porządkowych. Oto przykład takiej definicji, opisany bardziej szczegółowo w artykule na temat porządkowej funkcji zwijania :

ψ( α ) jest zdefiniowana jako najmniejsza liczba porządkowa, której nie można skonstruować, zaczynając od 0, 1, ω i Ω i wielokrotnie stosując dodawanie, mnożenie i potęgowanie oraz ψ do wcześniej skonstruowanych liczb porządkowych (z wyjątkiem tego, że ψ można zastosować tylko do argumenty mniejsze niż α , aby upewnić się, że jest dobrze zdefiniowany).

Tutaj Ω = ω ₁ jest pierwszą nieprzeliczalną liczbą porządkową. Jest wstawiana, ponieważ w przeciwnym razie funkcja ψ „utknęła” przy najmniejszej liczbie porządkowej σ takiej, że ε _σ = σ : w szczególności ψ( α )= σ dla dowolnej liczby porządkowej α spełniającej σ ≤ α ≤Ω. Jednak fakt, że uwzględniliśmy Ω pozwala nam ominąć ten punkt: ψ(Ω+1) jest większe niż σ . Kluczową właściwością Ω, której użyliśmy, jest to, że jest większa niż jakakolwiek liczba porządkowa wytworzona przez ψ.

Aby skonstruować jeszcze większe liczby porządkowe, możemy rozszerzyć definicję ψ, dodając więcej sposobów konstruowania niepoliczalnych liczb porządkowych. Można to zrobić na kilka sposobów, opisanych w pewnym stopniu w artykule o porządkowej funkcji zwijania .

₀ Bachmanna – Howarda (czasami nazywana po prostu porządkową Howarda , ψ (ε _{Ω + 1} ) z powyższym zapisem) jest ważna, ponieważ opisuje siłę dowodu teorii mnogości Kripkego – Plateka . Rzeczywiście, głównym znaczeniem tych dużych liczb porządkowych i powodem ich opisania jest ich związek z pewnymi systemami formalnymi, jak wyjaśniono powyżej. Jednak tak potężne systemy formalne, jak pełna arytmetyka drugiego rzędu , nie mówiąc już o teorii mnogości Zermelo-Fraenkla , wydają się na razie poza zasięgiem.

Poza nawet porządkową Bachmanna-Howarda

Poza tym istnieje wiele rekurencyjnych liczb porządkowych, które nie są tak dobrze znane jak poprzednie. Pierwszym z nich jest liczba porządkowa Buchholza , zdefiniowana jako ${\ Displaystyle \ psi _ {0} (\ Omega _ {\ omega})}$ , w skrócie po prostu ${\ Displaystyle \ psi (\ Omega _{\omega })}$ , używając poprzedniej notacji. Jest to teoretyczna liczba porządkowa dowodu . $\ Displaystyle \ Pi _ {1} ^ {1} -CA_ {0}}$ $oraz$ naturalnych, a także zbiorów liczb naturalnych , „formalna teoria skończenie iterowanych definicji indukcyjnych”

Następna jest liczba porządkowa Takeuti-Fefermana-Buchholza , liczba porządkowa teorii dowodu ${\ Displaystyle \ Pi _ {1} ^ {1} -CA + BI}$ ; i inny podsystem arytmetyki drugiego rzędu: - rozumienie + indukcja pozaskończona i $”$ teoria formalna $\ displaystyle ID_ {\ omega}$ z ${\ Displaystyle \ omega}$ - razy iterowane definicje indukcyjne ”. W tej notacji jest to zdefiniowane jako ${\ Displaystyle \ psi _ {0} (\ varepsilon _ {\ Omega _ {\ omega} + 1})$ } Jest to supremum zakresu funkcji psi Buchholza. Po raz pierwszy został nazwany przez Davida Madore. ^{[ potrzebne źródło ]}

Następna liczba porządkowa jest wymieniona we fragmencie kodu opisującym duże policzalne liczby porządkowe i liczby w Agda i zdefiniowana przez „AndrasKovacs” jako ${\ Displaystyle \ psi _ {0} (\ Omega _ {\ omega +1}\cdot\varepsilon_{0})}$ .

Następna liczba porządkowa jest wymieniona w tym samym fragmencie kodu co wcześniej i zdefiniowana jako ${\ Displaystyle \ psi _ {0} (\ Omega _ {\ omega ^ {\ omega}})}$ . Jest to liczba porządkowa oparta na teorii dowodu z ${\ displaystyle ID_ {<\ omega ^ {\ omega}}}$ .

Ta następna liczba porządkowa jest ponownie wymieniona w tym samym fragmencie kodu, zdefiniowana jako $\ psi _ {0} (\ Omega _ {\ varepsilon _ {0}})}$ Displaystyle -teoretyczna liczba porządkowa ja $\ displaystyle ID_ {<\ varepsilon _ {0}}}$ . Ogólnie $})}$ biorąc, teoretyczna liczba porządkowa dowodu $równa$ ψ $zauważ$ $, że w$ konkretnym przypadku reprezentuje pierwszą niezerową liczbę porządkową.

Większość liczb porządkowych do tego momentu można wyrazić za pomocą gry hydra Buchholza (np. ${\ Displaystyle \ psi (\ Omega _ {\ omega}) = + (0 (\ omega) )}$ )

$displaystyle \ varepsilon _$ $I + 1}$ ” upadek , gdzie jest pierwszym niedostępnym (= $} \displaystyle \Pi _{0}^{1}}$ -nie do opisania) kardynał. Jest to liczba porządkowa teorii dowodów teorii mnogości Kripkego-Plateka powiększona o rekurencyjną niedostępność klasy liczb porządkowych (KPi) lub, po stronie arytmetycznej, ${\ Displaystyle \ Delta _ {2} ^ {1 }}$ -zrozumienie + indukcja pozaskończona. Jego wartość jest równa użyciu nieznanej funkcji. ${\ Displaystyle \ psi (\ varepsilon _ {I + 1})}$

$nienazwana liczba$ $.$ określana przez Davida Madore'a jako „policzalny” upadek , gdzie pierwszym kardynałem Mahlo To jest liczba porządkowa teorii dowodu KPM, rozszerzenie teorii mnogości Kripkego-Platka opartej na kardynale Mahlo. $jednej$ równa przy Buchholza

$jest$ $kolejna nienazwana liczba porządkowa,$ ” upadek , gdzie słabo zwartym ( ${\ Displaystyle \ Pi _ {1} ^ {1}}$ - nie do opisania) kardynał. To jest teoretyczno-dowodowa liczba porządkowa teorii mnogości Kripkego-Plateka + Π3 - Ref. Jego wartość jest równa ${\ Displaystyle \ Psi (\ varepsilon _ {K + 1})}$ używając funkcji Psi Rathjena.

$określana$ $,$ liczba porządkowa $displaystyle \Pi _{0}^{2}}$ $policzalny$ ” upadek , gdzie -nieopisany kardynał. To jest liczba porządkowa teorii dowodów teorii mnogości Kripkego-Plateka + Πω-Ref. Jego wartość jest równa ${\ Displaystyle \ Psi _ {X} ^ {\ varepsilon _ {\ Xi + 1}}}$ używając funkcji Psi Stegerta, gdzie ${\ Displaystyle X}$ = ( ${\ Displaystyle \ omega ^ {+}}$ ; ${\ Displaystyle P_ {0}}$ ; ${\ Displaystyle \ epsilon}$ , ${\ Displaystyle \ epsilon}$ , 0).

Następna jest ostatnia nienazwana liczba porządkowa, określana przez Davida Madore'a jako teoretyczna liczba porządkowa stabilności. Jest to dowód-teoretyczny porządek porządkowy Stabilności, rozszerzenie teorii mnogości Kripkego-Płatka. $Psi$ jest równa przy użyciu funkcji gdzie $X}$ = ( $\ displaystyle \ omega ^ {+}}$ ; ${\ Displaystyle P_ {0}}$ ; ${\ Displaystyle \ epsilon}$ , ${\ Displaystyle \ epsilon}$ , 0).

Następna jest grupa liczb porządkowych, o których niewiele wiadomo, ale nadal są dość znaczące (w porządku rosnącym):

Dowód-teoretyczna liczba porządkowa arytmetyki drugiego rzędu .
Możliwa granica notacji porządkowej Taranowskiego. (Przypuszczalny, przy założeniu zasadności systemu notacji)
Dowód-teoretyczna liczba porządkowa ZFC .

„Nierekurencyjne” rekurencyjne liczby porządkowe

Rezygnując z wymogu posiadania konkretnego opisu, można uzyskać jeszcze większe rekurencyjne policzalne liczby porządkowe jako liczby porządkowe mierzące siłę różnych mocnych teorii; z grubsza mówiąc, te liczby porządkowe są najmniejszymi liczbami porządkowymi, których teorie nie mogą udowodnić, że są dobrze uporządkowane. Przyjmując coraz silniejsze teorie, takie jak arytmetyka drugiego rzędu , teoria mnogości Zermelo , teoria mnogości Zermelo-Fraenkla czy teoria mnogości Zermelo-Fraenkla z różnymi dużymi liczbami kardynalnymi aksjomatów, otrzymujemy bardzo duże rekurencyjne liczby porządkowe. (Ściśle mówiąc, nie wiadomo, czy wszystkie z nich naprawdę są liczbami porządkowymi: ze względu na konstrukcję siłę porządkową teorii można udowodnić jedynie na podstawie jeszcze silniejszej teorii. Tak więc w przypadku dużych aksjomatów kardynalnych staje się to dość niejasne.)

Poza rekurencyjnymi liczbami porządkowymi

Porządkowa Church-Kleene

Supremum zbioru rekurencyjnych liczb porządkowych to najmniejsza liczba porządkowa, której nie można opisać w sposób rekurencyjny. (Nie jest to typ porządkowy żadnego rekurencyjnego uporządkowania liczb całkowitych). Ta liczba porządkowa jest policzalną liczbą porządkową zwaną porządkową Churcha -Kleene'a , ${\ Displaystyle \ omega _ {1} ^ {\ operatorname {CK } }}$ . ${\ operatorname {CK}}}$ ^ jest najmniejszą nierekurencyjną liczbą porządkową i od tego momentu nie ma nadziei na dokładne „opisanie” jakichkolwiek liczb porządkowych - możemy je tylko zdefiniować . Ale to wciąż znacznie mniej niż pierwsza niepoliczalna liczba porządkowa, ${\ displaystyle \ omega _ {1}}$ . Jednak, jak sugeruje jego symbol, zachowuje się na wiele sposobów raczej jak ${\ displaystyle \ omega _ {1}}$ . Na przykład można zdefiniować porządkowe funkcje zwijania za pomocą ${\ Displaystyle \ omega _ {1} ^ {\ operatorname {CK}}}$ zamiast ${\ Displaystyle \ omega _ {1}}$ .

Dopuszczalne liczby porządkowe

Porządkowa Churcha-Kleene'a jest ponownie powiązana z teorią mnogości Kripkego-Plateka , ale teraz w inny sposób: podczas gdy liczba porządkowa Bachmanna-Howarda (opisana powyżej ) była najmniejszą liczbą porządkową, dla której KP nie dowodzi indukcji pozaskończonej, liczba porządkowa Churcha-Kleene'a $,$ najmniejszym α takim że konstrukcja wszechświata Gödla L , aż do etapu α , daje model . Takie liczby porządkowe nazywane są dopuszczalnymi , stąd $jest$ najmniejszą dopuszczalną liczbą porządkową (poza ω w przypadku, gdy aksjomat nieskończoności nie jest zawarty w KP

Zgodnie z twierdzeniem Sacksa policzalne dopuszczalne liczby porządkowe są dokładnie skonstruowane w sposób podobny do liczby porządkowej Churcha-Kleene'a, ale dla maszyn Turinga z wyroczniami . Czasami pisze się dla -tej $.$ $porządkowej,$ lub granica mniejszych

Poza dopuszczalnymi liczbami porządkowymi

$jest$ najmniejszą granicą dopuszczalnych liczb porządkowych (wspomnianych później), ale sama liczba porządkowa Jest to również najmniejszy taki, że $)}$ $Displaystyle L _ {\ alfa} \ czapka P (\$ jest modelem ${\ Displaystyle \ Pi _ {1}^{1}} –$ zrozumienie.

Liczba porządkowa, która jest zarówno dopuszczalna, jak i granica dopuszczalnych, lub równoważnie taka, że jest -tą dopuszczalną liczbą porządkową, nazywana jest rekurencyjnie niedostępną , a najmniej rekurencyjnie niedostępną można oznaczyć $alpha$ $}$ ${\ Displaystyle \ omega _ {1} ^ {E_ {1}}}$ . Liczba porządkowa, która jest zarówno rekurencyjnie niedostępna, jak i granica rekurencyjnie niedostępnych, nazywana jest rekurencyjnie hiperniedostępną . Istnieje teoria dużych liczb porządkowych w ten sposób, która jest wysoce równoległa do teorii (małych) dużych liczb kardynalnych . Na przykład możemy zdefiniować rekurencyjnie liczby porządkowe Mahlo $:$ są to $}$ , że każdy -rekurencyjny zamknięty nieograniczony podzbiór $alpha$ zawiera dopuszczalną liczbę porządkową (rekurencyjną odpowiednik definicji kardynała Mahlo ). Ale zauważ, że wciąż mówimy tutaj o możliwych policzalnych liczbach porządkowych. (Chociaż istnienie niedostępnych lub Mahlo kardynałów nie może zostać udowodnione w teorii mnogości Zermelo-Fraenkela , istnienie rekurencyjnie niedostępnych lub rekurencyjnie porządkowych Mahlo jest twierdzeniem ZFC: w rzeczywistości każdy regularny kardynał jest rekurencyjnie Mahlo i więcej, ale nawet jeśli ograniczymy się do policzalnych liczb porządkowych, ZFC dowodzi istnienia rekurencyjnie liczb porządkowych Mahlo, które są jednak poza zasięgiem teorii mnogości Kripkego-Plateka).

Odbicie

Dla zestawu formuł nazywana jest $}$ porządkowa - $czy$ $Gamma$ , $ranga$ spełnia a \ pewna właściwość odbicia dla każdego -formula ${\ displaystyle \ gamma}$ ${\ displaystyle \ phi}$ . Te liczby porządkowe pojawiają się w analizie porządkowej teorii, takich jak KP+Π ₃ -ref , teoria rozszerzająca $Teoria$ Kripkego-Plateka według schematu . Można je również uznać za „rekurencyjne analogi” niektórych niezliczonych kardynałów, takich jak słabo zwarte i nieopisane kardynały . Na przykład $-rekurencyjnie$ porządkowa, która odzwierciedla zwarta . Dla skończonego ${\ Displaystyle n}$ , najmniej ${\ Displaystyle \ Pi _ {n}}$ -odzwierciedlająca liczba porządkowa jest także supremum domkniętych liczb porządkowych monotonicznych definicji indukcyjnych, których wykresy to Π _m+1⁰ .

W szczególności, $odzwierciedlające$ porządkowe mają również charakterystykę przy użyciu funkcjonałów wyższego typu funkcjach porządkowych, nadając im nazwę 2-dopuszczalnych liczb porządkowych . Niepublikowany artykuł Solomona Fefermana $-refleksji$ dla każdej skończonej $podobnej$ odpowiadającej

Nierzutność

Dopuszczalna liczba porządkowa $jest$ nierzutną $nie$ jeśli ma całkowitej $funkcji$ iniekcyjnej odwzorowującej na mniejszą liczbę porządkową. (Jest to banalnie prawdziwe w przypadku regularnych kardynałów; jednak interesują nas głównie policzalne liczby porządkowe.) Bycie nieprzewidywalnym jest znacznie silniejszym warunkiem niż bycie dopuszczalnym, rekurencyjnie niedostępnym, a nawet rekurencyjnie Mahlo. Zgodnie z metodą projektu Jensena to stwierdzenie jest równoważne ze stwierdzeniem, że wszechświat Gödla , L , aż do etapu $}$ , daje model -separacji KP + ${\ Displaystyle \ Sigma _ {1}$ Jednak sama separacja (nie w obecności ) nie jest wystarczająco silnym schematem aksjomatu, aby sugerować brak rzutowania, w rzeczywistości istnieje $\$ $Sigma _ {1}}$ są modelami przechodnimi ${\ displaystyle KP}$ + ${\ Displaystyle \ Sigma _ {1}}$ -oddzielenie dowolnej policzalnej dopuszczalnej wysokości ${\ Displaystyle > \ omega}$ .

Nonprojectible porządkowe są powiązane z pracą Jensena nad projecta.

Liczby porządkowe „nie do udowodnienia”.

Możemy sobie wyobrazić nawet większe liczby porządkowe, które wciąż są policzalne. Na przykład, jeśli ZFC ma model przechodni (hipoteza $\ displaystyle L_{\alpha}}$ niż zwykła hipoteza spójności i implikowana przez istnienie niedostępnego kardynała), to istnieje policzalny taki, że ${$ jest modelem ZFC. Takie liczby porządkowe są poza zasięgiem ZFC w tym sensie, że nie może (z założenia) udowodnić ich istnienia.

Jeśli jest $rekurencyjnie$ przeliczalną teorią mnogości zgodną z $in )\vDash T}$ = L , to najmniejszą taką, że $Displaystyle$ $(L_ {\ alfa},$ jest mniejsze niż najmniej stabilna liczba porządkowa, która następuje.

Stabilne liczby porządkowe

Nawet większe policzalne liczby porządkowe, zwane stabilnymi liczbami porządkowymi , można zdefiniować za pomocą warunków nieopisywalności lub jako takie, że ${\ displaystyle L_ {\ alfa}$ $}$ jest Σ ₁ -elementarnym L ; istnienie tych liczb porządkowych można udowodnić w ZFC i są one blisko spokrewnione z liczbami porządkowymi nieprzewidywalnymi z perspektywy teorii modeli. Dla $policzalnej$ stabilności ${\ Displaystyle \ alfa}$ jest równoważne ${\ Displaystyle L _ {\ alfa} \ prec _ {\ Sigma _ {1}} L _ {\ omega _ {1}}}$ .

Warianty stałych liczb porządkowych

Są to osłabione warianty stabilnych liczb porządkowych. Istnieją liczby porządkowe o tych właściwościach mniejsze niż wspomniana wyżej najmniej niemożliwa do rzutowania liczba porządkowa, na przykład liczba porządkowa jest ${\ Displaystyle (+1)}$ - stabilna, jeśli jest ${\ Displaystyle \ Pi _ {n} ^ {0 }} -$ odzwierciedlając wszystkie naturalne ${\ displaystyle n}$ .

Nazywa się $beta$ liczbę porządkową $)}$ -stabilną iff ${\ Displaystyle L _ {\ alfa} \ prec _ {\ Sigma _{1}}L_{\alpha +\beta }}$
$\ Displaystyle$ liczba porządkowa nazywa się $(^ {+})}$ -stabilna iff ${\ Displaystyle L _ {\ alfa} \ prec _ {\ Sigma _ {1}} L_ {\ beta}}$ $displaystyle \ alpha}$ gdzie jest najmniej dopuszczalną liczbą porządkową większą niż $\$ .
Nazywa się policzalną liczbę porządkową $-stabilną$ iff L $Sigma _ {1}} L_ {\ beta}}$ $\$ $L _ {\ alfa} \$ , gdzie jest najmniejszą $.$ liczbą porządkową $niż$ niż dopuszczalna liczba porządkowa większa
Policzalna liczba porządkowa $nazywana$ jest niedostępnie stabilną iff $_ {1}} L_ {\ beta}$ } ${\ displaystyle \ beta}$ jest najmniej dostępną rekurencyjnie liczbą porządkową większą niż ${\ displaystyle \ alpha}$ .
$β$ liczba porządkowa nazywana jest stabilną Mahlo iff ${\ Displaystyle L _ {\ alfa} \ prec _ {\ Sigma _ {1}} L_ {\ beta$ } ${\ displaystyle \ beta}$ jest najmniej rekurencyjnie porządkową Mahlo większą niż ${\ displaystyle \ alpha}$ .
$Displaystyle ($ liczba porządkowa $porządkowa$ podwójnie $}$ -stabilna , jeśli istnieje -stabilna liczba ${ \ Displaystyle \ beta > \ alfa}$ takie, że ${\ Displaystyle L _ {\ alfa} \ prec _ {\ Sigma _ {1}} L_ {\ beta}}$ .

Silniejsze osłabienia stabilności pojawiły się w publikacjach dowodowych, w tym w analizie podsystemów arytmetyki drugiego rzędu .

Pseudo-dobrze uporządkowany

W schemacie notacji Kleene niektóre reprezentują liczby porządkowe, a inne nie. Można zdefiniować rekurencyjne uporządkowanie całkowite, które jest podzbiorem notacji Kleene i ma segment początkowy, który jest dobrze uporządkowany z typem zamówienia . ω 1 do K. {\ ${1} ^ {\ operatorname {CK}} }$ . Każdy rekurencyjnie przeliczalny (lub nawet hiperarytmetyczny) niepusty podzbiór tego całkowitego uporządkowania ma najmniejszy element. Pod pewnymi względami przypomina więc dobrze uporządkowaną. Na przykład można na nim zdefiniować operacje arytmetyczne. Jednak nie jest możliwe dokładne określenie, gdzie kończy się początkowa dobrze uporządkowana część, a zaczyna część pozbawiona najmniejszego elementu.

Jako przykład rekurencyjnego pseudo-dobrego uporządkowania, niech S będzie ATR ₀ lub inną rekurencyjnie aksjomatyzowalną teorią, która ma model ω, ale nie ma hiperarytmetycznych modeli ω, i (w razie potrzeby) konserwatywnie rozszerz S o funkcje Skolema . Niech T będzie drzewem (zasadniczo) skończonych częściowych ω-modeli S: Sekwencja liczb naturalnych ${\ Displaystyle x_ {1}, x_ {2}, ..., x_ {n}}$ w T iff S plus ∃m φ (m) ⇒ φ (x _⌈φ⌉ ) (dla pierwszych n wzorów φ z jedną liczbową zmienną wolną; ⌈φ⌉ to liczba Gödla) nie ma dowodu niespójności krótszego niż n. Wtedy porządek T Kleene-Brouwera jest rekurencyjnym pseudoporządkowaniem.

Każda taka konstrukcja musi mieć typ porządkowy ${\ Displaystyle \ omega _ {1} ^ {CK} \ razy (1 + \ eta) + \ rho}$ , gdzie $eta }$ ${\ Displaystyle$ $,$ $porządkową$ porządku a rekurencyjną

Większość książek opisujących duże policzalne liczby porządkowe dotyczy teorii dowodów i niestety nakład jest wyczerpany.

Na rekurencyjnych liczbach porządkowych

Wolfram Pohlers, Teoria dowodu , Springer 1989 ISBN 0-387-51842-8 (dla hierarchii Veblena i niektórych impredicative porządkowych). Jest to prawdopodobnie najbardziej czytelna książka o dużych policzalnych liczbach porządkowych (co nie mówi wiele).
Gaisi Takeuti , Teoria dowodu , wydanie drugie 1987 ISBN 0-444-10492-5 (dla diagramów porządkowych)
Kurt Schütte , Teoria dowodu , Springer 1977 ISBN 0-387-07911-4 (dla hierarchii Veblena i niektórych impredicative porządkowych)
Craig Smoryński, Odmiany nadrzewnego doświadczenia Matematyka. Inteligencja 4 (1982), no. 4, 182–189; zawiera nieformalny opis hierarchii Veblena.
Hartley Rogers Jr. , Theory of Recursive Functions and Effective Computability McGraw-Hill (1967) ISBN 0-262-68052-1 (opisuje rekurencyjne liczby porządkowe i porządkową Churcha-Kleene'a)
Larry W. Miller, Normal Functions and Constructive Ordinal Notations , The Journal of Symbolic Logic , tom 41, numer 2, czerwiec 1976, strony 439 do 459, JSTOR 2272243 ,
Hilbert Levitz, liczby porządkowe pozaskończone i ich zapisy: dla niewtajemniczonych , artykuł wyjaśniający (8 stron, w PostScript )
Herman Ruge Jervell, Prawda i możliwość udowodnienia , rękopis w toku.

Poza rekurencyjnymi liczbami porządkowymi

Barwise, Jon (1976). Dopuszczalne zestawy i struktury: podejście do teorii definiowalności . Perspektywy w logice matematycznej . Springer-Verlag. ISBN 3-540-07451-1 .
Hinman, Peter G. (1978). Hierarchie teorii rekurencji . Perspektywy w logice matematycznej . Springer-Verlag.

Zarówno rekurencyjne, jak i nierekurencyjne liczby porządkowe

Michael Rathjen, „Dziedzina analizy porządkowej”. w SB Cooper i J. Truss (red.): Zestawy i dowody . (Cambridge University Press, 1999) 219-279. W pliku Postscript .

Referencje wbudowane

^ Buchholz, W. (1986-01-01). „Nowy system funkcji porządkowych opartych na teorii dowodu” . Roczniki czystej i stosowanej logiki . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 . ISSN 0168-0072 .
^ Simpson, Stephen G. (2009). Podsystemy arytmetyki drugiego rzędu . Perspektywy w logice (2 wyd.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6 .
^ Buchholz, Wilfried; Feferman, Salomon ; Pohlers, Wolfram; Sieg, Wilfried (1981). Iterowane definicje indukcyjne i podsystemy analizy: najnowsze badania teoretyczno-dowodowe . Notatki z wykładów z matematyki. Tom. 897. Springer-Verlag, Berlin-Nowy Jork. doi : 10.1007/bfb0091894 . ISBN 3-540-11170-0 . MR 0655036 .
^ ^a ^b ^c „Zoo porządkowych” (PDF) . Madore . 2017-07-29 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ W. Buchholz, Nowy system funkcji porządkowych opartych na teorii dowodu (1984) (lematy 1.3 i 1.8). Dostęp 2022-05-04.
^ ^a ^b ^c ^d ^e ^f D. Madore, A Zoo of Ordinals (2017) (s. 6). Dostęp 2021-05-06.
^ Rathjen, Michael (1994-01-01). „Funkcje zwijające oparte na rekurencyjnie dużych liczbach porządkowych: dobrze uporządkowany dowód dla KPM” . Archiwum logiki matematycznej . 33 (1): 35–55. doi : 10.1007/BF01275469 . ISSN 1432-0665 . S2CID 35012853 .
^ „Notacje porządkowe oparte na słabo kardynale Mahlo” (PDF) . Uniwersytet w Leeds . 1990 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ „Dowód teorii odbicia” (PDF) . Uniwersytet w Leeds . 1993-02-21 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ ^a ^b Stegert, Jan-Carl (2010). „Porządkowa teoria dowodu teorii mnogości Kripkego-Plateka rozszerzona o zasady silnego odbicia” . miami.uni-muenster.de . Źródło 2021-08-10 .
^ ^a ^b „Podsystemy arytmetyki drugiego rzędu” (PDF) . Instytucja stanu Penn . 2006-02-07 . Źródło 2010-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ FG Abramson, GE Sacks, „ Niepoliczalne liczby porządkowe Gandy ” (1976), s. 387. Dostęp 13 lutego 2023 r.
^ Arai, Toshiyasu (2015). „Uproszczona analiza odbicia pierwszego rzędu”. arXiv : 1907.17611v1 .
^ W. Richter, P. Aczel, definicje indukcyjne i właściwości odbicia dopuszczalnych liczb porządkowych (1973)
^ ^a ^b ^c ^d Richter, Wayne; Aczel, Peter (1974-01-01). „Definicje indukcyjne i odzwierciedlające właściwości dopuszczalnych liczb porządkowych” (PDF) . Studia z logiki i podstaw matematyki . 79 : 301–381. doi : 10.1016/S0049-237X(08)70592-5 . hdl : 10852/44063 . ISBN 9780444105455 . ISSN 0049-237X .
^ S. Feferman, nieopisane kardynały i dopuszczalne analogi (2013, niepublikowane). Dostęp 18 listopada 2022 r.
^ KJ Devlin, Wprowadzenie do subtelnej struktury konstruowalnej hierarchii , Studies in Logic and the Foundations of Mathematics (tom 79, 1974). Dostęp 2022-12-04.
^ „Fred G. Abramson, $.$ modele separacji ” (2014) Dostęp 23 lipca 2022 r.
^ ^a ^b ^c ^d ^e ^f ^g ^h D. Madore, Zoo porządkowe . Dostęp 2022-12-04.
^ KJ Devlin, Wprowadzenie do subtelnej struktury konstruowalnej hierarchii (1974). Dostęp 21 lutego 2023 r.
^ W. Marek, K. Rasmussen, Widmo L w bibliotekach ( katalog WorldCat ) ( strona EuDML ), Państwowe Wydawn. Dostęp 2022-12-01.
^ Barwise (1976), twierdzenie 7.2.
^ ^ab ^Simpson , Stephen G. (1978-01-01). „Krótki kurs teorii dopuszczalnej rekurencji” . Studia z logiki i podstaw matematyki . 94 : 355–390. doi : 10.1016/S0049-237X(08)70941-8 . ISBN 9780444851635 . ISSN 0049-237X .
^ Arai, Toshiyasu (1996). „Wprowadzenie twardej linii w teorii dowodu”. arXiv : 1104.1842v1 .
^ W. Chan, policzalna dopuszczalna porządkowa relacja równoważności (2017), s.1233. Dostęp 28 grudnia 2022 r.

[1] Buchholz, W. (1986-01-01). „Nowy system funkcji porządkowych opartych na teorii dowodu” . Roczniki czystej i stosowanej logiki . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 . ISSN 0168-0072 .

[2] Simpson, Stephen G. (2009). Podsystemy arytmetyki drugiego rzędu . Perspektywy w logice (2 wyd.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6 .

[3] Buchholz, Wilfried; Feferman, Salomon ; Pohlers, Wolfram; Sieg, Wilfried (1981). Iterowane definicje indukcyjne i podsystemy analizy: najnowsze badania teoretyczno-dowodowe . Notatki z wykładów z matematyki. Tom. 897. Springer-Verlag, Berlin-Nowy Jork. doi : 10.1007/bfb0091894 . ISBN 3-540-11170-0 . MR 0655036 .

[:1-4] „Zoo porządkowych” (PDF) . Madore . 2017-07-29 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[5] W. Buchholz, Nowy system funkcji porządkowych opartych na teorii dowodu (1984) (lematy 1.3 i 1.8). Dostęp 2022-05-04.

[:0-6] ^ ^a ^b ^c ^d ^e ^f D. Madore, A Zoo of Ordinals (2017) (s. 6). Dostęp 2021-05-06.

[7] Rathjen, Michael (1994-01-01). „Funkcje zwijające oparte na rekurencyjnie dużych liczbach porządkowych: dobrze uporządkowany dowód dla KPM” . Archiwum logiki matematycznej . 33 (1): 35–55. doi : 10.1007/BF01275469 . ISSN 1432-0665 . S2CID 35012853 .

[8] „Notacje porządkowe oparte na słabo kardynale Mahlo” (PDF) . Uniwersytet w Leeds . 1990 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[9] „Dowód teorii odbicia” (PDF) . Uniwersytet w Leeds . 1993-02-21 . Źródło 2021-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[:2-10] Stegert, Jan-Carl (2010). „Porządkowa teoria dowodu teorii mnogości Kripkego-Plateka rozszerzona o zasady silnego odbicia” . miami.uni-muenster.de . Źródło 2021-08-10 .

[:3-11] „Podsystemy arytmetyki drugiego rzędu” (PDF) . Instytucja stanu Penn . 2006-02-07 . Źródło 2010-08-10 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[12] FG Abramson, GE Sacks, „ Niepoliczalne liczby porządkowe Gandy ” (1976), s. 387. Dostęp 13 lutego 2023 r.

[13] Arai, Toshiyasu (2015). „Uproszczona analiza odbicia pierwszego rzędu”. arXiv : 1907.17611v1 .

[14] W. Richter, P. Aczel, definicje indukcyjne i właściwości odbicia dopuszczalnych liczb porządkowych (1973)

[RichterAczel74-15] Richter, Wayne; Aczel, Peter (1974-01-01). „Definicje indukcyjne i odzwierciedlające właściwości dopuszczalnych liczb porządkowych” (PDF) . Studia z logiki i podstaw matematyki . 79 : 301–381. doi : 10.1016/S0049-237X(08)70592-5 . hdl : 10852/44063 . ISBN 9780444105455 . ISSN 0049-237X .

[16] S. Feferman, nieopisane kardynały i dopuszczalne analogi (2013, niepublikowane). Dostęp 18 listopada 2022 r.

[17] KJ Devlin, Wprowadzenie do subtelnej struktury konstruowalnej hierarchii , Studies in Logic and the Foundations of Mathematics (tom 79, 1974). Dostęp 2022-12-04.

[18] „Fred G. Abramson, $.$ modele separacji ” (2014) Dostęp 23 lipca 2022 r.

[OrdinalZoo-19] ^ ^a ^b ^c ^d ^e ^f ^g ^h D. Madore, Zoo porządkowe . Dostęp 2022-12-04.

[20] KJ Devlin, Wprowadzenie do subtelnej struktury konstruowalnej hierarchii (1974). Dostęp 21 lutego 2023 r.

[21] W. Marek, K. Rasmussen, Widmo L w bibliotekach ( katalog WorldCat ) ( strona EuDML ), Państwowe Wydawn. Dostęp 2022-12-01.

[22] Barwise (1976), twierdzenie 7.2.

[:5-23] Simpson , Stephen G. (1978-01-01). „Krótki kurs teorii dopuszczalnej rekurencji” . Studia z logiki i podstaw matematyki . 94 : 355–390. doi : 10.1016/S0049-237X(08)70941-8 . ISBN 9780444851635 . ISSN 0049-237X .

[24] Arai, Toshiyasu (1996). „Wprowadzenie twardej linii w teorii dowodu”. arXiv : 1104.1842v1 .

[25] W. Chan, policzalna dopuszczalna porządkowa relacja równoważności (2017), s.1233. Dostęp 28 grudnia 2022 r.