Kleene O

W teorii mnogości notacje jest $kanonicznym$ teorii obliczalności Kleene podzbiorem liczb naturalnych traktowanych jako porządkowe . Zawiera notacje porządkowe dla każdej obliczalnej liczby porządkowej , to znaczy liczb porządkowych poniżej liczby porządkowej Churcha-Kleene'a , ${\ Displaystyle \ omega _ {1} ^ {\ tekst {CK}}}$ . Ponieważ ${\ Displaystyle \ omega _ {1} ^ {\ tekst {CK}}}$ jest pierwszą liczbą porządkową, której nie można przedstawić w obliczalnym systemie notacji porządkowej, elementy można uznać za ${\ Displaystyle {\ mathcal {O}}}$ kanoniczne notacje porządkowe.

Kleene (1938) opisał system notacji dla wszystkich policzalnych liczb porządkowych (mniejszych niż liczba porządkowa Churcha-Kleene'a ). Wykorzystuje podzbiór liczb naturalnych zamiast skończonych ciągów symboli. Niestety, na ogół nie ma skutecznego sposobu stwierdzenia, czy jakaś liczba naturalna reprezentuje liczbę porządkową, czy też dwie liczby reprezentują tę samą liczbę porządkową. Jednak można skutecznie znaleźć notacje reprezentujące sumę porządkową, iloczyn i potęgę (patrz arytmetyka porządkowa ) dowolnych dwóch podanych notacji w Kleene's ${\ displaystyle {\ mathcal {O}}}$ ; a biorąc pod uwagę dowolną notację dla liczby porządkowej, istnieje przeliczalny zestaw notacji, który zawiera jeden element dla każdej mniejszej liczby porządkowej i jest efektywnie uporządkowany.

Definicja

Podstawową ideą systemu notacji porządkowych Kleene'a jest efektywne budowanie liczb porządkowych. Dla członków O $\ displaystyle {\$$,$${O}}}$ liczba porządkowa, dla której jest notacją ${\ displaystyle | p |}$ . ${\ mathcal {O}}$$i$ ( częściowe uporządkowanie Kleene'a ${\ displaystyle {\ mathcal {O}}}$ ) to najmniejsze zestawy, takie, że następujące.

• ${\ Displaystyle 0 \ w {\ mathcal {O}} \ ziemi | 0 | = 0}$ .
• ${\ Displaystyle i \ w {\ mathcal {O}} \ ziemia |i | = \ alfa \ rightarrow 2 ^ {i} \ w {\ mathcal {O}} \ ziemia | 2^{i}|=\alpha +1\land i<_{\mathcal {O}}2^{i}}$
• Załóżmy, $.$ -tą $\ displaystyle e}$ obliczalną funkcją mi mi ${\ displaystyle e} jest$ i ${\ Displaystyle {\ textrm {zakres}} (\ {e \}) \ podzbiór {\ mathcal {O}} \ ziemia \ forall n (\ {e \} (n) <_ {\ mathcal {O}} \ {e\}(n+1))}$ , wtedy ${\ Displaystyle 3 \ cdot 5 ^ {e} \ in {\ mathcal {O}} \ ziemia \ forall n, \ {e \} (n) <_ {\ mathcal {O}} 3 \ cdot 5 ^ {e }\land |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}$
• ${\ Displaystyle p <_ {\ mathcal {O}} q \ ziemia q <_ {\ mathcal {O}} r \ rightarrow p <_ {\ mathcal { Lub}$

$)$ poprzedników danej liczby porządkowej (choć nie w porządku że notacje są zamknięte w dół, tj. gdzie $}$ notacja dla i jest notacja dla $\ alpha <\ gamma$$displaystyle$ \ Istnieją alternatywne definicje, takie jak zestaw wskaźników (częściowych) uporządkowań liczb naturalnych.

Podstawowe właściwości < _O

• Jeśli ${\ Displaystyle | i | = \ alfa}$ i ${\ Displaystyle | j | = \ beta}$ i ${\ Displaystyle i <_ {\ mathcal {O}} j \ ,}$ wtedy ${\ Displaystyle \ alfa <\ beta}$ ; ale odwrotność może się nie udać.
• ${\ Displaystyle <_ {\ mathcal {O}}}$ indukuje strukturę drzewa na ${\ Displaystyle {\ mathcal {O}}}$ , więc ${\ Displaystyle {\ mathcal {O}}}$ jest dobrze uzasadniony .
• ${\ Displaystyle {\ mathcal {O}}}$ rozgałęzia się tylko na granicznych liczbach porządkowych; a przy każdym zapisie granicznej liczby porządkowej $się$ w nieskończoność.
• Ponieważ każda obliczalna funkcja ma przeliczalnie wiele indeksów, każda nieskończona liczba porządkowa otrzymuje przeliczalnie wiele zapisów; skończone liczby porządkowe mają unikalne oznaczenia, $\ displaystyle n _ {\ mathcal {O}}}$ oznaczane ${$ .
• Pierwsza liczba porządkowa, która nie otrzymuje notacji, nazywana jest liczbą porządkową Churcha-Kleene'a i jest oznaczona przez ${\ displaystyle \ omega _ {1} ^ {\ tekst {CK}}}$ . Ponieważ istnieje tylko przeliczalnie wiele funkcji obliczalnych, liczba $policzalna$ .
• Liczby porządkowe z notacją w Kleene'a $są$ policzalnymi liczbami porządkowymi . (Fakt, że każda obliczalna liczba porządkowa ma notację, wynika z zamknięcia tego systemu notacji porządkowej pod następnikami i efektywnymi granicami).
• ${\ Displaystyle <_ {\ mathcal {O}}}$ nie jest obliczalnie przeliczalny , ale istnieje obliczalnie przeliczalna relacja, która zgadza się z ${\ displaystyle <_ {\ mathcal {O}}}$ dokładnie na elementach ${O}}}$ mathcal
• ${\ displaystyle p}$ zestaw notacji ${\ displaystyle \ lbrace q \ mid q <_ {\ mathcal {$ } $} }$ jest przeliczalny. Jednak Kleene'a $, rozpatrywana$ jako całość, jest (patrz hierarchia analityczna $i$ z następujące:
• W rzeczywistości jest kompletny i każdy ${$$\ Displaystyle \ Pi _ {1} ^ {1}}$$}$${\ Displaystyle \ Sigma _ {1}$$.$ podzbiór $jest$ skutecznie ograniczony w (wynik Spectora
• $.$ uniwersalnym systemem notacji porządkowych w tym sensie, że każdy określony zestaw notacji porządkowych można w nim odwzorować w prosty sposób Dokładniej, istnieje obliczalna funkcja $taka$ , że ​​jeśli $indeksem$ dla obliczalnego uporządkowania, to jest członkiem $(e)}$${\ Displaystyle {\ mathcal {O}}}$ i ${\ Displaystyle <_ {e}}$ jest rzędu izomorficzne z początkowym segmentem zbioru ${\ Displaystyle \ {p \ mid p <_ {\ mathcal {O}} f (e) \}}$ .
• Istnieje obliczalna funkcja $+$ która dla członków $naśladuje$ dodawanie porządkowe i ma właściwość ${\ Displaystyle \ max \ {p, q \} \ równoważnik p + _ {\ mathcal {O}} q}$ . (Jockusch)

Właściwości ścieżek w < _O

Ścieżka w $O$ podzbiorem ${\ Displaystyle {\ mathcal {$$}}$ , który jest całkowicie uporządkowany przez $}}$$\ Displaystyle {\ mathcal {P}}}$ i jest zamknięty pod poprzednikami, tj. jeśli jest członkiem ścieżki ${$ i ${\ displaystyle q <_ {\ mathcal {O}} p},$ a następnie ${\ displaystyle q}$ jest również członkiem ${\ displaystyle {\ mathcal {P}}}$ . Ścieżka ${\ displaystyle <_ {}} \mathcal {O}}}$ jeśli nie ma elementu $, który znajduje$ w sensie ${\ displaystyle$$każdy$$jest$ , w przeciwnym razie nie maksymalny.

• Ścieżka nie $przeliczalna$ maksymalna wtedy i tylko wtedy, gdy $jest$ obliczeniowo (ce) Z powyższych uwag wynika, że ​​każdy element O $\ Displaystyle$${\ mathcal {O}}}$ określa niemaksymalną ścieżkę ${\ displaystyle {\ mathcal {P}}$ ; i każda niemaksymalna ścieżka jest tak określona.
• Istnieją maksymalne ścieżki przez ${\ Displaystyle 2 ^ {\ aleph _ {0}$$}$ ; ponieważ są maksymalne, nie są ce
• $}$ rzeczywistości istnieją maksymalne ścieżki w obrębie długości $^ {\ aleph _ {0}$$\ Displaystyle$ . (Crossley, Schütte)
• Dla każdej niezerowej liczby porządkowej istnieją maksymalne ścieżki ${0}$$Displaystyle 2 ^ {\$ w ${$ długości $\ Displaystyle \ omega ^ {2} \ cdot \ lambda}$ . (Acel)
• Ponadto, jeśli jest ścieżką, której długość nie jest wielokrotnością $},$$to$ P $\ Displaystyle {\ displaystyle {\ mathcal {P}}}$ nie jest maksymalna. (Acel)
• $\ Displaystyle {\ mathcal {P}} = \ lbrace p \ mid p <_ {\ mathcal {O}} e_ {d} \ rbrace} ma wiele jeden stopień re {\$ każdego stopnia ce $członek$ O $\ Displaystyle$$mathcal {O}}} taki$ że ścieżka mi re { displaystyle $}$ . W rzeczywistości dla każdej obliczalnej liczby porządkowej ${\ Displaystyle \ alfa \ geq \ omega ^ {2}}$ notacja $\ Displaystyle e_ {d}}$ istnieje z ${\ Displaystyle | e_ {d} | = \ alfa}$ . (Jockusch)
• Istnieją ${1}$ przez $}$ są ${\ Displaystyle \ Pi _ {1} ^$ . Biorąc $pod$ postęp obliczalnie policzalnych teorii opartych na iteracyjnym jednolitym odbiciu, każda taka ścieżka jest niekompletna w odniesieniu do zbioru prawdziwych . (Feferman & Spector)
• Istnieją ścieżki $,$$każdy$ segment jest nie tylko ce, ale (Jockusch)
• Wykazano, że istnieją różne inne ścieżki , $z których każda ma określone$ (Zobacz referencje poniżej)

Zobacz też

• Obliczalna liczba porządkowa
• Duża policzalna liczba porządkowa
• Notacja porządkowa

• 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”, The Journal of Symbolic Logic , Association for Symbolic Logic , 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
•    Feferman, Salomon; Spector, Clifford (1962), „Niekompletność wzdłuż ścieżek w postępach teorii”, Journal of Symbolic Logic , 27 (4): 383–390, doi : 10,2307/2964544 , JSTOR 2964544 , S2CID 33892829