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

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

Iný príklad: Rek:

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

. 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á "wen:Tarski–Kuratowski%20algorithm" nejak vyhrabať

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 26: …orall \exists (\̲m̲b̲o̲x̲{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$

#

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 16: B\in \Sigma_n (\̲m̲b̲o̲x̲{resp. } \Pi_n)…

pre $m>n$ #

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 31: …B\in \Sigma_n (\̲m̲b̲o̲x̲ ̲{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 <x, z_0>$ a $\overline{K} \leq_1 K\times \overline{K}$ napríklad funkciou $x\to <z_0, x>$. 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.