{{TIN065 Prednášky}}

Vieme klasifikovať množiny a predikáty podľa ich aritmetického tvaru. Triedime ich do skupín ${\Sigma }_n$ a ${\Pi }_n$ podľa ich prefixu. Keď urobíme zjednotenie cez všetky $n$, dostaneme aritmetickú hierarchiu.

Tiež vieme, že ${\Sigma }_0={\Pi }_0$ nemajú univerzálny ${\Sigma }_0$ (ani ${\Pi }_0$) predikát, ale vyššie už univerzálny predikát máme. Tým máme výhodu oproti zložitosti a ich polynomiálnej hierarchii pretože tam nemajú univerzálny polynóm. Tiež ešte vieme, že ${\Sigma }_n-{\Pi }_n$ je neprázdne.

Minule sme si definovali ${\Sigma }_n$ úplnosť a povedali si vetu o hierarchii, tak ich tu skopírujem:

${\Sigma }_n$úplnosť :: A je ${\Sigma }_n$ úplná ak je v ${\Sigma }_n$ a hocijaká B zo ${\Sigma }_n$ sa dá 1-previesť na A.

Veta o hierarchii:

#$\forall n\ge 1:{\varnothing }^n$ je ${\Sigma }_n$ úplná. #A je rekurzívne spočetná v ${\varnothing }^n⟺A\in {\Sigma }_{n+1}\forall n\ge 0$

#$A{\le }_T{\varnothing }^n⟺A\in {\Sigma }_{n+1}\cap {\Pi }_{n+1}$

Táto veta nám zväzuje aritmetickú hierarchiu s operáciou skoku.

Dôkaz: Časť 3 vyplýva z časti 2 a z postovej vety. Majme množinu A:

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 47: …, \overline{A} \̲m̲b̲o̲x̲{ sú rekurzívne…

. Prvá ekvivalencia je z postovej vety, druhá z časti 2 tejto vety a tretia z toho, že ak $A\in {\Sigma }_n$, tak $\overline{A}\in {\Pi }_n$.

Je možné sa niekedy stretnúť so značením ${\Delta }_n$. To je synonymum pre ${\Sigma }_n\cap {\Pi }_n$.

Časť 1 opäť vyplýva z časti 2. Pre $n\ge 1$ je ${\varnothing }^{(n)}$ rekurzívne spočetné v ${\varnothing }^{(n-1)}$ kvôli operácii skoku a podľa druhej časti vety je v ${\Sigma }_n$. Opačným smerom ak máme niečo v ${\Sigma }_n$, tak podľa časti 2 je to rekurzívne spočetné v ${\varnothing }^{(n-1)}$ a podľa vlastnosti skoku je to 1-prevoditeľné na ${\varnothing }^{(n)}$.

Takže nám treba dokázať druhú časť vety o hierarchii. To sa urobí indukciou podľa $n$. Pre $n=0$ to vieme. Ak je A rekurzívne spočetná, tak sa zapíše pomocou existenčného kvantifikátoru na rekurzívny predikát. A opačne.

Tak sa pozrime na indukčný krok. najprv jedným smerom.

Majme množinu $A\in {\Sigma }_{n+1}$. A sa dá teda vyjadriť v tvare $\exists \forall \dots Q(\dots )$. Odrežme to za prvým kvantifikátorom. To, čo dostaneme je v ${\Pi }_n$. Negácia toho je v ${\Sigma }_n$ a podľa indukčného predpokladu je rekurzívne spočetná v ${\varnothing }^{(n-1)}$. z vlastnosti skoku je rekurzívna v ${\varnothing }^{(n)}$. Keď je negácia rekurzívna v ${\varnothing }^{(n)}$, tak aj bez negácie je to rekurzívne v ${\varnothing }^{(n)}$ a po pridaní odtrhnutého kvantifikátoru späť je to rekurzívne spočetné v ${\varnothing }^{(n)}$.

Opačným smerom si ukážeme dva postupy.

Predpokladajme, že A je rekurzívne spočetné v ${\varnothing }^{(n)}$ A je teda definičným oborom ${\Phi }_z({\varnothing }^{(n)})$ pre nejaké z. Teda $x\in A⟺\exists \sigma \exists y,s({\Phi }_{z,s}(\sigma )(x)=y\&\sigma \le {\varnothing }^{(n)}$. ${\Phi }_{z,s}(\sigma )(x)=y$ je rekurzíva podmienka, takže nám zostáva niečo tvaru: $\exists (\sigma \le {\varnothing }^{(n)})$ a potrebujeme zistiť, aká zložitá je táto vec. $\sigma$ je vlastne konečná konjunkcia dĺžky $|\sigma |$ a hovorí nám: $\sigma (j)=1⟹j\in {\varnothing }^{(n)}$ a $\sigma (j)=0⟹j\notin {\varnothing }^{(n)}$ pre každé $j<|\sigma |$. Tu použijeme indukčný predpoklad a to taký, že to, že $j\in {\varnothing }^{(n)}$ je ${\Sigma }_n$ a $j\notin {\varnothing }^{(n)}$ je ${\Pi }_n$ (pretože ${\varnothing }^{(n)}$ je rekurzívne spočetná v ${\varnothing }^{(n-1)}$ a z indukčného predpokladu je to ${\Sigma }_n$ a preto aj $\overline{{\varnothing }^{(n)}}$ je ${\Pi }_n$. Takže naše $\exists (\sigma \le {\varnothing }^{(n)})$ je vlastne $\exists ({\Sigma }_n\&{\Pi }_n)$, kde to vnútri je konjunkcia mnohých ($|\sigma |$) ${\Sigma }_n$ a ${\Pi }_n$ vecí. Prenexnými operáciami môžeme vytiahnúť zo ${\Sigma }_n$ jeden kvantifikátor vonku a zvyšok $\exists ({\Pi }_{n-1}\&{\Pi }_n)$ je ${\Sigma }_{n+1}$.

Druhá možnosť je použiť vetu o limitnej vyčísliteľnosti. Ak máme

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 3: A=\̲m̲b̲o̲x̲{dom}(\Phi_z(\e…

, tak podľa vety o limitnej vyčísliteľnosti: ${\Phi }_z({\varnothing }^{(n)})={\lim }_{s}h(z,x,s)$, kde $h$ je ${\varnothing }^{(n-1)}$ORF. Takže $x\in A⟺{\Phi }_z({\varnothing }^{(n)})\downarrow$ a to je práve vtedy, keď existuje tá limita. To je práve vtedy, keď $\exists s_0\forall s\ge s_0(h(z,x,s)=h(z,x,s_0))$. Tá vec v poslednej zátvorke je rekurzívna v ${\varnothing }^{(n-1)}$ a podľa indukčného predpokladu je v prieniku ${\Sigma }_n\cap {\Pi }_n$, čiže aj v ${\Pi }_n$. Máme $\exists s_0\forall s\ge s_0({\Pi }_n)$. Všeobecný kvantifikátor necháme pohltiť v ${\Pi }_n$ a existenčný z toho vyrobí ${\Sigma }_{n+1}$.

Relativizácia funguje aj na túto vetu: $A{\le }_T{B}^{(n)}⟺A\in {\Sigma }_{n+1}^B\cup {\Pi }_{n+1}^B$ a $A$ je rekurzívne spočetná v $B$ práve vtedy, keď $A\in {\Sigma }_{n+1}^B$.

Tým skončila teória prednášky a nasledovali dva príklady, kde sa ukazovalo, že Tot je ${\Pi }_2$úplná a že Rek je ${\Sigma }_3$úplná. Snáď to tu ešte dopíšem.

Príklad: Tot je ${\Pi }_2$úplná.

Vieme, že Tot je v ${\Pi }_2$ $(\{x|\forall y\exists s({\phi }_x(y)\downarrow )\}$ za menej ako s krokov.). Ak vezmeme ľubovoľnú $B\in {\Pi }_2$, tak potrebujeme ukázať, že sa dá 1-previesť na Tot. Naša $B$ sa dá zapísať ako

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 58: …ace{Q(x,y,s)}_{\̲m̲b̲o̲x̲{rekurzívne}})

. Tak si vytvoríme pomocnú ČRF $\alpha (x,y)\simeq {\mu }_{s}Q(x,y,s)$. Ak máme prvok $x\in B$, tak pre každé $y$ existuje $s$, také, že platí $Q(x,y,z)$ (tiež sa hovorí, že existuje ${\Sigma }_1$ svedok alebo že nastane ${\Pi }_2$ udalosť (tieto pojmy neznamenajú to isté, treba skontrolovať, čo to presne je). Ak $x\notin B$, tak sa také $s$ aby $Q(x,y,s)$ platilo, pre nejaké $y_0$ nájsť nepodarí. A naše $\alpha (x,y)$ také $s$ hľadá. Podľa s-m-n vety je $\alpha (x,y)\simeq {\phi }_{g(x)}(y)$, kde $g(x)$ je ORF (dokonca by to mala byť PRF), ktorá prevádza $B$ na Tot (

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 23: … \iff g(x) \in \̲m̲b̲o̲x̲{Tot}

). Podrobnejšie: Ak $x\in B$, tak pre každý $y$ nájde $\alpha (x,y)\simeq {\phi }_{g(x)}(y)$ svedka $s$, teda sa zastaví (a

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 10: g(x) \in \̲m̲b̲o̲x̲{Tot}

) a pre $x\notin B$ svedka pre nejaké $y_0$ nenájde, takže tam nezastaví (a preto

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 13: g(x) \notin \̲m̲b̲o̲x̲{Tot}

).

Nakoniec sme si povedali a zosumarizovali, že

• Fin je ${\Sigma }_2$-úplná.

• Tot, Inf sú ${\Pi }_2$-úplné/

• Rek je ${\Sigma }_3$-úplná.

Tak sa pozrime na Rek a ukážme, že je ${\Sigma }_3$úplná.

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 1: \̲m̲b̲o̲x̲{Rek}=\{x:W_x \…

.

Dôkaz: Nech $B\in {\Sigma }_3$, teda $x\in B\iff \exists z\forall y\exists sQ(x,z,y,s)$, kde $z$ je ${\Sigma }_3$-svedok.

Majme $W_{\alpha (x)}=\{⟨z,y⟩:\exists sQ(x,z,y,s)\}$

$⟨z,y⟩$ čaká na svojho svedka $W_{\beta (x)}=\{⟨z,y⟩:\forall j\le y\exists Q(x,z,j,s)\}$

každý stĺpec je závislý počiatočný úsek, ak to platí pre $y$, tak to platí aj pre menšie od $y$.

Ak $x\in B$, potom v $W_{\beta (x)}$ existuje stĺpec $z$, ktorý je plný, lebo potom to platí pre všetky $y$. Ak $x\notin B$, potom všetky stĺpce v $W_{\beta (x)}$ sú konečné.

$W_{\gamma (x)}=$ stĺpce rastú smerom doprava, s bodmi $⟨z,y⟩$ z $W_{\beta (x)}$ pridaj do $W_{\gamma (x)}$ aj $⟨i,j⟩i\le z\wedge j\le y$.

Ak $x\in B$, potom na začiatku niekoľko konečných stĺpcov a potom všetko nekonečné totálne stĺpce.

Ak $x\notin B$, potom všetky stĺpce sú konečné (aj keď neklesajúce).

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 46: …n K \And j \leq\̲m̲b̲o̲x̲{ počet krokov …

$W_{\sigma (x)}=W_{\gamma (x)}\cup E$. $x\in B$ je niekoľko konečných a zvyšok nekonečné až totálne - rekúrzivne. $x\notin B$ sú všetky stĺpce konečné v $W_{\sigma (x)}$, ale $W_{\sigma (x)}$ je nerekurzívna.

Ak by bola $W_{\sigma (x)}$ rekurzívna, tak musí existovať ORF $h(z)$, ktorá dáva min. $y:⟨z,y⟩\notin W_{\sigma (x)}$. $z\in K\iff z$ padne do $K$ za menej ako $h(z)$ krokov $z\in K_{h(z)}$ potom $K$ je rekurzívna, čo je spor.

$x\in B\iff W_{\sigma }(x)$ je rekurzívna.

Dôkaz si treba pár krát sparsovať, uvedomiť si čo spraví $E$, keď ju pridáme, atď.