TIN065 Prednáška 09
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
|
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.)
