{{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

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 $\emptyset^{\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 $\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.)