{{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⟺\overline{W_x}$ je rekurzívne spočetná (Postová veta) $⟺\exists y(\overline{W_x}=W_y)$$⟺\exists y(W_x\cup W_y=\mathbb{N}\&W_x\cap W_y=\varnothing )$$⟺\exists y(\forall z(z\in W_x\cup W_y)\&\forall z(z\notin W_x\cap W_y))$$⟺\exists y(\forall z\exists s(z\in W_{x,s}\cup W_{y,s})\&\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 \&\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⟺\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{\le }_{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,\dots ,y_n)$. Keďže sú m-prevoditeľné, tak existuje ORF f, že $x\in A⟺f(x)\in B⟺\exists \forall \dots Q(f(x),y_1,\dots ,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\ge 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 \dots \exists Q(x,y_1,\dots ,y_n)$. Odrežeme to pred posledným kvantifikátorom a dostaneme $\exists y_{n}Q(x,y_1,\dots ,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,\dots ,y_n)$ a k tomu prilepíme odtrhnuté kvantifikátory: $\exists y_1\forall y_2\dots \exists y_n{T}_n(e,x,y_1,\dots ,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\ge 1:{\Sigma }_n-{\Pi }_n\ne \varnothing$.

Dôkaz: rovnaký ako pre n=1. Nech $Uni{v}^{(n)}(e,x)$ je univerzálny predikát pre ${\Sigma }_n$. Vezmem $P(x)=Uni{v}^{(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 $Uni{v}^{(n)}(e_0,x)$. Teda $\neg Uni{v}^{(n)}(x,x)=Uni{v}^{(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\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 vetu si dokážeme nabudúce.

Poznámky: $\{A:A{\le }_T{\varnothing }^{\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 ${\varnothing }^{\prime }$, ale nebude v ${\Sigma }_1\cup {\Pi }_1$.

Príkladom je množina $K\times \overline{K}$. Tá je T-prevoditeľná na ${\varnothing }^{\prime }$. Ale zároveň $K{\le }_{1}K\times \overline{K}$ (napr. funkciou $x\to <x,z_0>$ a $\overline{K}{\le }_{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.