Porządkowa funkcja zwijająca

W logice matematycznej i teorii mnogości porządkowa funkcja zwijania (lub funkcja projekcji ) jest techniką definiowania ( notacji ) pewnych rekurencyjnych dużych policzalnych liczb porządkowych , której zasadą jest nadawanie nazw pewnym liczbom porządkowym znacznie większym niż ta, która jest definiowana, być może nawet duże liczebniki porządkowe (chociaż można je zastąpić rekurencyjnie dużymi liczebnikami porządkowymi kosztem dodatkowych trudności technicznych), a następnie „zwiń” je do systemu notacji dla poszukiwanej liczby porządkowej. Z tego powodu porządkowe funkcje zwijające są opisywane jako impredicative sposób nazywania liczb porządkowych.

Szczegóły definicji porządkowych funkcji zwijających są różne i stają się bardziej skomplikowane w miarę definiowania większych liczb porządkowych, ale typową ideą jest to, że ilekroć w systemie notacji „wyczerpie się paliwo” i nie można nazwać określonej liczby porządkowej, jest znacznie większa liczba porządkowa sprowadzony „z góry”, aby nadać nazwę temu krytycznemu punktowi. Przykład tego, jak to działa, zostanie szczegółowo opisany poniżej, dla porządkowej funkcji zwijania definiującej liczbę porządkową Bachmanna-Howarda (tj. Definiując system notacji aż do liczby porządkowej Bachmanna-Howarda).

Użycie i definicja porządkowych funkcji zwijania jest nierozerwalnie splecione z teorią analizy porządkowej , ponieważ duże policzalne liczby porządkowe zdefiniowane i oznaczone przez dane złamanie są używane do opisania teoretycznej siły porządkowej pewnych systemów formalnych , zwykle podsystemów analizy (takich jak jak te widziane w świetle matematyki odwrotnej ), rozszerzeń teorii mnogości Kripkego-Plateka , systemów matematyki konstruktywnej typu Bishopa czy systemów typu Martina-Löfa intuicjonistyczna teoria typów . ( psi )(1)

oznaczane przy użyciu pewnej odmiany greckiej litery $)$ psi lub ( theta ) ${\ displaystyle \ theta}$ .

Przykład prowadzący do porządkowej Bachmanna-Howarda

Wybór porządkowej funkcji załamującej podany w poniższym przykładzie w dużej mierze naśladuje system wprowadzony przez Buchholza, ale ogranicza się do załamania jednego kardynała dla jasności ekspozycji. Więcej o relacji między tym przykładem a systemem Buchholza będzie mowa poniżej .

Definicja

Niech oznacza pierwszą niepoliczalną liczbę $porządkową$ , lub w rzeczywistości dowolną liczbę porządkową, która jest liczbą $Displaystyle \$ i gwarantuje, że będzie $}$ większy niż wszystkie policzalne liczby porządkowe , które zostaną skonstruowane (na przykład liczba porządkowa Churcha-Kleene jest odpowiednia do naszych celów; ale będziemy pracować z ${\ displaystyle \ omega _ {1}},$ ponieważ pozwala to na wygodne użycie słowo policzalne w definicjach).

Definiujemy funkcję $malejąca$ nie będzie i ciągła ), przyjmując dowolną liczbę porządkową do policzalnej liczby porządkowej $displaystyle \ psi} }$${\ Displaystyle \ psi (\ alpha) ψ {$ , rekurencyjnie na , jak następuje: ${\ displaystyle \ alpha}$

Załóżmy , że został zdefiniowany dla wszystkich i chcemy zdefiniować $\ psi$$)}$$(\ alpha}$$\ Displaystyle \ psi (\ beta)$ .

Niech do $(\ alfa)}$ będzie zbiorem liczb porządkowych generowanych począwszy od ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ i $\ psi}$$↾$ α { \ Displaystyle $}}$$upharpoonright _ {\$ do liczb porządkowych ${\ Displaystyle \ beta <\ alfa}$ . (Formalnie definiujemy ${\ Displaystyle C (\ alfa) _ {0} = \ {0,1, \ omega, \ Omega \}}$ i indukcyjnie ${\ Displaystyle C (\ alfa) _ {n + 1} = C (\ alfa) _ {n} \ kubek \ {\ beta _ { 1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{\beta _{2}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \} }$ dla wszystkich liczb naturalnych ${\ Displaystyle n}$ i pozwalamy do $(\ alfa)}$ być związkiem dla wszystkich $jest$$zdefiniowany$ do

{\ Displaystyle n}.) Następnie α $)}$ jako najmniejsza liczba $.$

W bardziej zwięzły (choć bardziej niejasny) sposób:

${\ Displaystyle \ psi (\ alfa)}$ jest najmniejszą liczbą porządkową, której nie można wyrazić na podstawie ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ i ${\ Displaystyle \ Omega} } za pomocą sum, iloczynów,$$wykładników$ i samej funkcji (do wcześniej skonstruowanych liczb porządkowych mniejszych $)$

Oto próba wyjaśnienia motywacji definicji w sposób intuicyjny: ponieważ zwykłe operacje dodawania, mnożenia i potęgowania nie wystarczają do wyznaczenia liczb porządkowych bardzo daleko, staramy się systematycznie tworzyć nowe nazwy dla ψ {\ displaystyle \ $}$ porządkowe, biorąc pierwszą, która nie ma jeszcze nazwy, a kiedy zabraknie nam nazw, zamiast wymyślać je ad hoc lub stosując schematy ukośne , szukamy ich w liczbach porządkowych znacznie wykraczających poza te, które konstruujemy ( poza ${\ Displaystyle \ Omega}$ , to jest); więc nadajemy nazwy niezliczonym liczbom porządkowym, a ponieważ ostatecznie lista nazw jest z konieczności policzalna, „zwinie” je do policzalnych liczb $porządkowych$

Obliczanie wartości ψ

Aby wyjaśnić, w jaki sposób funkcja jest $.$ stanie tworzyć notacje dla pewnych liczb porządkowych, obliczymy teraz jej pierwsze wartości

Wstępny początek

Najpierw rozważ do $displaystyle C (0)}$ . Zawiera liczby porządkowe ${\ Displaystyle 0,1,2,3, \ omega, \ omega +1, \ omega +2, \ omega \ cdot 2, \ omega \ cdot 3, \ omega ^ {2}, \ omega ^ {3}, \omega ^{\omega },\omega ^{\omega ^{\omega }}}$ i tak dalej. Zawiera również takie liczby porządkowe jak ${\ Displaystyle \ Omega, \ Omega + 1, \ omega ^ {\ Omega + 1}, \ Omega ^ {\ Omega}}$ . Pierwsza ${\ displaystyle$ porządkowa, której nie zawiera, to (co jest granicą , $\ varepsilon _ {0}$ } ${\ Displaystyle \ omega ^ {\ omega}}$$i$ ω $Displaystyle \ omega ^ {\ omega ^ {\ omega}}}$ tak dalej - mniej niż z założenia). $,$ liczebników porządkowych to (granica ${\ Displaystyle \ Omega}$$}$ \ $Displaystyle \ Omega ^ {\ Omega}$ , ${\ Displaystyle \ Omega ^ {\ Omega ^ {\ Omega}}}$ i tak dalej), ale to nie jest takie ważne. To pokazuje, że ${\ Displaystyle \ psi (0) = \ varepsilon _ {0}}$ .

Podobnie, zawiera liczby porządkowe, które można utworzyć z $C(1)$$0$, $1$, $\omega$, $\Omega$ and this time also $\varepsilon _{0}$, using addition, multiplication and exponentiation. This contains all the ordinals up to $\varepsilon _{1}$ but not the latter, so ${\ Displaystyle \ psi (1) = \ varepsilon _ {1}}$ . W ten sposób udowadniamy, że indukcyjnie na ${\ Displaystyle \ psi (\ alfa) = \ varepsilon _ {\ alfa}}$$dowód$ działa jednak tylko jako tak długo, jak ${\ Displaystyle \ alfa <\ varepsilon _ {\ alfa}}$ . Mamy zatem:

${\ Displaystyle \ psi (\ alfa) = \ varepsilon _ {\ alfa} = \ phi _ {1} (\ alfa)}$ dla wszystkich ${\ Displaystyle \ alfa \ leq \ zeta _ {0}}$ , gdzie ${\ Displaystyle \ zeta _ {0} = \ varphi _ {2} (0)}$ jest najmniejszym stałym punktem ${ \displaystyle \alpha \mapsto \varepsilon _{\alpha}}$ .

(Tutaj funkcje są funkcjami Veblena zdefiniowanymi zaczynając od $ε$${\ Displaystyle \ phi _ {1} (\ alfa) = \ varepsilon _ {\ alfa$ } )

${\ Displaystyle \ psi (\ zeta _ {0}) = \ zeta _ {0}}$ ale $}$${\ Displaystyle \ psi (\ zeta _ {0} + 1$ ) nie jest większy, ponieważ nie można skonstruować przy użyciu skończonych zastosowań $_$$\alpha }}$${\ Displaystyle \ varphi _ {1} \ okrężnica \ alfa \ mapsto \ varepsilon$ i dlatego nigdy nie należy do $alfa)}$$Displaystyle$ ustawione na ${\ Displaystyle \ alfa \ leq \ Omega}$ , a funkcja pozostaje „utknęła” w $\ zeta _ {0 }}$ przez jakiś czas:

${\ Displaystyle \ psi (\ alfa) = \ zeta _ {0}}$ dla wszystkich ${\ Displaystyle \ zeta _ {0} \ równoważnik \ alfa \ równoważnik \ Omega}$ .

Pierwsze wartości bezwzględne

Ponownie ${\ Displaystyle \ psi (\ Omega) = \ zeta _ {0}}$ . Jednak kiedy dochodzimy do obliczeń $coś$ się zmieniło: odkąd $do$${\ Displaystyle C (\ alpha)}$ ) dodany wolno nam przyjąć wartość ${\ Displaystyle \ psi (\ Omega) = \ zeta _ {0}}$ w trakcie. Więc do $\ Displaystyle C (\ Omega + 1)}$ zawiera wszystkie liczby porządkowe, które można zbudować z ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ , ${\ displaystyle \ Omega}$ , funkcja ${\ Displaystyle \ varphi _ {1} \ dwukropek \ alfa \ mapsto \ varepsilon _ {\ alfa}}$$używając$ do i tym razem także samego $siebie ,$ , mnożenia i potęgowania. Najmniejsza liczba porządkowa nie w jest ${\ Displaystyle$$\ varepsilon _ {\ zeta _ {0} + 1}}) do ( Ω + 1 ) {\ Displaystyle$ \ $} displaystyle \ varepsilon}$ - liczba po ${\ displaystyle \ zeta _ {0}}$ ).

Mówimy, że definicja i kolejne wartości funkcji takie jak $\ Omega) = \ zeta _ {0}$${\ Displaystyle \ psi (\ Omega + 1) = \ varepsilon _ {\ zeta _ {0} + 1}}$${\ Displaystyle \ psi$ są nieprecyzyjne , ponieważ używają liczb porządkowych (tutaj, ${\ Displaystyle \ Omega}$ ) większe niż te, które są definiowane ( $)$ .

Wartości ψ aż do liczby porządkowej Fefermana – Schütte

Fakt, że ${\ Displaystyle \ psi (\ Omega + \ alfa) = \ varepsilon _ {\ zeta _ {0} + \ alfa}}$ pozostaje prawdziwy dla wszystkich ${\ Displaystyle \ alfa \ leq \ zeta _ {1} = \ varphi _ {2} (1)}$ (zauważ w szczególności, że ${\ Displaystyle \ psi (\ Omega + \ zeta _ {0}) = \ varepsilon _ {\ zeta _ {0} \ cdot 2}}: ale od teraz liczba$ porządkowa ma ${\ Displaystyle \ zeta _ {0}}$ została skonstruowana, nic nie stoi na przeszkodzie, aby wyjść poza to). ${\ Displaystyle \ zeta _ {1} = \ phi _ {2} (1)} ($ = stały punkt ${\ Displaystyle \ alfa \ mapsto \ varepsilon _ {\ alfa}}$ poza ${\ Displaystyle \ zeta _ {0}}$ ), konstrukcja ponownie się zatrzymuje, ponieważ $}$ można skonstruować z mniejszych liczb porządkowych i $przez$ skończone zastosowanie funkcji ${1}$ . Mamy więc ${\ Displaystyle \ psi (\ Omega 2) = \ zeta _ {1}}$ .

To $_$ _ ${\ Displaystyle \ alfa \ równoważnik \ phi _ {3} (0)}$ , gdzie ${\ Displaystyle \ phi _ {2}}$ wylicza stałe punkty ${\ Displaystyle \ phi _ {1} \ okrężnica \ alfa \ mapsto \ varepsilon _ {\ alfa}}$ i ${\ Displaystyle \ phi _ {3} (0)}$ jest pierwszym stałym punktem ${ \displaystyle\phi_{2}}$ . Mamy wtedy ${\ Displaystyle \ psi (\ Omega ^ {2}) = \ phi _ {3} (0)}$ .

Ponownie widzimy, że przez pewien czas: ${\ Displaystyle \ psi (\ Omega ^ {\ alfa}) = \ varphi _ {1+ \ alfa} (0)} pozostaje to prawdą aż$ do pierwszego stałego punktu $Displaystyle \ alpha$$mapsto \ phi _ {\ alfa} (0)}$ \ \ Schütte porządkowy . Zatem ${\ Displaystyle \ psi (\ Omega ^ {\ Omega}) = \ Gamma _ {0}}$ jest liczbą porządkową Fefermana – Schütte.

Poza porządkową Fefermana – Schütte

for all $\alpha \leq \Gamma _{1}$ where ψ ${\ Displaystyle \ psi (\ Omega ^ {\ Omega} + \ Omega ^ {\ alfa}) = \ varphi _ {\ Gamma _$$\Gamma _{1}$ is the next fixed point of ${\ Displaystyle \ alfa \ mapsto \ varphi _ {\ alfa} (0)}$ . $alfa \ mapsto \ Gamma _ {\$ więc, jeśli wylicza punkty stałe, o których mowa (co można również zauważyć, $}$ używając wielowartościowych funkcji Veblena) mamy ${\ Displaystyle \ psi (\ Omega ^ {\ Omega} (1+ \ alfa)} = \ Gamma _ {\ alfa}}$ , aż do pierwszego stałego punktu $↦$${\ Displaystyle \ varphi (1,$ α ${\ Displaystyle \ alfa \ mapsto \ Gamma _ {\ alfa}}$ samego $+1})}$$Displaystyle \ psi (\ Omega ^ {\$ (i pierwszy stały punkt ${\ Displaystyle \ psi (\ Omega ^ {\ Omega \ cdot 2})}$$\ Displaystyle \ varphi (2,0,0)}$ α $alfa, 0)}$ \ ). W ten sposób:

• ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2}})}$ jest liczbą porządkową Ackermanna (zakres notacji ${\ Displaystyle \ varphi (\ alpha ,\beta ,\gamma )}$ zdefiniowane predykatywnie),
• ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {\ omega}})}$ to „mała” liczba porządkowa Veblena (zakres notacji ${\ Displaystyle \ varphi (\ cdot )}$ predykatywnie używając skończenie wielu zmiennych),
• ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {\ Omega}})}$ jest „dużą” liczbą porządkową Veblena (zakres notacji ${\ Displaystyle \ varphi (\ cdot )}$ predykatywnie używając nieskończenie-ale-predykatywnie-wielu zmiennych),
• ψ ${\ Displaystyle \ psi (\ varepsilon _ {\ Omega + 1})}$ ψ $Displaystyle \ psi (\ Omega)}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ Omega})}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {\ Omega}})}$ itd. to liczba porządkowa Bachmanna – Howarda : po tym nasza funkcja ${\ displaystyle \ psi}$ jest stała i nie możemy pójść dalej z podaną przez nas definicją.

Notacje porządkowe aż do porządkowej Bachmanna-Howarda

Wyjaśnimy teraz bardziej systematycznie, w jaki sposób $funkcja$ notacje dla liczb porządkowych aż do liczby porządkowej Bachmanna – Howarda.

Uwaga dotycząca reprezentacji bazowych

, że jeśli $varepsilon _ {0}}, ε {\ displaystyle \$$porządkową$ , która jest potęgą (na przykład sama lub ${\ displaystyle$$\$ lub $)$ każda liczba porządkowa $być$ jednoznacznie wyrażona w postaci ${\ Displaystyle \ delta ^ {\ beta _ {1}} \ gamma _ {1} + \ ldots + \ delta ^ {\ beta _ {k}} \ gamma _ {k}}, gdzie k {\$ displaystyle $}$${\ Displaystyle \ gamma _ {1}, \ ldots, \ gamma _ {k}}$ są niezerowymi liczbami porządkowymi mniejszymi niż ${\ Displaystyle \ delta$ } i ${\ Displaystyle \ beta _ {1}> \ beta _ {2}> \ cdots > \ beta _ {k}}$ są liczbami porządkowymi (dopuszczamy ${\ displaystyle \ beta _ {k} = 0}$ ). Ta „podstawowa $.$ ” jest oczywistym uogólnieniem postaci normalnej Cantora (co ma miejsce ${\ displaystyle \ delta = \ omega}$ ) $ale$ że wyrażenie jest nieinteresujące, tj. w każdym innym przypadku ${\ Displaystyle \ beta _ {i}}$ wszystkie muszą być mniejsze niż ${\ Displaystyle \ alpha}$ ; może się również zdarzyć, że wyrażenie jest trywialne (tj. $równoważnik$ w takim przypadku $1}$ i $gamma _{1}=\alfa }$$\ displaystyle$ ).

Jeśli $\$$Omega$$porządkową$ mniejszą niż $} displaystyle \ gamma _ {i}<\ Omega}$ podstawowa reprezentacja (z definicji) i wykładniki ${\ Displaystyle \ beta _ {i}<\ alfa}$ (ze względu na założenie ${\ Displaystyle \ alpha <\ varepsilon _ {\ Omega +1}} )$ : stąd można przepisać te wykładniki w podstawie i powtarzać operację, aż proces się zakończy (dowolna malejąca sekwencja liczb porządkowych jest skończona) Ω {\ $\ Omega }$ . Wynikowe wyrażenie nazywamy iterowaną bazową reprezentacją ${\ displaystyle$$\ alpha}$ i różnymi zaangażowanymi współczynnikami (w tym jako wykładniki) części wszystkie są < $\ alpha}$$Omega}$ ) lub, w skrócie, -kawałki $Displaystyle$ .

Niektóre własności ψ

• Funkcja $malejąca$ i ciągła (jest to mniej lub bardziej oczywiste z jej definicji).
• ψ ${\ Displaystyle \ psi (\ alfa) = \ psi (\ beta)}$${\ Displaystyle C (\ alfa) = C (\ beta)}$ β $\ Displaystyle \ beta <\ alfa}$ to koniecznie . żadna liczba $porządkowa$ z $\$$\ beta \ leq \ beta '<\ alfa}$ może należeć do (w przeciwnym razie jego obraz przez ${\ Displaystyle$ czyli ${ \ Displaystyle \ psi (\ alfa)}$ należałby do do $\ Displaystyle C (\ alfa)}$ - niemożliwe); więc jest zamknięty przez wszystko, pod czym ${\ Displaystyle C (\ beta$$zamknięciem ,$ są równe.
• Każda wartość przyjęta przez jest liczbą $\ gamma = \ psi (\ alfa$ (tj. stałym punktem ${\ Displaystyle \ beta \ mapsto \ omega ^ {\ beta}})$${$$\ Displaystyle$ . Rzeczywiście, gdyby tak nie było, to zapisując to w normalnej postaci Cantora , można by to wyrazić za pomocą sum, iloczynów i potęgowania z elementów mniejszych od niego, stąd w $\ Displaystyle C (\ alpha)}$$więc$ to .
• Lemat: Załóżmy, że jest $varepsilon} <\ delta }$$,$ i $liczbą porządkową taką, że δ {\ Displaystyle \ delta} jest$$ε$ { dla wszystkich ${\ Displaystyle \ beta <\ alfa}$ : następnie -części (zdefiniowane powyżej ) dowolnego elementu ${\ Displaystyle \ Omega$${\ Displaystyle C (\ alfa)}$ są mniejsze niż ${\ Displaystyle \ delta}$ . Rzeczywiście, niech $delta$$zbiorem$ liczb porządkowych, których wszystkie części są mniejsze niż ${\ displaystyle$ . Wtedy do $\ displaystyle C '}$$\ varepsilon}$ zamknięty przez dodawanie, mnożenie i potęgowanie (ponieważ jest to $displaystyle$ -liczba, więc liczby porządkowe mniejsze od niej są zamknięte na dodawanie, mnożenie i potęgowanie). I zawiera również co $Displaystyle$$\ psi (\ beta)}$ β $\ Displaystyle \ beta <\ alfa}$ z założenia i zawiera ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ , ${\ Displaystyle \ Omega}$ . więc $\ Displaystyle C '\ supseteq C (\ alfa)}$ , który miał zostać pokazany.
• Zgodnie z hipotezą poprzedniego lematu $C(\alfa )}$ w rzeczywistości lemat pokazuje, że $do$$Displaystyle \ delta$ ).
• Dowolny numer mniejszy niż jakiś element z zakresu $Displaystyle \$$}$$\ varepsilon}$ sam mieści się w zakresie (to znaczy pomija $Displaystyle$ nie ${\ Displaystyle \ varepsilon}$ - liczba). Rzeczywiście $displaystyle \ delta$ jeśli jest to liczba nie większa niż zakres , $niech$$α$ δ ${\ Displaystyle \ alpha}$ być najmniejszą górną granicą ${\ Displaystyle \ beta}$ taką, że ${\ Displaystyle \ psi (\ beta) <\ delta}$ : wtedy zgodnie z powyższym mamy ${\ Displaystyle \ psi (\ alfa) \ równoważnik \ delta}$ , ale ${\ Displaystyle \ psi (\ alfa) <\ delta}$ byłoby sprzeczne z faktem, że ${\ Displaystyle \ alpha }$ jest najmniejszą górną granicą - więc ${\ Displaystyle \ psi (\ alfa) = \ delta}$ .
• Ilekroć , zbiór $mniej$$gamma$$dokładnie$ tych porządkowych niż $Omega + 1}}$$\$ ) z których wszystkie -kawałki są mniejsze niż ${\ Displaystyle \ delta}$ . Rzeczywiście, wiemy, że wszystkie liczby porządkowe mniejsze niż $}$$stąd wszystkie$ porządkowe (mniejsze niż ) Ω $\ omega$ - kawałki są mniejsze niż $)$ są w . do ${\ displaystyle C (\ alpha$ . I odwrotnie, jeśli przyjmiemy, ${\ Displaystyle \ psi (\ beta) <\ delta}$ dla wszystkich $to$ słowy, jeśli jest najmniej możliwe przy ${\ Displaystyle \ psi (\ alfa) =$$)$ ), lemat daje żądaną właściwość. Z drugiej strony, jeśli dla pewnego $\ beta)}$${\ Displaystyle \ beta <\ alfa}$ , to już zauważyliśmy do $\ Displaystyle C (\ alfa) = C (\ beta)}$ i możemy zastąpić ${\ Displaystyle \ alpha}$ w najmniejszym możliwym stopniu z ${\ Displaystyle \ psi (\ alfa) = \ delta}$ .

Notacja porządkowa

$powyższych$ faktów, możemy zdefiniować (kanoniczną) notację porządkową dla każdego niż liczba porządkowa Bachmanna – Howarda. Robimy to przez indukcję względem ${\ displaystyle \ gamma}$ .

Jeśli $\ gamma}$$displaystyle$ jest mniejsze niż , używamy iterowanej postaci normalnej Cantora $\ displaystyle \ gamma}$ . $Displaystyle \ delta$ przeciwnym razie istnieje największa ${\$$\ Displaystyle$ lub równa (dzieje się tak, ponieważ zbiór -liczb jest $\ varepsilon} -number δ$ } zamknięte): jeśli ${\ displaystyle \ delta <\ gamma}$ następnie przez indukcję zdefiniowaliśmy notację dla ${\ displaystyle \ delta},$ a podstawowa reprezentacja ${\ displaystyle \ delta}$ daje jeden dla ${\ displaystyle \$$} displaystyle \gamma }$ , więc skończyliśmy.

Pozostaje zająć się przypadkiem, w którym $argumentowaliśmy$${\ Displaystyle \ delta = \ psi (\ alfa)}$ : , że w tym przypadku $możemy$ dla niektórych (prawdopodobnie niepoliczalnych) porządkowych ${\ Displaystyle \ alpha <\ varepsilon _ {\ Omega + 1}}$ : niech ${\ Displaystyle \ alpha }$ być największa możliwa taka liczba porządkowa (która istnieje, ponieważ $ciągła$ ). Używamy iterowanej podstawowej reprezentacji ${\ displaystyle \ alpha$$}$ : pozostaje pokazać, że każdy element tej reprezentacji jest mniejszy niż (więc już zdefiniowaliśmy notację ${\ displaystyle \ delta$ dla tego). Jeśli tak nie jest , to według właściwości, które pokazaliśmy, do $(\ alfa)}$ nie zawiera ${\ displaystyle \ alpha}$ ; $Displaystyle$ wtedy $}$ w ramach tych samych operacji w ${\ Displaystyle \ alpha}$ nigdy nie można wziąć), więc ${\ Displaystyle \ psi (\ alfa + 1) = \ psi (\ alfa) = \ delta}$ , zaprzeczając maksymalności ${\ Displaystyle \ alpha}$ .

Uwaga : W rzeczywistości zdefiniowaliśmy notacje kanoniczne nie tylko dla liczb porządkowych poniżej liczby porządkowej Bachmanna-Howarda, ale także dla pewnych niepoliczalnych liczb porządkowych, a mianowicie tych, których -elementy $mniejsze$ niż liczba porządkowa Bachmanna-Howarda (mianowicie: zapisz je w iterowanej reprezentacji bazowej $i$ reprezentacji kanonicznej dla każdego kawałka). Ta notacja kanoniczna jest używana dla argumentów funkcji $.$ która może być niepoliczalna)

Przykłady

$)$ mniejszych niż notacja porządkowa pokrywa się z iterowaną postacią normalną Cantora (z definicji

$Dla$$notacja$ mniejszych niż pokrywa się z części $}}}$ omega zostanie napisane ${\ Displaystyle {\ varepsilon _{0}}^{\omega ^{\omega }}}$ lub, dokładniej, ${\ Displaystyle \ psi (0) ^ {\ omega ^ {\ omega}}}$ . Dla liczb porządkowych mniejszych niż , $\ Displaystyle \ varepsilon _ {2} = \ psi (2)}$ piszemy w bazie iterowanej, a następnie ${$ elementy w iterowanej bazie $i zapisz$ te elementy w iterowanej postaci normalnej Cantora): więc ${\ Displaystyle \ omega ^ {\ omega ^ {\ varepsilon _ {1} + \ varepsilon _ {0} + 1}}}$ jest napisane ${\ Displaystyle {\ varepsilon _ {1}} ^ {\ varepsilon _ {0} \ omega}}$ lub dokładniej ${\ Displaystyle \ psi (1) ^ {\ psi (0) \, \ omega}}$ . Tak więc do , zawsze używamy największego możliwego ${\ Displaystyle \ zeta _ {0} = \ psi (\ Omega)$${\ displaystyle \ varepsilon}$ - liczba podstawowa, która daje nietrywialną reprezentację.

Poza tym może być konieczne wyrażenie liczb porządkowych poza $-$$\varepsilon }$ zawsze wykonywane w iterowanej bazie , a same elementy muszą być wyrażone przy użyciu największej możliwej $}$${\ displaystyle \ Omega$ -liczba podstawowa dająca nietrywialną reprezentację.

Zauważ, że chociaż $liczbie porządkowej Bachmanna-Howarda,$ zdefiniowaliśmy (notacje kanoniczne są zdefiniowane tylko dla liczb porządkowych mniejszych niż liczba porządkowa Bachmanna-Howarda).

Warunki kanoniczności

Tak zdefiniowane notacje mają tę właściwość, że ilekroć zagnieżdżają $funkcje$ , argumenty funkcji „wewnętrznej $” są zawsze$ niż argumenty funkcji „zewnętrznej” (jest konsekwencją faktu, że $jest$ gdzie α $największym$$\displaystyle \alpha}$ możliwym takim, że ${\ Displaystyle \ psi (\ alfa) = \ delta}$ dla niektórych ${\ Displaystyle \ varepsilon}$ -number ${\ Displaystyle \ delta}$ , wszystkie są mniejsze niż ${\ Displaystyle \ delta}$ , jak pokazaliśmy powyżej) . Na przykład występuje jako notacja: $równe$${\ Displaystyle \ psi (\ Omega) = \ zeta _ {0}},$ ponieważ jest stała między $\ zeta _ {0}}$$Displaystyle$ Ω $\ Displaystyle \ Omega}$ } nie jest to notacja wytworzona przez algorytm indukcyjny, który opisaliśmy.

$displaystyle$ i tylko wtedy, gdy jest iterowaną postacią normalną Cantora liczby porządkowej mniejszej niż lub iterowaną podstawą $\ varepsilon _ {0}} } reprezentacja$$\ Displaystyle \ delta = \ psi (\$ której wszystkie elementy są kanoniczne, dla niektórych $}$ δ $)$ alfa reprezentacja, której wszystkie elementy są kanoniczne i mniejsze niż ${\ displaystyle \ delta}$ . Kolejność $displaystyle$ sprawdzana przez weryfikację leksykograficzną na wszystkich poziomach (pamiętając, że $jest$ większa niż jakiekolwiek wyrażenie otrzymane przez , a dla wartości kanonicznych większa $\ psi}$ zawsze przewyższa mniejsze lub nawet dowolne sumy, iloczyny i wykładniki mniejszego).

Na przykład ${\ Displaystyle \ psi (\ Omega ^ {\ omega + 1} \, \ psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }} to kanoniczna notacja$ dla liczba porządkowa, która jest mniejsza niż liczba porządkowa Fefermana – Schütte: można ją zapisać za pomocą funkcji Veblena jako ${\ Displaystyle \ varphi _ {1} (\ varphi _ {\ omega + 1} (\ varphi _{2}(0))+\varphi _{\omega}(0)^{\varphi _{3}(0)}42)^{\varphi _{1}(1729)\,\omega} }$ .

${\ Displaystyle \ psi (\ Omega ^ {\ psi (\ Omega)}) = \ varphi _ {\ varphi _ {2} (0)} (0)} (ponieważ Ω {$$znacznie$ zauważyć, że (liczba Fefermana – Schütte) to \ $\ Omega}$ jest większa niż ${\ Displaystyle \ psi}$ czegokolwiek) i ${\ Displaystyle \ psi (\ Omega ^ {\ psi (\ Omega)}) = \ varphi _ {\ varphi _ {2} (0)} (0)}$ samo w sobie jest czymś więcej niż ${\ Displaystyle \ psi (\ Omega) ^ {\ psi (\ Omega)} = \ varphi _{2}(0)^{\varphi _{2}(0)}}$ (ponieważ jest większy niż ${\ Displaystyle \ Omega ^ {\ psi (\ Omega)}}$ jest większy niż ${\ Displaystyle \ Omega}}$ , więc każde wyrażenie sumy iloczynu lub wykładnicze obejmujące ${\ displaystyle \ psi (\ Omega)}$ , a mniejsza wartość pozostanie mniejsza niż ${\ Displaystyle \ psi (\ Omega ^ {\ Omega})})$ . W rzeczywistości ${\ Displaystyle \ psi (\ Omega) ^ {\ psi (\ Omega)}}$ jest już mniejszy niż ${\ Displaystyle \ psi (\ Omega + 1)}$ .

Sekwencje standardowe dla notacji porządkowej

Główny artykuł: Sekwencja podstawowa (liczniki porządkowe)

Aby być świadkiem faktu, że zdefiniowaliśmy notacje dla liczb porządkowych poniżej liczby porządkowej Bachmanna-Howarda (które wszystkie mają przeliczalną kofinalność ), możemy zdefiniować standardowe ciągi zbieżne do dowolnej z nich (oczywiście pod warunkiem, że jest to graniczna liczba porządkowa). W rzeczywistości zdefiniujemy również ciągi kanoniczne dla pewnych niepoliczalnych liczb porządkowych, a mianowicie dla niepoliczalnych liczb porządkowych o przeliczalnej kofinalności (jeśli mamy nadzieję zdefiniować ciąg zbieżny do nich...), które są reprezentowalne (to znaczy wszystkie których ${\ displaystyle \Omega }$ -elementy są mniejsze niż liczba porządkowa Bachmanna-Howarda).

Następujące zasady są mniej lub bardziej oczywiste, z wyjątkiem ostatniej:

• Najpierw pozbądź się (iterowanych) reprezentacji bazowych $aby$ zdefiniować standardową sekwencję zbieżną do ${\ Displaystyle \ alfa = \ delta ^ {\ beta _ {1}} \ gamma _ {1} + \ cdots + \ delta ^ {\ beta _ {k}} \ gamma _ {k}} δ {\ Displaystyle \ delta$ } $albo$ ω $\ styl wyświetlania \omega }$ lub ${\ Displaystyle \ psi (\ cdots)}$ (lub , ale patrz poniżej): ${\ Displaystyle \ Omega }$
  • jeśli $wynosi$ zero, to $i nie$ zrobienia;
  • jeśli $\ beta _ {k}}$$następcą i$$wynosi$ zero i jest następcą, to jest ma nic do zrobienia
  • $k}}$$_ {k}}$ jest granicą, weź standardową sekwencję zbieżną do i zamień w $gamma$ wyrażenie przez elementy tej sekwencji;
  • γ $_ {k}}$$gamma$ jest następcą i jest granicą, przepisz ostatni wyraz ${\ beta _ {k}} \ gamma _ {k}}$ jak ${\ Displaystyle \ delta ^ {\ beta _ {k}} (\ gamma _ {k} -1) + \delta ^{\beta _{k}}}$ i zastąp wykładnik ${\ displaystyle \ beta _ {k}}$ w ostatnim członie przez zbieżne do niego elementy sekwencji podstawowej;
  • γ $_ {k}}$$gamma$ jest następcą i jest również, przepisz ostatni termin $\ delta ^ {\ beta _ {k}} \ gamma _ {k}}$ jak ${\ Displaystyle \ delta ^ {\ beta _ {k}} (\ gamma _ {k} - 1)+\delta ^{\beta _{k}-1}\delta }$ i zastąp ostatnią ${\ displaystyle \ delta}$ w tym wyrażeniu przez zbiegające się do niego elementy sekwencji podstawowej.
• ${\ Displaystyle \ delta}$$Displaystyle$ ω $\ Displaystyle \ omega}$ oczywistą sekwencję podstawową sekwencję dla $} \displaystyle\delta}$ { .
• δ $\ delta = \ psi (0)}$$Displaystyle$ , a następnie weź jako podstawową sekwencję dla $\ Displaystyle \ omega, \ omega ^{\omega},\omega ^{\omega ^{\omega}},\ldots}$
• Jeśli ${\ Displaystyle \ delta = \ psi (\ alfa + 1)}$$to$ weź jako podstawową sekwencję dla ${\ Displaystyle \ psi (\ alfa), \ psi (\ alfa) ^ {\ psi (\ alfa)}, \ psi (\ alfa) ^ {\ psi (\ alfa) ^ {\ psi (\ alfa)}} ,\ldkropki}$
• δ ${\ Displaystyle \ delta = \ psi (\ alfa)}$$gdzie$ jest porządkową policzalnej współfinalności, zdefiniuj standardową sekwencję dla ${\ Displaystyle \ delta} uzyskany$$jest ciągła$ zastosowanie do standardowej sekwencji dla $($ przypomnij sobie, że $.$ rosnąca)
• $\$ obsłużyć przypadek, w którym $o$ liczbą porządkową niezliczonej (np. $}$ Displaystyle ). $zbieżnej$ w tym przypadku sekwencji do nie ma sensu ; jednak to, co możemy zdefiniować, to sekwencja zbieżna do pewnego ${\ Displaystyle \ rho <\ alfa}$ z policzalną współfinalnością i taką, że $\ rho}$ stała między $displaystyle$ a ${\ displaystyle \ alpha}$ . ρ ${\ Displaystyle \ rho}$ będzie pierwszym stałym punktem pewnej (ciągłej i nie malejącej) funkcji $)) }$ . Aby go znaleźć, zastosuj te same zasady (od podstawy ${\ Displaystyle \ Omega}$ reprezentacja , $α {\$ znaleźć kanoniczną sekwencję , $displaystyle$$\ alpha}$ wymagana jest sekwencja zbieżna do (czegoś, co nie może istnieć), zamień Ω $($$Omega}$$\ xi$ ξ { $\xi$ gdzie jest zmienną) i wykonaj powtarzaną iterację (zaczynając od {\ displaystyle $0$, say) of the function $\xi \mapsto h(\psi (\xi ))$: this gives a sequence ${\ Displaystyle 0, h (\ psi (0)), h (\ psi (h (\ psi (0)})), \ ldots} zmierzające$ do ${\ Displaystyle \ rho}$ i kanoniczna sekwencja dla ${\ Displaystyle \ psi (\ alfa) = \ psi (\ rho)}$ jest ${\ Displaystyle \ psi (0)}$ , ${\ Displaystyle \psi (h(\psi (0)))}$ , ${\ Displaystyle \ psi (h (\ psi (h (\ psi (0)})))}$ ... Jeśli pozwolimy $\ Displaystyle n}$ th element ( zaczynając od $oznaczamy$ sekwencji dla $jako$$,$ to wyraźniej stwierdzić za . Używając tej notacji, widzimy, że ${\ Displaystyle \ delta [0] = \ psi (0)}$ dość łatwo. Resztę sekwencji możemy zdefiniować za pomocą rekurencji: ${\ Displaystyle \ delta [n] = \ psi (h (\ delta [n-1]) )}$ . (Poniższe przykłady powinny to wyjaśnić.)

Oto kilka przykładów dla ostatniego (i najciekawszego) przypadku:

• Sekwencja kanoniczna dla $\psi (\psi (0))$ : ${\ Displaystyle \ psi$$(0)}$ , , $\psi (\psi (\psi (0)))$... This indeed converges to $Displaystyle \ Omega}$$psi (\ Omega) = \ zeta _ {0}},$ po czym jest stała aż do $\$ .
• Sekwencja kanoniczna dla $Omega + \ psi (0))}$ : ${\ Displaystyle \ psi$$(0)}$${\ Displaystyle \$ \ , ${\ Displaystyle \ psi (\ Omega + \ psi (\ Omega + \ psi (0))), \ ldots }$ do wartości $=$${\ Displaystyle \ rho = \ Omega + \ psi (\ Omega 2) = \ Omega$$\ Displaystyle \ Omega 2}$ po czym jest stała aż do $Ω$ .
• $\ psi (\ Omega ^ {2})}$ Displaystyle to: ${\ Displaystyle \ psi (0), \ psi (\ Omega \ psi (0)), \ psi (\ Omega \ psi (\ Omega \ psi (0))), \ ldots} To zbiega się do$ wartości ${ \displaystyle \psi}$ w ${\ Displaystyle \ rho = \ Omega \ psi (\ Omega ^ {2})}$ .
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {2} 3 + \ Omega)}$ to ${\ Displaystyle \ psi (0), \ psi (\ Omega ^ {2} 3+ \ psi (0)), \ psi (\ Omega ^ {2} 3 + \ psi (\ Omega ^ {2} 3 + \ psi (0)}), \ ldots} To zbiega się$ do wartości $ρ$${\ Displaystyle \ rho = \ Omega$ .
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ Omega})}$ to: ${\ Displaystyle \ psi (0), \ psi (\ Omega ^ {\ psi (0)}), \ psi (\ Omega ^ {\ psi (\ Omega ^ {\ psi (0)})}), \ ldots }$ To zbiega się do wartości ${\ Displaystyle \ psi}$ w ${\ Displaystyle \ rho = \ Omega ^ {\ psi (\ Omega ^ {\ Omega})}}$ .
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ Omega} 3)}$ to: ${\ Displaystyle \ psi (0), \ psi (\ Omega ^ {\ Omega} 2+ \ Omega ^ {\ psi (0)}), \ psi (\ Omega ^ {\ Omega} 2 + \ Omega ^ {\ psi (\ Omega ^ {\ Omega} 2+ \ Omega ^ {\ psi (0)})}), \ ldots}$ To zbiega się do wartości ${\ Displaystyle \ psi}$ przy ${\ Displaystyle \ rho = \ Omega ^ {\ Omega} 2 + \ Omega ^ {\ psi (\ Omega ^ {\ Omega} 3)}}$ .
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ Omega + 1})}$ to: ${\ Displaystyle \ psi (0), \ psi (\ Omega ^ {\ Omega} \ psi (0)), \ psi (\ Omega ^ {\ Omega} \ psi (\ Omega ^ {\Omega}\psi (0)}),\ldots}$ do wartości $=$${\ Displaystyle \ rho = \ Omega ^ {\ Omega} \ psi (\ Omega ^ {\ Omega +$ .
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} + \ Omega 3})}$ to: ${\ Displaystyle \ psi (0), \ psi (\ Omega ^ {\ Omega ^ {2} + \ Omega 2 + \ psi (0)}), \ psi (\ Omega ^ { \Omega ^{2}+\Omega 2+\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)})}),\ldots }$

Oto kilka przykładów innych przypadków:

• Sekwencja kanoniczna dla ${\ Displaystyle \ omega ^ {2}}$ to: ${\ Displaystyle 0}$ , ${\ Displaystyle \ omega}$ , ${\ Displaystyle \ omega 2}$ , ${\ Displaystyle \ omega 3 }$ ...
• ${\ Displaystyle \ psi (\ omega ^ {\ omega})}$ to : ${\ Displaystyle \ psi (1)}$ , ${\ Displaystyle \ psi ( ( \ omega )}$ , ${\ Displaystyle \ psi (\ omega ^ {2})}$ , ${\ Displaystyle \ psi (\ omega ^ {3})}$ ...
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega) ^ {\ omega}}$ to: ${\ Displaystyle 1}$ , ${\ Displaystyle \ psi (\ Omega)}$ , ${\ Displaystyle \ psi (\ Omega) ^ {2}}$ , ${\ Displaystyle \ psi (\ Omega) ^ {3}}$ ...
• Sekwencja kanoniczna dla $\$$}$ : ${\ Displaystyle \ psi (\$ , , ${\ Displaystyle \ psi (\ Omega) ^ {\ psi (\ Omega) ^ {\ psi (\Omega)}}}$ ...
• Sekwencja kanoniczna dla jest $psi (\ Omega + 1)}$ : $(\ Omega)}$${\ Displaystyle$$psi$ + , ${\ Displaystyle \ psi (\ Omega + 2)}$ , ${\ Displaystyle \ psi (\ Omega + 3)}$ ...
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega \ omega)}$ to: ${\ Displaystyle \ psi (0)}$ , ${\ Displaystyle \ psi (\ Omega)}$${\ Displaystyle \ psi (\ Omega 2)}$ , ψ $\ Displaystyle \ psi (\ Omega 3)}$ ...
• Sekwencja kanoniczna dla $1)}$$ψ$ ) $\ psi ( \ Omega )}$ ( , ${\ Displaystyle \ psi (\ Omega ^ {2})}$ , ${\ Displaystyle \ psi (\ Omega ^ {3})}$ ...
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ psi (0)})}$ jest następująca: ${\ Displaystyle \ psi (\ Omega ^ {\ omega}) }$ , ${\ Displaystyle \ psi (\ Omega ^ {\ omega ^ {\ omega}})}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ omega ^ { \omega ^{\omega}}})}$ ... (jest to wyprowadzone z podstawowej sekwencji dla ${\ Displaystyle \ psi (0)}$ ).
• Sekwencja kanoniczna dla ${\ Displaystyle \ psi (\ Omega ^ {\ psi (\ Omega)})}$ to: ${\ Displaystyle \ psi (\ Omega ^ { \ psi (0)})}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ psi (\ psi (0))})}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ psi (\ psi (\ psi (0))}})} ...$ (wywodzi się to z podstawowej sekwencji dla ${\ Displaystyle \ psi (\Omega )}$ , co podano powyżej).

Chociaż sama $to$ sekwencji kanonicznej jest ${\ Displaystyle \ psi (\ Omega)}$ , ${\ Displaystyle \ psi (\ Omega ^ {\ Omega})}$ , ${\ Displaystyle \ psi (\ Omega ^{\Omega ^{\Omega}})}$ ...

Kończący się proces

Zacznij od dowolnej liczby porządkowej mniejszej lub równej liczbie porządkowej Bachmanna-Howarda i powtarzaj następujący proces, o ile nie wynosi ona zero:

• jeśli liczba porządkowa jest następnikiem, odejmij jeden (to znaczy zastąp go jego poprzednikiem),
• jeśli jest to granica, zastąp ją jakimś elementem określonej dla niej sekwencji kanonicznej.

Wtedy prawdą jest, że proces ten zawsze się kończy (ponieważ każdy malejący ciąg liczb porządkowych jest skończony); jednak lubię (ale nawet bardziej niż za) grę hydra :

1. zakończenie może zająć bardzo dużo czasu,
2. dowód zakończenia może być poza zasięgiem niektórych słabych systemów arytmetycznych.

$posmak tego$ , oto kilka jego kroków: zaczynając od Veblen $\ psi (\ Omega ^ {\ Omega ^ {3}})}$ Displaystyle , stamtąd w dół do ${\ Displaystyle \psi (\Omega ^{\Omega ^{2}\psi (0)})}$ , następnie ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} \ omega ^ {\ omega}})}$ potem ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} \ omega ^ {3}})}$ potem ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} \ omega ^ {2} 3} )}$ wtedy ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} (\ omega ^ {2} 2 + \ omega)})} wtedy$ ψ $\ styl wyświetlania \psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})}$ następnie ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2} \ omega ^ {2} 2+ \ Omega \ psi (\ Omega ^ {\ Omega ^ {2} \ omega ^ {2} 2 + \ Omega \ psi (0)})})}$ następnie ${\ Displaystyle \ psi (\ Omega ^ {\ Omega ^ {2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}}) })}$ i tak dalej. Wydaje się, że wyrażenia stają się coraz bardziej skomplikowane, podczas gdy w rzeczywistości liczebniki porządkowe zawsze się zmniejszają.

Jeśli chodzi o pierwsze stwierdzenie, można by wprowadzić dla dowolnej liczby porządkowej $porządkowej$ Bachmanna-Howarda ${\ Displaystyle \ psi (\ varepsilon _ {\ Omega + 1} )}$ , funkcja całkowitoliczbowa ${$ liczbę kroków procesu przed zakończeniem, jeśli zawsze wybiera się $}$ 'ty element z ciągu kanonicznego (ta funkcja spełnia tożsamość ${\ Displaystyle f _ {\ alfa} (n) = f _ {\ alfa [n]} ( n)+1}$ ). Wtedy ${\ Displaystyle f _ {\ alfa}}$ może być bardzo szybko rosnącą funkcją: już ${\ Displaystyle f _ {\ omega ^ {\ omega}} (n)}$ jest zasadniczo ${\ Displaystyle n ^ {n}}$ , funkcja ${\ Displaystyle f _ {\ psi (\ Omega ^ {\ omega})} (n)}$ jest porównywalna z ${\ Displaystyle A (n, n)}$ Ackermanna i ${\ Displaystyle f _ {\ psi (\ varepsilon _ {\ Omega + 1})} (n)}$ jest porównywalny z Funkcja Goodsteina . Jeśli zamiast tego stworzymy funkcję spełniającą tożsamość ${\ Displaystyle g_ {\ alfa} (n) = g _ {\ alfa [n]} (n +1) +1}$ , więc stosuje się indeks funkcji, a następnie tworzymy znacznie szybciej rosnącą funkcję: sol ${\ Displaystyle g _ {\ psi (0)} (n)$ jest już porównywalna z funkcją Goodsteina i jest porównywalna ${\ Displaystyle g _ {\ psi (\ Omega ^ {\ Omega ^ {\ omega} \ omega})} (n)}$ do funkcji TREE .

Jeśli chodzi o drugie stwierdzenie, dokładna wersja jest podana przez analizę porządkową $:$ na przykład teoria mnogości Kripkego – Plateka może udowodnić, że proces kończy się dla dowolnej danej niż liczba porządkowa Bachmanna – Howarda, ale nie może tego zrobić to jednolicie, tj. nie może udowodnić zakończenia począwszy od porządkowej Bachmanna-Howarda. Niektóre teorie, takie jak $arytmetyka$ Peano , są ograniczone mniejszymi liczbami porządkowymi ( w przypadku arytmetyki Peano).

Wariacje na przykładzie

Zmniejszenie wydajności funkcji

Pouczające (choć nie do końca przydatne) jest $zmniejszenie$ .

$powyższą$ definicję, $displaystyle \ psi (0) = \ omega ^ {\ omega}}$ pominąć potęgowanie z repertuaru, z którego $ψ$ otrzymamy (ponieważ jest to najmniejsza liczba porządkowa, której nie można zbudować z ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ i ${\ Displaystyle \ omega}$${\ Displaystyle \ psi (1) = \ omega ^ {\ omega ^ {2}}}$ i podobnie ${\ Displaystyle \ psi (\ omega) = \ omega ^ {\ omega ^ {\ omega}}}$ , ${\ Displaystyle \ psi (\ psi (0)) = \ omega ^ {\ omega ^{\omega ^{\omega}}}}$ aż dojdziemy do stałego punktu, który jest wtedy naszym ${\ Displaystyle \ psi (\ Omega) = \ varepsilon _ {0}}$ . Mamy wtedy ${\ Displaystyle \ psi (\ Omega + 1) = {\ varepsilon _ {0}} ^ {\ omega}}$ i tak dalej, aż ${\ Displaystyle \ psi (\ Omega 2) = \ varepsilon _ {1}}$ . Ponieważ mnożenie ${\ Displaystyle \ Omega}$ ψ ${\ Displaystyle \ psi (\ Omega ^ {2}) = \ varphi _ {2} (0)$ i ${\ Displaystyle \ psi (\ Omega ^ {3}) = \ varphi _ {3} (0)}$ i tak dalej, ale nasza konstrukcja kończy się na tym, ponieważ nie ma sposobu, aby dostać się do lub poza ${ \displaystyle \Omega ^{\omega}}$ : więc zakres tego osłabionego systemu notacji wynosi ${\ Displaystyle \ psi (\ Omega ^ {\ omega}) = \ phi _ {\ omega} (0)}$ (wartość ${\ Displaystyle \ psi ( \Omega ^{\omega })}$ jest taki sam w naszym słabszym systemie, jak w naszym pierwotnym systemie, z tą różnicą, że teraz nie możemy go przekroczyć). To nie sięga nawet tak daleko, jak liczba porządkowa Fefermana – Schütte.

Jeśli zmienimy definicję jeszcze trochę, aby umożliwić tylko dodawanie jako element pierwotny konstrukcji, otrzymamy $^ {2}}$$( 0) = \$ i ${\ Displaystyle \ psi (1) = \ omega ^ {3}}$ i tak dalej, aż ${\ Displaystyle \ psi (\ psi (0)) =\omega^{\omega^{2}}}$ i nadal ${\ Displaystyle \ psi (\ Omega) = \ varepsilon _ {0}}$ . ${\ Displaystyle \ psi (\ Omega + 1) = \ varepsilon _ {0} \ omega}$ i tak dalej, aż ${\ Displaystyle \ psi (\Omega 2)=\varepsilon _{1}}$ i podobnie ${\ Displaystyle \ psi (\ Omega 3) = \ varepsilon _ {2}}$ . $\$ : ponieważ możemy tylko dodawać zakres naszego systemu wynosi Ω {\ Displaystyle \ Omega} , $Ω$ .

W obu przypadkach stwierdzamy, że ograniczenie osłabionej $,$ wynika nie tyle z operacji dozwolonych na policzalnych liczbach porządkowych, ile na niepoliczalnych liczbach porządkowych które pozwalamy sobie oznaczać.

Wykraczając poza porządkową Bachmanna-Howarda

Wiemy, $.$ - Powodem, dla którego $to,$${\ Displaystyle \ varepsilon _ {\ Omega + 1}}$ notacji (nie należy do $alpha$$)}$ dla każdego to zawsze najmniejsza jego górna granica). Można by spróbować dodać $($ lub funkcje Veblena tak wielu zmiennych) do dozwolonych prymitywów poza dodawaniem, mnożeniem i potęgowaniem, ale to nie zaprowadzi nas zbyt daleko. Aby stworzyć bardziej systematyczne notacje dla policzalnych liczb $samej$ , potrzebujemy bardziej systematycznych notacji dla niepoliczalnych liczb porządkowych: nie możemy użyć funkcji, ponieważ daje ona tylko policzalne liczby porządkowe (np. ${\ Displaystyle \ psi (\ Omega + 1)}$ jest, ${\ Displaystyle \ varepsilon _ {\ varphi _ {2} (0) + 1}}$ , na pewno nie ${\ Displaystyle \ varepsilon _ {\ Omega + 1}} )$ , więc pomysł polega na naśladowaniu jego definicji w następujący sposób:

Niech będzie najmniejszą liczbą porządkową, której nie można wyrazić ze wszystkich policzalnych liczb porządkowych i $,$$Omega _ {2}}$ za pomocą sum, $.$ i samą funkcję (do wcześniej skonstruowanych liczb mniejszych $)$

Tutaj ${\ Displaystyle \ Omega _ {2}}$ jest nową liczbą porządkową, która gwarantuje, że będzie większa niż wszystkie liczby porządkowe, które zostaną skonstruowane przy użyciu : ponownie, pozwalając ${\ Displaystyle \ Omega = \ omega _ {1}}$${\ Displaystyle \ Omega _ {2}}$ i ${\ Displaystyle \ Omega _ {2} = \ omega _ {2}}$ działa.

Na przykład ${\ Displaystyle \ psi _ {1} (0) = \ Omega}$ i bardziej ogólnie ${\ Displaystyle \ psi _ {1} (\ alpha )=\varepsilon _{\Omega +\alpha }}$ dla wszystkich policzalnych liczb porządkowych, a nawet dalej ( ${\ Displaystyle \ psi _ {1} (\ Omega) = \ psi _ {1} (\ psi _ {1} (0)) = \ varepsilon _ {\ Omega 2}}$ i ${\ Displaystyle \ psi _ {1} (\ psi _ {1} (1)) = \ varepsilon _ {\ varepsilon _ {\ Omega + 1}}})$ : dotyczy to pierwszy stały punkt ${\ Displaystyle \ zeta _ {\ Omega + 1}}$ funkcji ${\ Displaystyle \ xi \ mapsto \ varepsilon _ {\ xi}}$ poza ${\ Displaystyle \ Omega}$ , która jest granicą ${\ Displaystyle \ psi _ {1} (0)}$ , ${\ Displaystyle \ psi _ {1} ( \psi _{1}(0))}$ i tak dalej. Poza tym mamy ${\ Displaystyle \ psi _ {1} (\ alfa) = \ zeta _ {\ Omega + 1}}$ i pozostaje to prawdą do ${\ Displaystyle \ Omega _ {2}}$ : dokładnie tak, jak w przypadku , mamy ${\ Displaystyle \ psi (\ Omega)}$${\ Displaystyle \ psi _{1}(\Omega _{2})=\zeta _{\Omega +1}}$ i ${\ Displaystyle \ psi _ {1} (\ Omega _ {2} + 1) = \ varepsilon _ {\ zeta _ {\ Omega + 1} + 1}}$ .

Funkcja daje nam system notacji ( zakładając, że $w$ sposób zapisać wszystkie policzalne liczby porządkowe!) Dla niepoliczalnych liczb porządkowych poniżej ${\ Displaystyle \ psi _ {1} (\ varepsilon _ {\ Omega _ {2} + 1})}$ , co jest granicą ${\ Displaystyle \ psi _ {1} (\ Omega _ {2}) }$ , ${\ Displaystyle \ psi _ {1} ({\ Omega _ {2}} ^ {\ Omega _ {2}})} i$ tak dalej.

Teraz możemy ponownie wprowadzić te notacje do oryginalnej funkcji, zmodyfikowanej w następujący sposób: ${\ displaystyle \ psi}$

${\ Displaystyle \ psi (\ alfa)}$ jest najmniejszą liczbą porządkową, której nie można wyrazić z ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ , ${\ Displaystyle \ Omega }$ i ${\ Displaystyle \ Omega _ {2}}$$}$ użyciu sum, iloczynów, wykładników, funkcji i funkcji ${\ Displaystyle \ psi _ {1}$ sama funkcja (do wcześniej skonstruowanych liczb porządkowych mniejszych $)$ .

Ta zmodyfikowana funkcja $pokrywa$ się z poprzednią aż do (włącznie) ${\ Displaystyle \ psi (\ psi _ {1} (1))}$ co jest Porządkowa Bachmanna-Howarda. Ale teraz możemy wyjść poza to i $\ psi _ {1} (1) + 1)}$ ) ${\ Displaystyle \ varepsilon _ {\ psi (\ psi _ {1} (1)) + 1}}$ (następna $porządkowej$ Bachmanna-Howarda). Sprawiliśmy, że nasz system jest podwójnie impredykacyjny: do tworzenia notacji dla policzalnych liczb porządkowych używamy notacji dla pewnych liczb porządkowych między i ${$$\ Displaystyle \ Omega _ {2}},$ które same są zdefiniowane przy użyciu pewnych liczb porządkowych poza ${\ Displaystyle \ Omega _ {2}}$ .

Odmianą tego schematu, która nie ma większego znaczenia przy użyciu tylko dwóch (lub skończenie wielu) zwijających się funkcji, ale staje się ważna dla nieskończenie wielu z nich, jest zdefiniowanie

${\ Displaystyle \ psi (\ alfa)}$ jest najmniejszą liczbą porządkową, której nie można wyrazić z ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ , ${\ Displaystyle \ Omega }$ i ${\ Displaystyle \ Omega _ {2}}$ używając sum, iloczynów, wykładników i ${\ Displaystyle \ psi _ {1}}$ i ${\ Displaystyle \ psi}$ funkcja (do wcześniej skonstruowanych liczb porządkowych mniejszych $niż$ .

$.$$zezwalaj$ użycie tylko dla argumentów niż sama $\ psi (\ Omega _ {2})}$ Displaystyle zamiast ${\ Displaystyle \ psi (\ psi _ {1} ( \Omega _{2}))}$ (chociaż nadal jest równe ${\ Displaystyle \ psi (\ psi _ {1} (\ Omega _ {2}}) = \ psi (\ zeta _ {\ Omega + 1})},$ oczywiście, ale teraz jest stały aż do ${\ Displaystyle \ Omega _ {2}}$ ). $,$ ponieważ, intuicyjnie mówiąc, $zwija$ nazwalne liczby porządkowe poniżej tej ostatniej, więc nie ma większego znaczenia ${\ displaystyle \ psi _ {1}$$displaystyle \ psi}$ jest przywoływany bezpośrednio na liczbach porządkowych poza $}$ na ich obrazie przez . Ale umożliwia zdefiniowanie i zdefiniowanie przez jednoczesną ( a nie „w dół”) indukcję, co jest ważne, jeśli mamy użyć nieskończenie wielu załamań $\ displaystyle \$$}$ Funkcje.

Rzeczywiście, nie ma powodu, aby zatrzymywać się na dwóch poziomach: używając w ten sposób nowych kardynałów, $1$$Omega _ {1}, \Omega _{2},\ldots,\Omega _{\omega}}$ , otrzymujemy system zasadniczo równoważny z tym wprowadzonym przez Buchholza, z tą nieistotną różnicą, że ponieważ Buchholz używa ${\ Displaystyle \ omega +1}$ porządkowych od początku, nie musi dopuszczać mnożenia ani potęgowania; również Buchholz nie wprowadza do systemu liczb ani liczb, ponieważ będą one również generowane przez $że$ : $elegancki$$,$ ​​​​cały schemat jest znacznie bardziej i bardziej zwięzły do ​​zdefiniowania, choć trudniejszy do zrozumienia. Ten system jest również sensownie równoważny z wcześniejszymi (i znacznie trudniejszymi do uchwycenia) „diagramami porządkowymi” Takeutiego i ${\ displaystyle \ theta}$ funkcje Fefermana: ich $taki$ co $)$ - Feferman -Buchholz, która opisuje siłę -zrozumienia taktu .

„Normalny” wariant

Większość definicji porządkowych funkcji zwijających, które można znaleźć w najnowszej literaturze, różni się od tych, które podaliśmy w jeden techniczny, ale ważny sposób, który czyni je technicznie wygodniejszymi, choć intuicyjnie mniej przejrzystymi. Wyjaśniamy to teraz.

Następująca definicja (przez indukcję po ) jest całkowicie równoważna definicji funkcji powyżej : $alpha }$$\ displaystyle \$

Niech do $\ Displaystyle C (\ alfa, \ beta)}$ będzie zbiorem liczb porządkowych generowanych począwszy od ${\ Displaystyle 0}$ , ${\ Displaystyle 1}$ , ${\ Displaystyle \ omega}$ , $\ Omega}$${ \$$displaystyle$ i wszystkie liczby porządkowe mniejsze niż rekurencyjne stosowanie następujących funkcji: dodawanie porządkowe, mnożenie i potęgowanie oraz funkcja ${\ Displaystyle \ psi \ upharpoonright _ {\ alfa}}$ . Wtedy ${\ Displaystyle \ psi (\ alfa)}$$jest$ definiowany jako najmniejsza liczba porządkowa , że ${\ Displaystyle C (\ alfa, \ rho} )\cap \Omega =\rho }$ .

$}$$\ psi (\ alfa)}$ równoważne, ponieważ jeśli najmniejszą liczbą porządkową nie w pierwotnie zdefiniowaliśmy $\$$\ sigma$ , to jest to również najmniejsza liczba porządkowa nie w do ${\ Displaystyle C (\ alfa, 0) = C (\ alfa, \ sigma)$ , a ponadto właściwości, które opisaliśmy $omega$$że$ żadna liczba porządkowa między wyłączną nie należy do ${\ displaystyle \ sigma}$${\ displaystyle$ .)

Możemy teraz dokonać zmiany w definicji, która czyni ją nieco inną:

Niech $będzie$ zbiorem liczb porządkowych generowanych począwszy od { $0$, $1$$\omega$, $\Omega$ and all ordinals less than $\beta$ by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function ${\ Displaystyle {\ tylda {\ psi}} \ upharpoonright _ {\ alfa}}$ . Wtedy $)}$$alfa$ jest zdefiniowany jako najmniejsza liczba porządkowa , że ${\ styl wyświetlania {\tylda {C}}(\alpha,\rho)\cap \Omega =\rho}$ i ${\ Displaystyle \ alfa \ w {\ tylda {C}} (\ alfa, \ rho)}$ .

Pierwsze wartości ${\ Displaystyle {\ tylda {\ psi}}}$ pokrywają się z wartościami ${\ Displaystyle \ psi}$ : mianowicie dla wszystkich ${\ Displaystyle \ alfa <\ zeta _ {0}}$ gdzie $($$}(\alfa)=\psi (\alfa)}$ ( $Displaystyle {\$$_$ klauzula _ Ale w $_ { 0}\leq \alpha \leq \Omega }$ momencie funkcje zaczynają się różnić: podczas gdy funkcja utknęła” w punkcie $dla$ wszystkich $zeta$ , funkcja ${\ Displaystyle {\ tylda {\ psi}}}$ spełnia ${\ Displaystyle {\ tylda {\ psi}} (\ zeta _ {0}) = \ varepsilon _ {\ zeta _ {0}+1}}$ , ponieważ nowy warunek ${\ Displaystyle \ alfa \ w {\ tylda {C}} (\ alfa, \ rho)}$ narzuca ${\ Displaystyle {\ tylda {\ psi}} (\ zeta _ {0})> \ zeta _ {0}}$ . Z drugiej strony nadal mamy ${\ Displaystyle {\ tylda {\ psi}} (\ Omega) = \ zeta _ {0}}$ (ponieważ $)}$${\ displaystyle \ Omega \ in C (\ alfa, \$$rho$ dla wszystkich więc dodatkowy warunek nie wchodzi w grę). W szczególności zauważ, że w przeciwieństwie do $\ tylda {\ psi }}}$$\ Displaystyle {$ , nie jest monotoniczna ani ciągła.

Pomimo tych zmian funkcja definiuje również system notacji porządkowych aż do porządkowej Bachmanna – Howarda: notacje i warunki kanoniczności są nieco inne $na$ , ${\ Displaystyle \ psi (\ Omega + 1 + \ alfa) = {\ tylda {\ psi}} ({\ tylda {\ psi }}(\Omega )+\alpha )}$ dla wszystkich ${\ Displaystyle \ alfa}$ mniej niż wspólna wartość ${\ Displaystyle \ psi (\ Omega 2) = {\ tylda {\ psi}} (\ Omega + 1)}$ ).

Inne podobne OCF

ψ Arai

Funkcja ψ Arai jest porządkową funkcją zwijania wprowadzoną przez Toshiyasu Arai (męża Noriko H. Arai ) w jego artykule: Uproszczona analiza porządkowa odbicia pierwszego rzędu . ${\ Displaystyle \ psi _ {\ Omega} (\ alfa)}$ jest funkcją zwijającą taką, że ${\ Displaystyle \ psi _ {\ Omega} (\ alfa) <\ Omega }$ , gdzie reprezentuje. ${\ Displaystyle \ Omega}$ pierwsza niepoliczalna liczba porządkowa (można ją zastąpić liczbą porządkową Churcha-Kleene'a kosztem dodatkowych trudności technicznych). W całym artykule ${\ Displaystyle {\ mathsf {KP \ Pi _ {N}}}}$ reprezentuje teorię mnogości Kripkego – Plateka dla a ${\ Displaystyle {\ mathsf {\ Pi _ {N} }}}} -$ odzwierciedlając wszechświat, ${\ Displaystyle \ mathbb {K} _ {N}}$ jest najmniejszy ${\ Displaystyle {\ mathsf {\ Pi _ {N}}}}$ - odzwierciedlając liczbę porządkową, $liczbą$ naturalną $Displaystyle$ Ω $\ Omega _ {0} = 0$ .

Załóżmy, że ${\ Displaystyle {\ mathsf {KP \ Pi _ {N} \ vdash \ theta}}}$ za ( ${\ Displaystyle \ Omega}$$_ {1}}}}$ } - zdanie ${\ Displaystyle {\ mathsf {\ theta}}}$ . Wtedy istnieje skończony $,$ że dla ${\ Displaystyle \ alfa = \ psi _ {\ Omega} (\ Omega _ {n} (\ mathbb {K} _ {N} + 1})} , L α ⊨ θ {\$ Displaystyle $} \modele \theta}$ . Można również udowodnić, że $że$ segment ${\ Displaystyle \ {\ alfa \ w OT: \ alfa <\ psi _ {\ Omega} (\ Omega _ {n} (\ mathbb {K} _ {N} + 1}} \ }; n = 1,2, \ ldots}$ jest dobrze ugruntowany , a zatem liczba porządkowa teorii dowodu z ${\ Displaystyle \ psi _ {\ Omega} (\ varepsilon _ {\ mathbb {K} _ {N} +1})}$ jest liczbą porządkową teorii dowodu ${\ Displaystyle {\ mathsf {KP \ Pi _ {N}}}}$ . Korzystając z tego, ${\ Displaystyle \ psi _ {\ Omega} (\ varepsilon _ {\ mathbb {K} _ {N} + 1}) = \ min (\ {\ alfa \ równoważnik \ Omega \ mid \ forall \ theta \ in \ Sigma _{1}({\mathsf {KP\Pi _{N}}}\vdash \theta ^{L_{\Omega}}\rightarrow L_{\alpha}\models \theta)\})}$ . Następnie można dokonać następujących konwersji:

• ${\ Displaystyle \ psi _ {\ Omega} (A) = \ psi _ {0} (\ Omega) = | {\ mathsf {PA}} | = \ varphi (1,0)}$ , gdzie jest najmniej dopuszczalną liczbą porządkową, $jest$ arytmetyką $Peano$ i jest P $varphi}$ Hierarchia Veblena .
• ${\ Displaystyle \ psi _ {\ Omega} (\ varepsilon _ {A + 1}) = \ psi _ {0} (\ varepsilon _ {\ Omega + 1}) = | {\ mathsf {KP} } | = {\ mathsf {BHO}}}$ , gdzie $jest$ najmniej dopuszczalną liczbą porządkową, teorią mnogości Kripkego – Plateka ${\ Displaystyle {\ mathsf {KP}}}$ a ${\ Displaystyle {\ mathsf {BHO}}}$ to liczba porządkowa Bachmanna-Howarda .
• ${\ mathsf {BO}}}$${\ Displaystyle \ psi _ {\ omega} (ja) = \ psi _ {0} (\ omega _ {\ omega}) = | {\ mathsf {\ pi _ {1} ^ {1} -CA_ {0}}}|$$porządkową$ , gdzie jest najmniej dostępną rekurencyjnie liczbą $liczbą$ jest Buchholza .
• ${\ Displaystyle \ psi _ {\ Omega} (\ varepsilon _ {I + 1}) = \ psi _ {0} (\ varepsilon _ {\ Omega _ {\ omega} + 1}) = | {\ mathsf {KPI}}|= {\ mathsf {TFBO}}}$ , gdzie ${\ displaystyle I}$ jest najmniej dostępną rekurencyjnie liczbą porządkową, $Buchholza$$KPI}}}$ to teoria mnogości Kripkego – Plateka z rekurencyjnie niedostępnym wszechświatem, a porządkowa Takeutiego – Fefermana – .

ψ Bachmanna

Pierwszy prawdziwy OCF, Bachmanna, $;$ wynaleziony przez Heinza Bachmanna, nieco nieporęczny, ponieważ zależy od podstawowych sekwencji dla wszystkich granicznych liczb porządkowych a oryginalna definicja jest skomplikowana. Michael Rathjen zasugerował „przekształcenie” systemu, co wygląda następująco:

• Niech reprezentują niepoliczalną liczbę porządkową, taką jak ${\ Displaystyle \ omega _$${1}$ ;
• Następnie zdefiniuj $}}$ zamknięcie $} {\$$\ {0,$ pod dodatkiem, ${\ Displaystyle (\ xi \ rightarrow \ omega ^ {\ xi})}$ i ${\ Displaystyle (\ xi \ rightarrow \ psi _ { \Omega }(\xi ))}$ dla ${\ Displaystyle \ xi <\ alfa}$ .
• ${\ Displaystyle \ psi _ {\ Omega} (\ alfa)}$ jest najmniejszą policzalną liczbą porządkową ρ taką, że ${\ Displaystyle C ^ {\ Omega} (\ alpha ,\rho )\cap \Omega =\rho }$

${\ Displaystyle \ psi _ {\ Omega} (\ varepsilon _ {\ Omega + 1})}$ to liczba porządkowa Bachmanna – Howarda, teoretyczna liczba porządkowa teorii mnogości Kripkego – Plateka z aksjomat nieskończoności (KP).

ψ Buchholza

Główny artykuł: funkcje psi Buchholza

Buchholza to hierarchia funkcji jednoargumentowych $ν$$\ rightarrow {\ mathsf {On} }}$ , z ${\ Displaystyle \ psi _ {\ nu} (\ alfa)}$ czasami skracane jako ${\ Displaystyle \ psi _ {\ nu} \ alfa}$ . Ta funkcja jest prawdopodobnie najbardziej znaną ze wszystkich OCF. Definicja jest taka:

• Ω ${\ Displaystyle \ Omega _ {0} = 1}$ i $\ aleph _ {\ nu}}$ dla ${\ Displaystyle \ nu > 0}$ .
• Niech $^$ zbiorem odrębnych terminów w postaci normalnej Cantora $\ xi}}$$ξ$ { dla ${\ Displaystyle \ xi \ in {\ mathsf {On}}}$ , patrz twierdzenie Cantora o postaci normalnej )
• ${\ Displaystyle C _ {\ nu} ^ {0} (\ alfa) = \ Omega _ {\ nu}}$
• ${\ Displaystyle C_ {\ nu} ^ {n + 1} (\ alfa) = C_ {\ nu} ^ {n} (\ alfa) \ kubek \ {\ psi _ {\ nu} (\ xi) \ mid \ xi \in \alpha \cap C_{\nu }^{n}(\alpha)\land \xi \in C_{u}(\xi)\land u\leq \omega \}}$
• ${\ Displaystyle C _ {\ nu} (\ alfa) = \ bigcup \ ograniczenia _ {n <\ omega} C_ {\ nu} ^ {n} ( \alfa )}$
• ${\ Displaystyle \ psi _ {\ nu} (\ alfa) = \ min (\ {\ gamma \ mid \ gamma \ notin C_ { \nu }(\alfa )\})}$

Granica $porządkowa$ systemu , Takeuti

ψ Buchholza

Główny artykuł: funkcje psi Buchholza § Rozszerzenie

$OCF$ wyrafinowanym rozszerzeniem Buchholza autorstwa matematyka Denisa Maksudova. Granica tego systemu jest znacznie większa, równa gdzie ψ $Omega _ {\ Omega _ {\ cdots}}})}$${\ Displaystyle \ Omega _ {\ Omega _ {\ Omega _ {...}}}}$ oznacza pierwszy stały punkt omega, czasami nazywany rozszerzoną liczbą porządkową Buchholza. Funkcja jest zdefiniowana w następujący sposób:

• Zdefiniuj ${\ Displaystyle \ Omega _ {0} = 1}$ i ${\ Displaystyle \ Omega _ {\ nu} = \ aleph _ {\ nu}}$ dla ${\ Displaystyle \ nu > 0}$ .
• ${\ Displaystyle C _ {\ nu} ^ {0} (\ alfa) = \ {\ beta \ mid \ beta <\ Omega _ {\ nu} \}}$
• ${\ Displaystyle C_ {\ nu} ^ {n +1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \mu ,\beta ,\gamma ,\eta \in C_{\nu }^{n }(\alpha )\land \eta <\alpha \}}$
• ${\ Displaystyle C _ {\ nu} (\ alfa) = \ bigcup \ ograniczenia _ {n <\ omega} C_ {\ nu} ^ {n} ( \alfa )}$
• ${\ Displaystyle \ psi _ {\ nu} (\ alfa) = \ min (\ {\ gamma \ mid \ gamma \ notin C_ { \nu }(\alfa )\})}$

ψ Madore'a

Ta OCF była taka sama jak funkcja ψ używana wcześniej w tym artykule; jest to prostsza, bardziej wydajna wersja funkcji ψ Buchholza zdefiniowanej przez Davida Madore'a. Jego użycie w tym artykule doprowadziło do szerokiego wykorzystania tej funkcji.

• ${\ Displaystyle C_ {0} (\ alfa) = \ {0,1, \ omega, \ Omega \}}$
• ${\ Displaystyle C_ {n + 1} (\ alfa) = \ {\ gamma + \ delta, \ gamma \ delta, \ gamma ^ {\ delta}, \ psi (\ eta) \ mid \ gamma, \delta ,\eta \in C_{n}(\alpha );\eta <\alpha \}}$
• $\ Displaystyle C (\ alfa) = \ bigcup \ ograniczenia _ {n <\ omega} C_ {n} (\ alfa)}$
• ${\ Displaystyle \ psi (\ alfa) = \ min (\ {\ beta \ in \ Omega \ mid \ beta \ notin C (\ alfa )\})}$

Funkcja ta została wykorzystana przez Chrisa Birda, który wynalazł również kolejny OCF.

ptasie θ

Chris Bird wymyślił następujący skrót dla rozszerzonej funkcji Veblena: ${\ displaystyle \ varphi}$ :

• ${\ Displaystyle \ theta (\ Omega ^ {n-1} a_ {n-1} + \ cdots + \ Omega ^ {2} a_ {2} + \ Omega a_ {1} + a_ {0}, b) = \varphi (a_{n-1},\ldots,a_{2},a_{1},a_{0},b)}$
• ${\ Displaystyle \ teta (\ alfa, 0)}$ jest skracane ${\ Displaystyle \ teta (\ alfa)}$

Ta funkcja jest zdefiniowana tylko dla argumentów mniejszych niż $ograniczone$ przez małą liczbę porządkową Veblena.

ψ Jägera

₀ ψ Jägera jest hierarchią jednoargumentowych funkcji porządkowych ψ _κ indeksowanych przez niezliczone kardynały foremne κ mniejsze niż najmniej słabo kardynał Mahlo M wprowadzony przez niemieckiego matematyka Gerharda Jägera w 1984 roku. Został opracowany na podstawie podejścia Buchholza.

• κ $\ Displaystyle \ kappa = ja _ {\ alfa} (0)}$ { dla pewnego < κ , ${\ Displaystyle \ kappa ^ {-} = 0}$ .
• κ ${\ Displaystyle \ kappa = ja _ {\ alfa} (\ beta + 1)}$ pewnego α , β < κ , ${\ Displaystyle \ kappa ^ {-}=I_{\alfa}(\beta)}$ .
• $\ Displaystyle C _ {\ kappa} ^ {0} (\ alfa) = \ {\ kappa ^ {-} \} \ kubek \ kappa ^ {-}}$
• Dla każdego skończonego n , jest najmniejszym zbiorem spełniającym: $Displaystyle C _ {\ kappa} ^ {n + 1} (\ alfa) \ podzbiór M_ {0}}$
  • Suma dowolnych skończenie wielu liczb porządkowych w należy do ${\ Displaystyle C _ {\ kappa} ^ {n + 1} (\ alfa) \ podzbiór M_ {0}}$${\ Displaystyle C _ {\ kappa} ^ {n} (\ alfa) \ podzbiór$ do .
  • dla każdego ${\ Displaystyle \ beta, \ gamma \ in C _ {\ kappa} ^ {n} (\ alfa)}$ , ${\ Displaystyle \ varphi _ {\ beta} (\ gamma) \ w C _ {\ kappa} ^ {n + 1} (\ alfa)}$ .
  • dla każdego ${\ Displaystyle \ beta, \ gamma \ in C _ {\ kappa} ^ {n} (\ alfa)}$ , ${\ Displaystyle I _ {\ beta} (\ gamma) \ w C _ {\ kappa} ^ {n + 1} (\ alfa)}$ .
  • Dla każdego porządkowego γ i niepoliczalnego regularnego kardynała ${\ Displaystyle \ pi \ w C _ {\ kappa} ^ {n} (\ alfa)}$ , ${\ Displaystyle \ gamma <\ pi <\ kappa \ strzałka w prawo \ gamma \ in C _ {\ kappa} ^ {n + 1} (\ alfa)}$ .
  • γ ${\ Displaystyle \ gamma \ in \ alfa \ czapka C_ {\ kappa} ^ {n} (\ alfa)}$ niezliczony kardynał regularny ${ \ Displaystyle \ pi \ in C _ {\ kappa} ^ {n} (\ alfa)}$ , ${\ Displaystyle \ gamma \ in C _ {\ pi} (\ gamma) \ Strzałka w prawo \ psi _ {\ pi} (\ gamma) \ w C _ {\ kappa} ^ {n + 1} (\ alfa)}$ .
• $Displaystyle C _ {\ kappa} (\ alfa) = \ bigcup \ ograniczenia _ {n <\ omega} C _ {\ kappa} ^ {n} ( \alfa )}$
• ${\ Displaystyle \ psi _ {\ kappa} (\ alfa) = \ min (\ {\ xi \ in \ kappa \ mid \xi \notin C_{\kappa }(\alpha )\})}$

ψ Jägera

ψ Jägera stworzone przez Denisa Maksudova. Liczba porządkowa jest α -słabo niedostępna, jeśli jest nieprzeliczalna, regularna i jest granicą γ -słabo niedostępnych kardynałów dla γ < α . Niech I ( α , 0) będzie pierwszym α-słabo niedostępnym kardynałem, I ( α , β + 1) będzie pierwszym α -słabo niedostępnym kardynałem po I ( α , β ) i ja ( α , β ) = ${\ Displaystyle sup (\ {ja (\ alfa, \ gamma) \ środkowy \ gamma <\ beta \})}$ dla granicy β . Ogranicz ρ i π do niezliczonych regularnych liczb porządkowych postaci I ( α , 0) lub I ( α , β + 1). Następnie,

• ${\ Displaystyle C_ {0} (\ alfa, \ beta) = \ beta \ kubek \ {0 \}}$
• ${\ Displaystyle C_ {n + 1} (\ alfa, \ beta) = \ {\ gamma + \ delta \ mid \ gamma, \ delta \in C_{n}(\alpha ,\beta )\}\cup \{I(\gamma ,\delta )\mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\} \cup \{\psi _{\pi}(\gamma)\mid \pi,\gamma,\in C_{n}(\alpha,\beta)\land \gamma <\alpha \}}$
• $\ Displaystyle C (\ alfa, \ beta) = \ bigcup \ ograniczenia _ {n <\ omega} C_ {n} (\ alfa, \ beta )}$
• ${\ Displaystyle \ psi _ {\ pi} (\ alfa) = \ min (\ {\ beta <\ pi \mid C(\alpha ,\beta )\cap \pi \subseteq \beta \})}$

Ψ Rathjena

Główny artykuł: funkcja psi Rathjena

Ψ Rathjena jest oparta na najmniej słabo zwartej liczbie kardynalnej w celu utworzenia dużych policzalnych liczb porządkowych. Dla słabo zwartego kardynała K funkcje ${\ Displaystyle M ^ {\ alfa}}$ , ${\ Displaystyle C (\ alfa, \ pi)}$ , ${\ Displaystyle \ Xi (\ alfa)}$ i ${\ Displaystyle \ Psi _ {\ pi} ^ {\ xi} (\ alfa)}$ są zdefiniowane we wzajemnej rekurencji w następujący sposób:

• ⁰ M = ${\ Displaystyle K \ cap {\ mathsf {Lim}}}$ gdzie Lim oznacza klasę granicznych liczb porządkowych.
• Dla α > 0, M ^α jest zbiorem ${\ Displaystyle \ {\ pi <K \ mid C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}}$ jest stacjonarny w ${\ Displaystyle \ pi \ ziemia \ alfa \ w C (\ alfa, \ pi) \}}$
• $}$$beta$${\ Displaystyle (\ xi, \ eta) \ rightarrow \ varphi (\ xi, \ eta)}$ zamknięciem pod dodaniem , ${\ Displaystyle \ xi \ rightarrow \ Omega _ {\ xi}}$ dane ξ < K, ${\ Displaystyle \ xi \ rightarrow \ Xi (\ xi)}$ podane ξ < α i ${\ Displaystyle (\ xi, \ pi, \ delta ) \ strzałka w prawo \ Psi _ {\ pi} ^ {\ xi} (\ delta)}$ podane ${\ Displaystyle \ xi \ równoważnik \ delta <\ alfa}$ .
• ${\ Displaystyle \ Xi (\ alfa) = \ min (M ^ {\ alfa} \ kubek \ {K \})}$ .
• dla ${\ Displaystyle \ xi \ równoważnik \ alfa$ } ${\ Displaystyle \ Psi _ {\ pi} ^ {\ xi} (\ alfa) = \ min (\ {\ rho \ w M ^ {\ xi} \ czapka \ pi: C (\ alfa, \ rho) \ czapka \pi =\rho \land \pi \land \alpha \in C(\alpha ,\rho )\}\cup \{\pi \})}$ .

Upadający wielcy kardynałowie

Jak zauważono we wstępie, użycie i definicja porządkowych funkcji załamujących jest silnie związana z teorią analizy porządkowej , więc o załamaniu tej lub innej dużej liczby kardynalnej należy wspomnieć jednocześnie z teorią, dla której dostarcza ona analizy teoretyczno-dowodowej.

• Gerhard Jäger i Wolfram Pohlers opisali upadek niedostępnego kardynała , aby opisać porządkowo-teoretyczną siłę teorii mnogości Kripkego – Plateka powiększoną o rekurencyjną niedostępność klasy liczb porządkowych ( KPi ), ​​która jest również teoretycznym dowodem dowodu ${\ Displaystyle \ Delta _ {2} ^ {1}}$ -zrozumienie plus indukcja słupkowa . Z grubsza mówiąc, to załamanie można uzyskać, dodając ${\ Displaystyle \ alfa \ mapsto \ Omega _ {\ alfa}}$$zastosowanie$ na liście konstrukcji, do których .
• Następnie Michael Rathjen opisał upadek kardynała Mahlo , aby opisać teoretyczną siłę teorii mnogości Kripkego – Plateka, wzmocnioną przez rekurencyjną Mahloness klasy liczb porządkowych ( KPM ).
• Rathjen opisał później upadek słabo zwartego kardynała $,$ aby opisać porządkowo-teoretyczną siłę teorii mnogości Kripkego – Plateka, wzmocnioną pewnymi refleksji (koncentrując się na przypadku ). Z $Mahlo$$wprowadzenie$ pierwszego kardynała, -hyper dodanie ${\ Displaystyle \ alpha \ mapsto \ Xi (\ alpha)}$ działa sama w upadającym systemie.
• W artykule z 2015 roku Toshyasu Arai stworzył porządkowe funkcje zwijania dla wektora liczb porządkowych ${\ Displaystyle \ psi _ {\ pi} ^ {\ vec {\ xi$ } $}$ zwiń ${\ Displaystyle \ Pi _ {n} ^ {1}}$ - nieopisane liczby główne dla ${\ Displaystyle n> 0}$ . Służą one do przeprowadzania analizy porządkowej teorii mnogości Kripkego – Plateka powiększonej o ${\ Displaystyle \ Pi _ {n + 2}} -$ zasady refleksji.
• Rathjen zaczął badanie upadku jeszcze większych kardynałów, którego ostatecznym celem jest osiągnięcie porządkowej analizy -zrozumienia $co$ równoważne dowodowi z augmentacją z Kripke – Platek przez ${\ Displaystyle \ Sigma _ {1}}$ -separacja).

Notatki

•   Arai, Toshiyasu (wrzesień 2020). „Uproszczona analiza porządkowa odbicia pierwszego rzędu”. Dziennik logiki symbolicznej . 85 (3): 1163–1185. ar Xiv : 1907.07611 . doi : 10.1017/jsl.2020.23 . S2CID 118940547 .
•   Takeuti, Gaisi (1967). „Dowody spójności podsystemów analizy klasycznej”. Roczniki matematyki . 86 (2): 299–348. doi : 10.2307/1970691 . JSTOR 1970691 .
• Jager, Gerhard; Pohlers, Wolfram (1983). "Eine beweistheoretische Untersuchung von ( ${\ Displaystyle \ Delta _ {2} ^ {1}}$ -CA) + (BI) i system sterowania". Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte . 1982 : 1–28.
• Buchholz, Wilfried (1986). „Nowy system teoretyczno-dowodowych funkcji porządkowych” . Roczniki czystej i stosowanej logiki . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 .
•   Rathjen, Michael (1991). „Dowód-teoretyczna analiza KPM”. Archiwum logiki matematycznej . 30 (5–6): 377–403. doi : 10.1007/BF01621475 . S2CID 9376863 .
• Rathjen, Michael (1994). „Dowód teorii odbicia” (PDF) . Roczniki czystej i stosowanej logiki . 68 (2): 181–224. doi : 10.1016/0168-0072(94)90074-4 .
•    Rathjen, Michael (1995). „Ostatnie postępy w analizie porządkowej: ${\ Displaystyle \ Pi _ {2} ^ {1}}$ -CA i systemy pokrewne” . Biuletyn logiki symbolicznej . 1 (4): 468–485. doi : 10.2307/421132 . JSTOR 421132 . S2CID 10648711 .
•   Kahle, Reinhard (2002). „Matematyczna teoria dowodu w świetle analizy porządkowej”. synteza . 133 : 237–255. doi : 10.1023/A:1020892011851 . S2CID 45695465 .
•    Rathjen, Michael (2005). „Porządkowa analiza stabilności” . Archiwum logiki matematycznej . 44 : 1–62. CiteSeerX 10.1.1.15.9786 . doi : 10.1007/s00153-004-0226-2 . S2CID 2686302 .
• Rathjen, Michael (sierpień 2005). „Teoria dowodu: część III, teoria mnogości Kripkego – Plateka” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 12.06.2007 . Źródło 2008-04-17 . (slajdy z wykładu wygłoszonego w Fischbachau)