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