{{TIN065 Prednášky}} Táto prednáška sa venovala triede nekonečných vetiev skrz rekurzívne stromy (${\Pi }_1^0$ 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)\ne 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 \le \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 }_1^0$ 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 }_1^0$? 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 }_N^0$ a ${\Pi }_N^0$), 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 }_1^0$. (ak vezmem nejakú teóriu, tak má svoje rozšírenia a ich množina je ${\Pi }_1^0$.

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 }_1^0$.

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⟹f(x)=1\&x\in B⟹f(x)=0\}$ , tak táto je tiež ${\Pi }_1^0$. 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 }_1^0$ 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⟹\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 (${\varnothing }^{\prime }$).

"Inšpekcia dôkazu königovej lemy ukazuje, že nekonečný rekurzívny strom má nekonečnú vetvu, ktorá je rekurzívna v ${\varnothing }^{\prime }$." ${\varnothing }^{\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 ${\varnothing }^{\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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 14: \deg(f) \leq \̲[̲a]

.

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

je informácia, ktorá nájde cestu v ľubovoľnom nekonečnom rekurzívnom strome. Vieme, že ${\varnothing }^{\prime }$ stačí.

Veta: Nasledujúce tvrdenia sú ekvivalentné:

#

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

je kompletné rozšírenie Peanovej alebo Robinzonovej aritmetiky alebo základnej aritm. sily (axiomatizovateľnej teórie s minimálnou aritmetickou silou) #

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

je stupeň množiny separujúcej nejakú efektívne neoddeliteľnú dvojicu rekurzívne spočetných množín.

#

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

je guide (v každom nekonečnom rekurzívnom strome existuje nekonečná vetva $f$ a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 14: \deg(f) \leq \̲[̲a]

Zaujímavé je, že sú aj také

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

, ktoré sú ostro menšie ako ${\varnothing }^{\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.)