{{TIN065 Prednášky}} Máme tu siedmu prednášku, čo znamená, že by sme mali byť už za polovicou. Na minulej prednáške sme sa začali zaoberať aritmetickou hierarchiou. Tak trochu s nadhľadom sme vynechávali premenné. Tiež sme si povedali, že hierarchie nie sú až tak zriedkavá vec. Jednu nájdeme v zložitosti - tam máme kvantifikátory obmedzené polynómom (asi ako "niečo existuje a je to nájditeľné v polynomiálnom čase"). Tiež je istá paralela medzi kvantifikátormi a operáciami zjednotenie a prienik (patrí do každej množiny, patrí do aspoň jednej množiny). Pre pripomenutie: $\Sigma$ sú tie, ktoré začínajú existenčným kvantifikátorom a $\Pi$ sú tie, čo začínajú všeobecným. Triedy $\Sigma_0$ a $\Pi_0$ sú základné predikáty (bez kvantifikátorov, takže $\Sigma_0=\Pi_0$). V $\Sigma_n$ a $\Pi_n$ sú zasa tie predikáíty, ktoré sú vyjadriteľné ako predikáty s $\Sigma_n$ alebo $\Pi_n$ prefixom, čiže pred sebou majú n striedajúcich sa skupín kvantifikátorov. Dôležité je tiež, že prefix sa dá redukovať (v každej skupine ostane len jeden kvantifikátor) a obmedzené kvantifikátory nám nevadia (vieme sa ich zbaviť). Aritmetický predikát je taký, ktorý má jeden z našich prefixov a zvyšok je záležitosťou predikátovej logiky (sú tam nejaké spojky a tak). Presnejšie značenie je $\Sigma_n^0$, kde 0 znamená, že kvantifikujeme cez základné objekty (prirodzené čísla). 1 by znamenalo kvantifikovať cez funkcie, vyššie čísla cez niečo vyššie. To robiť nebudeme. V zložitosti sa dá stretnúť s označením $\Sigma_n^p$, kde p znamená polynomiálnu hierarchiu. V značení je trochu neporiadok. Celá hierarchia sa dá relativizovať a vzniknú nám $\Sigma_n^{0,A}$ predikáty. Príklad: *Tot* je $\Pi_2$. $\mbox{Tot} = \{x:\forall y \exists s: \underbrace{\varphi_x(y)\downarrow \mbox{za } s\mbox{ krokov}}_\mbox{rekurzívna podmienka}\}$ Iný príklad: *Rek*: $\mbox{Rek} = \{x:W_x \mbox{je rekurzívna}\}$. Každá $W_x$ je rekurzívne spočetná (to vieme), len niektoré nie sú rekurzívne.$x \in Rek \iff \overline{W_x}$ je rekurzívne spočetná (Postová veta) $\iff \exists y (\overline{W_x} = W_y)$$\iff \exists y (W_x \cup W_y = \mathbb{N} \And W_x \cap W_y = \emptyset)$$\iff \exists y (\forall z (z \in W_x \cup W_y) \And \forall z (z \notin W_x \cap W_y))$$\iff \exists y (\forall z \exists s (z \in W_{x,s} \cup W_{y,s}) \And \forall z, s (z \notin W_{x,s} \cap W_{y,s}))$. V poslednom kroku už máme iba kvantifikátory na rekurzívnej podmienke (s je ako vždy počet krokov) a celé je to tvaru $\exists (\forall \exists \And \forall)$, z čoho sa dá "[šikovnými úpravami](wen:Tarski–Kuratowski%20algorithm)" nejak vyhrabať $\exists \forall \exists (\mbox{rek. podm.})$, takže to celé bude v $\Sigma_3$. Keby ostal čas a nezabudlo sa na to, na konci by sme si povedali prečo to lepšie nejde. Podobným spôsobom sa ukáže, že Fin je $\Sigma_2$. ## Vetičky ## #$B\in \Sigma_n \iff \overline{B} \in \Pi_n$ #$B\in \Sigma_n (\mbox{resp. } \Pi_n) \implies B \in \Sigma_m \cap \Pi_m$ pre $m>n$ #$A\leq_m B \And B\in \Sigma_n (\mbox {resp. } \Pi_n) \implies A\in \Sigma_n (\mbox {resp. } \Pi_n)$ Dôkaz: #Triviálne z De Morganových pravidiel (teda, z toho, že $\exists \neg \equiv \neg \forall$ a opačne). #Druhé tvrdenie je len vyjadrením toho, že ak niečo ide jednoducho, ide to aj zložito. Ak potrebujem pridať kvantifikátor, tak si pridám fiktívnu premennú, ktorá nič nezmení a nepokazí. A kvantifikátor pridávam na koniec reťazca (akurát keď potrebujem zmeniť $\Sigma$ na $\Pi$ alebo späť, tak pridám jeden na začiatok) tak, by sa striedali. #Mali sme vetu, ak $A \leq_m B$ a B je rekurzívne spočetná, tak aj A je rekurzívne spočetná. Táto veta má rovnaký dôkaz. Ale predsa aspoň niečo: Nech $B = \exists \forall \cdots Q(x, y_1, \ldots, y_n)$. Keďže sú m-prevoditeľné, tak existuje ORF *f*, že $x \in A \iff f(x) \in B \iff \exists \forall \ldots Q(f(x), y_1, \ldots, y_n)$, kde to na konci je už vyjadrenie A v $\Sigma_n$ (pre $\Pi_n$ podobne). Zaujíma nás, ako zapisovať množiny čo najjednoduchšie a ako táto hierarchia súvisí so skokom. A tiež nás zaujíma numerácia a indexácia. ## Numerácia a indexácia ## Vieme, že $\Sigma_0=\Pi_0$ nemajú univerzálny ORP. (sporom: Nech je $R(e, x)$ *e*-ty ORP. Tak si vezmime $\neg R(x, x)$, ktorý bude mať číslo $e_0$ a keď pustíme $R(e_0, e_0)$, tak sa to bude rovnať svojej negácii). Tiež vieme, že $\Sigma_1$ má univerzálny $\Sigma_1$ predikát. Ten pre jednu premennú má premenné dve a je tvaru $\exists s T_1(e, x, s)$ a platí tam s-m-n veta. **Veta:** Pre $\forall n \geq 1$ triedy $\Sigma_n$ a $\Pi_n$ majú univerzálny $\Sigma_n$ a $\Pi_n$ predikát. Dôsledkom je, že sa dá zaviesť pojem $\Sigma_n$index, prípadne $\Sigma_n$goedelového čísla. Univerzálny predikát nám poskytuje indexáciu a numeráciu a my vieme povedať, čo je to *etý* predikát. Dokazuje sa to indukciou. Pre $n=1$ máme pre $\Sigma_1$ predikát $\exists s T_1(e, x, s)$ a pre $\Pi_1$ $\forall s \neg T_1(e, x, s)$. K $\Pi_1$: $\Pi_1$ je negáciou $\Sigma_1$, a z $\neg \exists s T_1(e,x,s)$ vzniklo $\forall s \neg T_1(e,x,s)$. Rovnako z univerzálneho predikátu k $\Sigma_n$ vytvoríme univerzálny k $\Pi_n$. Nech n je nepárne. Náš $\Sigma_n$ reťazec končí na $\exists$ a vyzerá asi takto: $\exists \forall \ldots \exists Q(x, y_1, \ldots, y_n)$. Odrežeme to pred posledným kvantifikátorom a dostaneme $\exists y_n Q(x, y_1, \ldots, y_n)$, kde všetky premenné okrem $y_n$ sú voľné. To je ekvivalentné s univerzálnym $\Sigma_1$ predikátom pre *n* premenných: $\exists y_n T_n(e, x, y_1, \ldots, y_n)$ a k tomu prilepíme odtrhnuté kvantifikátory: $\exists y_1 \forall y_2 \ldots \exists y_n T_n(e, x, y_1, \ldots, y_n)$, kde *e* je číslo predikátu a x je vstup. Pre párne n je postup skoro rovnaký, len pri odtrhnutí $\forall$ prejdem k negácii: z $\forall Q()$ sa stane jednou negáciou $\exists \neg Q()$, ktoré je ekvivalentné univerzálnemu $\exists T_n()$ a z toho druhou negáciou späť na $\forall \neg T_n()$. A k tomu pridám odrezané kvantifikátory. Pre $\Pi_n$ sa to dokazuje rovnako. Pekným zistením je, že $K\in \Sigma_1 - \Pi_1$ (K je rekurzívne spočetná, ale jej doplnok už nie). Máme dokonca vetu: **Veta:** $\forall n \geq 1 : \Sigma_n - \Pi_n \neq \emptyset$. Dôkaz: rovnaký ako pre *n*=1. Nech $Univ^{(n)}(e, x)$ je univerzálny predikát pre $\Sigma_n$. Vezmem $P(x) = Univ^{(n)}(x,x)$. To, že je v $\Sigma_n$ je vidieť a keby bol v $\Pi_n$, tak jeho negácia by musela byť v $\Sigma_n$. Tá má svoje číslo $e_0$ a je teda $Univ^{(n)}(e_0, x)$. Teda $\neg Univ^{(n)}(x, x) = Univ^{(n)}(e_0, x)$, čo pre $x=e_0$ dá spor. Takže $P(x)$ je v $\Sigma_n$ ale nie v $\Pi_n$. **Fakt:** $\Sigma_1 \cap \Pi_1 = \Sigma_0 = \Pi_0$ (to je Postova veta). Uvidíme ale, že to neplatí pre vyššie $\Sigma_n$. Už pre dvojku $\Sigma_1\cup \Pi_1$ je vlastnou podmnožinou $\Sigma_2 \cap \Pi_2$. **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 vetu si dokážeme nabudúce. Poznámky: $\{A: A \leq_T \emptyset^{\prime}\}$ je viac ako $\Sigma_1 \cup \Pi_1$ $\Sigma_1$ sú rekurzívne spočetné množiny a $\Pi_1$ ich doplnky. Ale už netriviálna kombinácia množín z $\Sigma_1$ a $\Pi_1$ bude T-prevoditeľná na $\emptyset^{\prime}$, ale nebude v $\Sigma_1 \cup \Pi_1$. Príkladom je množina $K\times \overline{K}$. Tá je T-prevoditeľná na $\emptyset^{\prime}$. Ale zároveň $K \leq_1 K\times \overline{K}$ (napr. funkciou $x\to $ a $\overline{K} \leq_1 K\times \overline{K}$ napríklad funkciou $x\to $. A teda ak by $K\times \overline{K}$ bolo v $\Sigma_1$, tak by tam musela byť aj $\overline{K}$ a ak by $K\times \overline{K}$ bolo v $\Pi_1$, tak by tam musela byť aj $K$. A tie ako vieme tam nie sú. A ešte definíciu pojmu, ktorý sme vo vete o hierarchii použili: A je $\Sigma_n$ úplná ak je v $\Sigma_n$ a hocijaká B zo $\Sigma_n$ sa dá 1-previesť na A. Poznámka: prečo v zložitosti nevieme tak pekne zistiť niektoré vzťahy (či niektoré triedy sú alebo nie sú zhodné)? Pretože si nemôžeme pomôcť univerzálnym polynómom. Taký proste nemáme.