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

A\leq_T \emptyset^{(n)} \iff A , \overline{A} \mbox{ sú rekurzívne spočetné v }\emptyset^{(n)} \iff A,\overline{A} \in \Sigma_{n+1} \iff A\in \Sigma_{n+1}\cap \Pi_{n+1}. 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 A=\mbox{dom}(\Phi_z(\emptyset^{(n)}), 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 x \in B \iff \forall y \exists s (\underbrace{Q(x,y,s)}_{\mbox{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 (x \in B \iff g(x) \in \mbox{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 g(x) \in \mbox{Tot}) a pre x \notin B svedka pre nejaké y_0 nenájde, takže tam nezastaví (a preto g(x) \notin \mbox{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á. \mbox{Rek}=\{x:W_x \mbox{ je rekurzívne }\}.

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

E = \{ \langle z,j\rangle: z\in K \And j \leq\mbox{ počet krokov kedy }z \mbox{ vstúpi do }K \}

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ď.