Nierekurencyjna liczba porządkowa

W matematyce, zwłaszcza w teorii mnogości, nierekurencyjne liczby porządkowe są dużymi policzalnymi liczbami porządkowymi większymi niż wszystkie rekurencyjne liczby porządkowe, a zatem nie można ich wyrazić za pomocą porządkowych funkcji zwijających .

Porządkowa Church-Kleene i warianty

Najmniejszą nierekurencyjną liczbą porządkową jest liczba porządkowa Church Kleene $nazwana$ na Churcha i Kleene ; jego typem porządku jest zbiór wszystkich rekurencyjnych liczb porządkowych . Ponieważ następnik rekurencyjnej liczby porządkowej jest rekurencyjny, liczba porządkowa Churcha-Kleene'a jest liczbą porządkową graniczną . Jest to również najmniejsza liczba porządkowa, która nie jest hiperarytmetyczna i najmniejsza dopuszczalna liczba porządkowa po ω (liczba porządkowa α nazywana jest dopuszczalną, jeśli ${\ Displaystyle L _ {\ alfa} \ modele {\ mathsf {KP}}}$ .) ${\ Displaystyle \ omega _ {1} ^ {\ mathsf {CK}}}$ -rekurencyjne podzbiory ω są dokładnie podzbiorami ω $\ Displaystyle \ Delta _ {1} ^ {1}}$ {

Notacja odnosi się do $jak$ , pierwszej niepoliczalnej liczby porządkowej , zbiorem wszystkich policzalnych liczb porządkowych, analogicznie do tego ,
_Kościół -Kleene porządkowa to zbiór wszystkich rekurencyjnych liczb porządkowych.

Zrelatywizowana liczba porządkowa Churcha-Kleene'a $supremum$ liczb porządkowych x-

$\ Displaystyle \ omega _ {\ omega} ^ {\ mathsf {CK}}}$ , po raz pierwszy zdefiniowany przez Stephena G. Simpsona i nazwany „Ordinal Great Church – Kleene” jest rozszerzeniem Porządkowy Church-Kleene. Jest to najmniejsza granica dopuszczalnych liczb porządkowych, ale ta liczba porządkowa jest niedopuszczalna. Alternatywnie, jest to najmniejsza α taka, że ${\ Displaystyle L _ {\ alfa} \ cap {\ mathsf {P}} (\ omega)}$ jest modelem ${\ Displaystyle \ Pi _ {1} ^ {1}}$ -zrozumienie .

Liczby porządkowe rekurencyjnie

rekurencyjnie „ x” , gdzie „x” zazwyczaj reprezentuje dużą właściwość kardynalną , to rodzaje nierekurencyjnych liczb porządkowych.

Liczba porządkowa $dopuszczalna$$jeśli jest$ rekurencyjnie niedostępną $liczba$ i granica dopuszczalnych ( to dopuszczalna porządkowa). Alternatywnie, jest rekurencyjnie niedostępny, jeśli , rozszerzenie teorii $mnogości$ Kripkego – Plateka w modelu Teoria mnogości Kripkego – Plateka, liczba porządkowa $($${ \mathsf {P}} (\ omega)}$$P$ ω ) { $\$ jest modelem -zrozumienia $_ {2} ^ {1}}$ Delta

Liczbę porządkową $,$ się rekurencyjnie hiperniedostępną jeśli jest rekurencyjnie niedostępna i granica rekurencyjnie niedostępnych, lub $gdzie$ jest $niedostępna$ Podobnie jak „hiper-niedostępny kardynał”, różni autorzy spierają się co do tej terminologii.

Porządkowa jest nazywana rekurencyjnie Mahlo $f: \ alpha \ rightarrow \ alpha}$ jeśli jest dopuszczalna i dla dowolnej -rekurencyjnej funkcji $Displaystyle$$\ displaystyle$ istnieje α { dopuszczalne ${\ Displaystyle \ beta <\ alfa}$ takie, że ${\ displaystyle f}$$\ beta \ prawo \} \ subseteq \ beta}$$($ to znaczy, że jest zamknięty pod ) . Odzwierciedlając hierarchię Mahlonessa , jest rekurencyjnie ${\ displaystyle \ gamma}$ dla $-Mahlo$ liczby porządkowej $}$ jeśli jest dopuszczalna i dla dowolnej -rekurencyjnej funkcji $alpha$$Displaystyle f: \ alpha \ rightarrow \ alpha}$ \ $}$$dopuszczalna$ liczba porządkowa , że ​​jest zamknięta pod $displaystyle$ i jest rekurencyjnie ${\ displaystyle$$\ delta}$ -Mahlo dla wszystkich $\ gamma}$ .

Liczbę porządkową $,$ się rekurencyjnie słabo zwartą jeśli jest $-odzwierciedlająca$ lub równoważnie 2- $-Mahlo$$,$ rekurencyjne właściwości Mahlonessa, jeśli - $odzwierciedlając$ to jest

Osłabienia stałych liczb porządkowych

Liczba porządkowa jest stabilna, jeśli $Displaystyle L _ {\ alpha} \ preceq$${1} L}$ . Są to jedne z największych nazwanych nierekurencyjnych liczb porządkowych pojawiających się w kontekście teorii modeli, na przykład większe niż ${\ Displaystyle \ min \ {\ alfa: L _ {\ alfa} \ modele T \} }$ dla dowolnej obliczalnie aksjomatyzowalnej teorii ${\ displaystyle T}$ . ^{Propozycja 0.7} . Istnieją różne osłabienia stabilnych liczb porządkowych:

• Nazywa się policzalną liczbę porządkową $\ Displaystyle$$(+1)}$ -stabilna iff ${\ Displaystyle L _ {\ alfa} \ preceq _ {1} L_ {\alfa +1}}$ .
  • Najmniejsza -stabilna liczba $porządkowa jest znacznie większa niż najmniejsza rekurencyjnie słabo$ liczba porządkowa: wykazano, że najmniejsza $\ Displaystyle (+1)}$ porządkowa Π ${\ displaystyle \ Pi _ {n}}$ - odzwierciedla dla wszystkich skończonych $n}$ .
  • ${\ Displaystyle$ liczba porządkowa nazywa się $(+ \ beta)}$ -stabilna iff ${\ Displaystyle L _ {\ alfa} \ preceq _ {1}L_{\alfa +\beta}}$ .
• ${\ Displaystyle$ liczba porządkowa nazywa się $(^ {+})}$ -stabilna iff ${\ Displaystyle L _ {\ alfa} \ preceq _ {1} L_ {\ alfa ^ {+}}}$${\ displaystyle > \ beta}$ gdzie $jest$ dopuszczalną liczbą porządkową . najmniejszy ${\ Displaystyle (^ {+})}$ -stabilna liczba porządkowa jest ponownie znacznie większa niż najmniejsza -stabilna lub najmniejsza $}$$\ Displaystyle$ -stabilna dla dowolnej stałej $Displaystyle \ beta }$ .
• Nazywa się policzalną liczbę porządkową $-stabilną$ iff $1} L _ {\ alfa ^ {++}}}$$Displaystyle$$L _ {\ alfa}$ , gdzie ${\ Displaystyle \ beta ^ {++}}$ to dwie najmniejsze dopuszczalne liczby porządkowe ${\ Displaystyle > \ beta}$ . najmniejszy ${\ Displaystyle (^ {++})} -$$odzwierciedlająca$ liczba porządkowa jest większa niż .
• Policzalna liczba porządkowa nazywana jest niedostępnie stabilną iff $}$${\ Displaystyle L _ {\ alfa} \ preceq _ {1} L _ {\ beta}}$ , gdzie $}$$\ Displaystyle \ beta$ to najmniejsza rekurencyjnie niedostępna liczba porządkowa ${\ Displaystyle > \ alpha}$ . Najmniejsza niedostępna stabilna liczba porządkowa jest większa niż najmniejsza - ${\ Displaystyle (^ {++})}$ .
• $}$ liczba porządkowa nazywana jest Mahlo-stabilna iff ${\ Displaystyle L _ {\ alfa} \ preceq _ {1} L_ {\ beta}}$ , gdzie $}$${\ Displaystyle \ beta$ jest najmniejszym rekurencyjnie porządkowym Mahlo ${\ Displaystyle > \ alpha}$ . Najmniejsza stabilna liczba porządkowa Mahlo jest większa niż najmniejsza niedostępna stabilna.
• ${\ Displaystyle$ liczba porządkowa jest nazywana podwójnie $(+1)}$ -stabilna iff ${\ Displaystyle L _ {\ alfa} \ preceq _{1}L_{\beta }\preceq _{1}L_{\beta +1}}$ . Najmniejsza podwójnie $porządkowa$ większa niż najmniejsza stabilna Mahlo

Większe nierekurencyjne liczby porządkowe

• Najmniej porządkowy taki, że $}$${\ Displaystyle L _ {\ alfa} \ preceq _ {1} L_ {\ beta$$}$ jest nieprzerzutowym porządkowy.
• Liczby porządkowej $jest$$liczb$$,$ jeśli -stabilnych porządkowych lub; jeśli zestaw ${\ Displaystyle X = \ lewo \ {\ beta <\ alfa \ mid L_ {\ beta} \ preceq _ {1} L _ {\ alfa} \ prawo\}}$ jest nieograniczone w ${\ displaystyle \ alpha}$ .
• Liczba porządkowa analizy rozgałęzionej, często $zapisywana$ . Jest to najmniejszy taki, że $Displaystyle$$L _ {\ beta} \ cap {\ mathsf {P}} (\ omega)}$ jest modelem rozumienia rzędu ${\ Displaystyle L _ {\ beta} \ modele {\ mathsf {ZFC ^ {-}}$ } } ${\ Displaystyle {\ mathsf {ZFC}}}$ bez aksjomatu powerset.
• Najmniej porządkowy $alfa$ , że $} \ modele {\ mathsf {KP}} + '\ omega _ {1} {\ textrm {istnieje}}'}$ . Ta liczba porządkowa została scharakteryzowana przez Toshiyasu Arai.
• Najmniej porządkowy $taki$ , że ${\ Displaystyle L _ {\ alfa} \ modele {\ mathsf {ZFC ^ {-}}} + '\$ .
• Najmniej stabilna liczba porządkowa.

•   Kościół, Alonzo ; Kleene SC (1937), "Definicje formalne w teorii liczb porządkowych.", Fundamenta Mathematicae, Warszawa , 28 : 11–21, doi : 10.4064/fm-28-1-11-21 , JFM 63.0029.02
• Church, Alonzo (1938), „Konstruktywna druga klasa liczbowa” , Bull. Amer. Matematyka soc. , 44 (4): 224–232, doi : 10.1090/S0002-9904-1938-06720-1
•    Kleene, SC (1938), „O zapisie liczb porządkowych”, Journal of Symbolic Logic , tom. 3, nr 4, 3 (4): 150–155, doi : 10.2307/2267778 , JSTOR 2267778 , S2CID 34314018
•   Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability , pierwsze wydanie prasowe MIT w miękkiej oprawie, ISBN 978-0-262-68052-3
•   Simpson, Stephen G. (2009) [1999], Podsystemy arytmetyki drugiego rzędu , Perspektywy w logice, tom. 2, Cambridge University Press, s. 246, 267, 292–293, ISBN 978-0-521-88439-6
•   Richtera, Wayne'a; Aczel, Peter (1974), Definicje indukcyjne i odzwierciedlające właściwości dopuszczalnych liczb porządkowych , s. 312–313, 333, ISBN 0-7204-2276-0