{{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 \geq 1: \emptyset^n$ je $\Sigma_n$ úplná. #A je rekurzívne spočetná v $\emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0$

#$A \leq_T \emptyset^n \iff 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 \geq 1$ je $\emptyset^{(n)}$ rekurzívne spočetné v $\emptyset^{(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 $\emptyset^{(n-1)}$ a podľa vlastnosti skoku je to 1-prevoditeľné na $\emptyset^{(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 \ldots Q(\ldots)$. 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 $\emptyset^{(n-1)}$. z vlastnosti skoku je rekurzívna v $\emptyset^{(n)}$. Keď je negácia rekurzívna v $\emptyset^{(n)}$, tak aj bez negácie je to rekurzívne v $\emptyset^{(n)}$ a po pridaní odtrhnutého kvantifikátoru späť je to rekurzívne spočetné v $\emptyset^{(n)}$.

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

Predpokladajme, že A je rekurzívne spočetné v $\emptyset^{(n)}$ A je teda definičným oborom $\Phi_z(\emptyset^{(n)})$ pre nejaké z. Teda $x \in A \iff \exists \sigma \exists y,s(\Phi_{z,s}(\sigma)(x) = y \And \sigma \leq \emptyset^{(n)}$. $\Phi_{z,s}(\sigma)(x) = y$ je rekurzíva podmienka, takže nám zostáva niečo tvaru: $\exists(\sigma \leq \emptyset^{(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 \implies j \in \emptyset^{(n)}$ a $\sigma(j) = 0 \implies j \notin \emptyset^{(n)}$ pre každé $j <|\sigma|$. Tu použijeme indukčný predpoklad a to taký, že to, že $j \in \emptyset^{(n)}$ je $\Sigma_n$ a $j \notin \emptyset^{(n)}$ je $\Pi_n$ (pretože $\emptyset^{(n)}$ je rekurzívne spočetná v $\emptyset^{(n-1)}$ a z indukčného predpokladu je to $\Sigma_n$ a preto aj $\overline{\emptyset^{(n)}}$ je $\Pi_n$. Takže naše $\exists(\sigma \leq \emptyset^{(n)})$ je vlastne $\exists(\Sigma_n \And \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}\And \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(\emptyset^{(n)}) = \lim_s h(z,x,s)$, kde $h$ je $\emptyset^{(n-1)}$ORF. Takže $x \in A \iff \Phi_z(\emptyset^{(n)})\downarrow$ a to je práve vtedy, keď existuje tá limita. To je práve vtedy, keď $\exists s_0 \forall s \geq s_0 (h(z,x,s)=h(z,x,s_0))$. Tá vec v poslednej zátvorke je rekurzívna v $\emptyset^{(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 \geq 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\leq_T B^{(n)} \iff A \in \Sigma^B_{n+1}\cup\Pi^B_{n+1}$ 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 (\varphi_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 \varphi_{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 \varphi_{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 \Leftrightarrow \exists z \forall y \exists s Q(x,z,y,s)$, kde $z$ je $\Sigma_3$-svedok.

Majme $W_{\alpha(x)} = \{ \langle z,y\rangle: \exists s Q(x,z,y,s) \}$

$\langle z,y \rangle$ čaká na svojho svedka $W_{\beta(x)} = \{ \langle z,y\rangle: \forall j \leq 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 \not\in B$, potom všetky stĺpce v $W_{\beta(x)}$ sú konečné.

$W_{\gamma(x)} =$ stĺpce rastú smerom doprava, s bodmi $\langle z,y \rangle$ z $W_{\beta(x)}$ pridaj do $W_{\gamma(x)}$ aj $\langle i,j \rangle i \leq z \land j \leq 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 \not\in 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 \not\in 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: \langle z,y \rangle \not\in W_{\sigma(x)}$. $z \in K \Leftrightarrow 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 \Leftrightarrow 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ď.