{{TIN065 Prednášky}} Táto prednáška sa venovala triede nekonečných vetiev skrz rekurzívne stromy (\Pi^0_1 triedy). Najprv si zavedieme niekoľko pojmov.

Strom v našom prípade budeme chápať ako množinu reťazcov/retiazkov/postupností (string) prirodzených čísel, pre ktoré niečo platí.

Ako 2^{<\omega} si označíme práve všetky konečné reťazce (postupnosti) z množiny \{0, 1\} (nula-jedničkové reťazce). Podobne 2^{\omega} si môžeme označiť nekonečné postupnosti núl a jedničiek (to sú vlastne podmnožiny \mathbb{N} - charakteristické funkcie). Rovnako máme \omega^{<\omega} a \omega^{\omega} - konečné a nekonečné postupnosti prirodzených čísel. My sa budeme zaoberať 2^{<\omega}.

Ešte si o 2^{\omega} povieme, že je to Cantorov priestor - úplný metrický kompaktný priestor, kde je metrika \rho(f,g) = 2^{-x_0}, kde x_0 je najmenšie také x, že f(x)\neq g(x) (ak také x neexistuje, tak vzdialenosť je samozrejme nulová) - na retiazky/postupnosti sa dívame ako na funkcie do \{0, 1\}. Čím dlhšie sú retiazky rovnaké, tým bližšie sú k sebe.

2^{<\omega} strom je podmnožiná 2^{<\omega} uzavretá na počiatočné segmenty: Je to T, pre ktoré platí: ak \sigma \in T a \tau \leq \sigma (tu má byť predchodca: \prec), tak \tau \in T. Zodpovedá to našej predstave o stromoch. Predstavíme si množinu ako klasický binárny strom, kde nulou ideme napríklad vľavo a jedničkou vpravo a tak skladáme reťazec. Ak sme nejaký poskladali, tak vieme poskladať aj všetky kratšie.

Naše stromy sú binárne. Keby sme sa zaoberali \omega^{\omega}, tak by sme mali nekonečne vetviace sa stromu a s tým by sa horšie pracovalo.

A už si môžeme povedať, čo je to rekurzívny strom. Zrejme je to strom, ktorý je rekurzívny: Keďže strom je množina, tak je to rekurzívna množina, pre ktorú platí pravidlo o počiatočných segmentoch. To, že je rekurzívna znamená, že dokážem algoritmicky rozhodnúť, či \sigma \in T.

Ďalej si povieme, čo sú \Pi^0_1 triedy množín (alebo charakteristických, nula-jedničkových, funkcií). Sú to práve tie triedy funkcií, ktoré sú triedami všetkých nekonečných vetiev skrz nejaký rekurzívny strom. Ak máme strom T, tak f je nekonečná vetva skrz/na/v T a k pre \forall n: f \upharpoonright n \in T, kde f \upharpoonright n je f parcializované na počiatočný úsek dĺžky n (proste z f vezmeme len počiatočný úsek).

Prečo sa to volá \Pi^0_1? Práve kvôli vyjadreniu nekonečných vetiev: \{f: \forall n (f \upharpoonright n \in T)\}, kde máme jeden kvantifikátor na rekurzívnu podmienku (T je rekurzívny strom).

Odbočka: Dajú sa zaviesť aj ostatné triedy nula-jedničkových funkcií (\Sigma^0_0 = \Pi^0_0, \Sigma^0_N a \Pi^0_N), ale tými sa teraz nebudeme zaoberať.

T = 2^{<\omega} má nespočetne mnoho rekurzívnych vetiev. (?)

A teraz sa pomaly prenesieme do logiky. Majme rozumnú teóriu prvého rádu, ktorá je axiomatizovateľná. Rozumná bude znamenať s rozumným jazykom, napríklad takým, ktorý má konečne mnoho symbolov, (vhodná je napríklad niektorá z aritmetík) a konečne axiomatizovateľná znamená, že vlastnosť "dá sa dokázať" je rekurzívne spočetná (viem generovať dôkazy programom). Tvrdenie je, že množina všetkých úplných (kompletných) rozšírení je \Pi^0_1. (ak vezmem nejakú teóriu, tak má svoje rozšírenia a ich množina je \Pi^0_1.

Majme axiomatizovateľnú teóriu prvého rádu R. Chceme vytvoriť rekurzívny strom T, ktorého nekonečné vetvy budú práve všetky kompletné rozšírenia R. Začnem teda do stromu T pridávať reťazce \alpha a to tak, že \alpha \in T práve vtedy, keď \alpha je bezosporné za |\alpha| krokov a je kompatibilné s tým, čo sa v R za |\alpha| krokov dokáže. Takže \alpha, ktoré ohodnocuje prvých |\alpha| formulí (priradí im nulu alebo jedničku) necháme žiť na strome, ak to ohodnotenie je bezosporné a ak pre formulu j <|\alpha|, ak sa za |\alpha| krokov dokáže, tak \alpha(j) musí byť jednička a ak vyvráti, tak \alpha(j) musí byť nula.

Takéto \alpha je nádejný začiatok kompletného rozšírenia R za |\alpha| krokov (je stále bezosporný a súhlasí s tým, čo je v R).

T je rekurzívny strom (pre \alpha je to, že je v strome, rekurzívna podmienka).

Platí: trieda \{f: \forall n (f\upharpoonright n \in T) \}, čo sú práve všetky nekonečné vetvy skrz T, sú práve všetky kompletné rozšírenia R.

Dôkaz: Jedným smerom: Ak f je kompletné rozšírenie teórie R, tak je nádejné za každý počet krokov, takže ho necháme na strome žiť. Druhým smerom: ak mám nekonečnú vetvu, ktorá prežila na strome, tak bola nádejná pre každé n, a preto je kompletným rozšírením. Alebo sporom: Ak niečo nie je kompletné rozšírenie, tak existuje n, kde sa dohrabeme ku sporu a za toto n už tú vetvu nepotiahneme (ďalej už na strome neprežije).

Takže rozšírenia sú \Pi^0_1.

Iná oblasť. Majme dve rekurzívne spočetné, disjunktné množiny A a B. Ak vezmeme Sep(A, B), čo je množina separujúcich funkcií \{f: \forall x (x\in A \implies f(x)=1 \And x\in B \implies f(x)=0\} , tak táto je tiež \Pi^0_1. Dôkaz sa opäť vyrobí cez nádejný reťazec \alpha, ktorý separuje A_s a B_s, kde s = |\alpha| a A_s znamená množinu A za s krokov (a \alpha separuje, ak separuje pre každý počet krokov).

Tak si vezmime efektívne neoddeliteľné A a B (stále rekurzívne spočetné). Tvrdíme, že Sep(A, B) nemá žiadnu nekonečnú rekurzívnu vetvu (tu mám napísané "lebo efektívna neoddeliteľnosť implikuje rekurzívnu neoddeliteľnosť". Sep(A, B) bude neprázdna \Pi^0_1 trieda s nespočetne veľa prvkami, ale so žiadnym rekurzívnym. Dostaneme tu nekonečný rekurzívny strom, ktorého žiadna nekonečná vetva nebude rekurzívna - nebude sa dať efektívne nájsť. Ak som to dobre pochopil, tak ak sa postavíme do koreňa stromu a budeme mať program, ktorý nám bude hovoriť v každom uzle, či máme ísť vľavo alebo vpravo, tak vždy skončíme na nejakej konečnej vetve, aj keď nekonečných je nespočetne veľa.

Königová lema: Binárny strom je nekonečný práve vtedy, keď obsahuje nekonečnú vetvu. Jedným smerom dokázať je to triviálne (ak má nekonečnú vetvu, tak je nekonečný). Opačným: Vezmem oba podstromy koreňa: Ak by boli oba konečné, tak celý strom je konečný, takže aspoň jeden je nekonečný. Tak si ho vezmem a ziterujem to - takto nájdem nekonečnú vetvu. (spomínate si na tvrdenie z analýzy, že každá obmedzená postupnosť má hromadný bod?). Toto však nie je efektívny spôsob hľadania nekonečnej vetvy.

Ak T rekurzívny strom, aká zložitá je otázka, či jeho podstrom T_1 je (ne)konečný? Prepíšeme si otázku: Existuje hĺba, že všetko v T_1 v tejto hĺbke umrie? Alebo: \exists h : \forall \alpha (|\alpha| = h \implies \alpha \notin T_1)? Kvantifikátor na \alpha je obmedzený, takže je to \Sigma_1 otázka. A na tú ám vie odpovedať starý známy halting problém (\emptyset^{\prime}).

"Inšpekcia dôkazu königovej lemy ukazuje, že nekonečný rekurzívny strom má nekonečnú vetvu, ktorá je rekurzívna v \emptyset^{\prime}." \emptyset^{\prime} nám vie nájsť cestu cez binárny strom (binárne bludisko). Je to guide. Príklad: existuje kompletné rozšírenie Peanovej aritmetiky, ktoré je rekurzívne v \emptyset^{\prime} (ale divoké).

(tu bola nejaká odbočka, ktorá vravela, že z kompletného rozšírenia môžeme vyrobiť model)

Otázka: Aké sú T-stupne, (informácie), ktoré sú takéto "guide"? Chcem \[a] (tu má byť a s vlnovkou pod sebou) také, že pre každý nekonečný rekurzívny strom T existuje nekonečná vetva f v ňom a \deg(f) \leq \[a]. \[a] je informácia, ktorá nájde cestu v ľubovoľnom nekonečnom rekurzívnom strome. Vieme, že \emptyset^{\prime} stačí.

Veta: Nasledujúce tvrdenia sú ekvivalentné:

#\[a] je kompletné rozšírenie Peanovej alebo Robinzonovej aritmetiky alebo základnej aritm. sily (axiomatizovateľnej teórie s minimálnou aritmetickou silou) #\[a] je stupeň množiny separujúcej nejakú efektívne neoddeliteľnú dvojicu rekurzívne spočetných množín.

#\[a] je guide (v každom nekonečnom rekurzívnom strome existuje nekonečná vetva f a \deg(f) \leq \[a]

Zaujímavé je, že sú aj také \[a], ktoré sú ostro menšie ako \emptyset^{\prime} a to hodne nižšie.

Ukázali sme si, že štandardná teória prvého rádu má blízko k štandardnej vyčísliteľnosti a že spolu tesne súvisia. Ak sa ide z vyčísliteľnosti nižšie (do polynomiálnej hierarchie), tak nám vznikajú malé logiky s polynomiálnou nájditeľnosťou (dôkazu(?)). Tiež sme sa pokúsili ukázať, ako nekonečné vetvy súvisia s logikou a ako nájsť nekonečnú vetvu a čo na to stačí.

(Nabudúce budú 1-generické množiny a aritmetický forcing.)