{{TIN065 Prednášky}}
Na minulej prednáške sme si spomenuli základný vzťah medzi limitami a prechodom medzi stupňami (zatiaľ iba od <math>\emptyset</math> k <math>\emptyset'</math>). Najprv špecifický prípad, kde sme mali totálne ''A'' a platilo <math>A \leq_T \emptyset'\iff A(x)=\lim_{s \to \infty} f(x, s)</math> pre nejakú ORF ''f''. Mali sme neefektívne orákulum, ale nám stačilo ho aproximovať na konečnej časti. A pýtali sme sa, či už je výsledok stabilný.
Všeobecnejšia veta zasa mala dve časti. Jedným smerom: ak máme ORF ''f'', tak <math>\lim_{s \to \infty} f(x, s)</math> je <math>\emptyset^\prime\mbox{-ČRF}</math>. Pomocou ''while'' cyklu sme hľadali najmenšie ''s'' také, že sa nám to stabilizuje. Opačným smerom zasa <math>\emptyset'\mbox{-ČRF}\varphi</math> je podmienene rovná <math>\lim_{s \to \infty} f(x,s)</math> pre nejakú ORF ''f''. Mali sme teda <math>\Phi_z(\emptyset')(x)</math> (to je naša <math>\varphi</math>), ktoré nemusí vždy konvergovať a my aproximujeme celý výpočet. Vytvárame si výpočet pre konečné množstvo krokov a vraciame <math><\sigma, x, y></math> keď <math>\Phi_{z,s}(\sigma)(x)=y \land \sigma \leq \emptyset'_s</math>.Keď sa nám výpočet stabilizuje, tak vrátime z neho tretiu zložku a to bude výsledok našej ''f'' (ak sa výpočet nestabilizuje, tak limita ''f'' nebude existovať).
Dnes sme začali dodatkom: <math>\exists \mbox{ORF} h: \Phi_z(\emptyset')(x) \simeq \lim_{s \to \infty} h(z,x,s)</math>.
Základná myšlienka je - ak aplikujeme limitu, prejdeme o skok vyššie. To si zhrnieme nasledujúcou ešte všeobecnejšou vetou:
===Ešte všeobecnejšia veta===
<b>Veta:</b> (relativizácia)
# Ak ''f'' je A-ORF, tak <math>\lim_{s \to \infty} f(x, s)</math> je A' ČRF.
# Pre ľubovoľnú A'-ČRF <math>\varphi</math> existuje A-ORF ''g'' taká, že <math>\varphi(x) = \lim_{s \to \infty} g(x, s)</math>.
#Dokonca <math>\exists a : \forall A : \Phi_z(A')(x) \simeq \lim_{s \to \infty} \Phi_a(A)(z, x, s)</math>, kde <math>g=\Phi_a(A)</math> a je všade definovaná. Pekné je, že ''a'' nezávisí na ''A''
Dokazuje sa to relativizáciou dôkazu z minulej prenášky. Len namiesto <math>\emptyset</math> všade napíšeme ''A''. Takže keď sme mali rekurzívne spočítateľnú <math>\emptyset'</math> a <math>\emptyset' = W_{z_0, s}^\emptyset</math>, kde ''s'' boli kroky, tak teraz budeme mať pre každé ''A'' množinu <math>W_{z_0}^A = A'</math>. A' je A-rekurzívne spočítateľná a vieme, že <math>A' = W_{z_0}^A</math> a to sa aproximuje cez <math>W_{z_0, s}^{A^\prime}</math>. Dôkaz bude rozvnaký ako minule.
Dôsledok: <math>\Phi_z(\emptyset^{(n+1)})(x) \simeq \underbrace{\lim_{t_0 \to \infty}, \lim_{t_1 \to \infty}, \ldots, \lim_{t_n \to \infty}}_{n+1 \mbox{ limit}} f(z, x, t_0, t_1, \ldots, t_n)</math>, kde vnútorné limity (<math>t_1 \to \infty, \ldots, t_n \to \infty</math>) existujú a vonkajšia pre <math>t_0 \to \infty</math> existovať nemusí. Dokazuje sa to iteráciou predchádzajúceho dôkazu ("je to vidět") pravdepodobne s troškou indukcie. Vnútri sú ORF, preto vnútorné limity musia existovať.
Takže z tejto časti si odnesieme to, že prechod o skok niektorým smerom znamená pridať alebo odbrať limitu.
==Vsuvka: O niektorých množinách a kvantifikátoroch==
Označme si nasledujúce množiny takto:
* <math>A = \{x: W_x = \emptyset\}</math>
* <math>B = \{x: W_x \neq \emptyset\}</math>
* <math>Fin = \{x: W_x \mbox{ je konečná}\}</math>
* <math>Inf = \{x: W_x \mbox{ je nekonečná}\}</math>
* <math>Tot = \{x: W_x = \mathbb{N}\}</math>
* <math>Rek = \{x: W_x \mbox{ je rekurzívna}\}</math>
Tvrdenie: B je rekurzívne spočítateľná a <math>B \equiv_1 K</math>.
Prvá časť je vidieť. <math>B = \{x: \exists s : W_{x, s} \neq \emptyset\} = \{x:\exists y, s : y \in W_{x, s}\}</math>, kde na konci máme existenčný kvantifikátor na rekurzívnej podmienke, takže je to rekurzívne spočítateľné.
Prevoditeľnosť K na B vyplýva z prevoditeľnosti K na Tot, keďže Tot je podmnožina B. Chceme teda nájsť takú ORF f, pre ktorú bude platiť <math>\varphi_{x}(x)\downarrow \iff W_{f(x)} = \mathbb{N}</math>. Opäť pomôže s-m-n veta a fiktívna premenná. Definujme ČRF <math>\alpha</math> takto: <math>\alpha(x,w)\downarrow \iff \varphi_{x}(x)\downarrow</math>. Funkcia <math>\alpha</math> má index e, použijeme s-m-n vetu: <math>\alpha(x,w) \simeq \varphi_{e}(x,w) \simeq \varphi_{s_1(e,x)}(w)</math>. Našu f definujme <math>f(x) = s_1(e,x)</math>. Potom pre každé w: <math>x \in K \iff \varphi_{x}(x)\downarrow \iff \alpha(x,w)\downarrow \iff \varphi_{f(x)}(w)\downarrow \iff W_{f(x)} = \mathbb{N} \iff f(x) \in Tot</math>. Takže K je prevediteľná na Tot a teda ja na B.
Ešte ukážeme, že <math>B \leq_1 K</math>. Rovnakým postupom ako pri dôkaze opačného smeru si vytvoríme funkciu <math>\beta(x, y, w)</math> s fiktívnou premennou <math>w</math> a z jej indexu pomocou s-m-n vety vytvoríme ORF funkciu <math>g(x)</math>. Pre túto funkciu <math>g(x)</math> bude platiť, že pre každý vstup <math>x</math> vráti číslo programu, ktorý ignoruje svoj vstup a skonverguje práve vtedy, ak nájde nejaký prvok, ktorý padne do <math>W_x</math>.
{{TODO|Nasledujúci postup je síce zrejme správny, ale nevedie k cieľu. Trebalo by ho ešte vylepšiť, opraviť a dotiahnuť to do konca.}}
Formálne: Funkciu <math>\beta(x, y, w)</math> definujeme takto: <math>\beta(x, y, w)\downarrow</math><math>\iff</math><math>\varphi_x(y)\downarrow</math> Nech <math>\beta(x, y, w)</math> má index <math>e</math>. Potom platí:
<math>\beta(x, y, w)\downarrow</math><math>\iff</math><math>\varphi_e(x, y, w)\downarrow</math><math>\iff</math><math>\varphi_{s_2(e, x, y)}(w)\downarrow</math>. Zadefinujeme si: <math>g(x) = s_2(e, x, y)</math> pre pevné <math>x</math> a <math>y</math>. Potom platí: <math>x \in B</math><math>\iff</math><math>(\exists y)(\varphi_x(y)\downarrow)</math><math>\iff</math><math>(\exists y)(\beta(x, y, w)\downarrow)</math><math>\iff</math><math>(\exists y)(\varphi_e(x, y, w)\downarrow)</math><math>\iff</math><math>(\exists y)(\varphi_{s_2(e, x, y)}(w)\downarrow)</math><math>\iff</math><math>(\exists y)(\varphi_{g(x)}(w)\downarrow)</math>. Funkcia <math>g(x)</math> nezávisí na <math>w</math>. Položme teda <math>w = g(x)</math> a dostávame: <math>(\exists y)(\varphi_{g(x)}(w)\downarrow)</math><math>\Longrightarrow</math><math>(\exists y)(\varphi_{g(x)}(g(x))\downarrow)</math><math>\iff</math><math>(\exists y)(g(x) \in K)</math>.
Problémy sú dva: prvým je, že sled ekvivalencií je porušený jednou implikáciou a druhým je existenčný kvantifikátor cez premennú y, ktorý sa stále objavuje pred požadovanou formulou <math>g(x) \in K</math>.
Pre takúto funkciu <math>g</math> má platiť: <math>x \in B</math><math>\iff</math><math>W_x\neq \emptyset</math><math>\iff</math><math>g(x) \in W_{g(x)}</math><math>\iff</math><math>g(x) \in K</math>. A teda <math>B \leq_1 K</math>.
<b>Iná možnosť dôkazu</b> <math>B \leq_1 K</math> je, že si spomenieme na to, že K je 1-úplná.
Keďže <math>A = \overline{B}</math>, tak <math>A \equiv_1 B</math> a preto A nie je rekurzívne spočítateľná.
Ešte je vhodné si všimnúť, že A aj B majú v definícii jeden kvantifikátor (<math>\exists y</math> ... alebo <math>\forall y</math> ...).
===Množiny s dvoma kvantifikátormi===
* Fin: <math>\{x:\exists s_0 \forall s > s_0: s\notin W_x\}</math> alebo tiež <math>\exists s_0: \forall s > s_0 \forall t: s \notin W_{x, t}</math>.
* Inf: podmienka: <math>\forall s \exists j j>s \land j\in W_{x}</math> alebo tiež <math>\forall s \exists j \exists t: j>s \land j\in W_{x, t}</math>
* Tot: <math>\forall s \exists t : s\in W_{x, t}</math>
Tvrdenie: <math>\mbox{Inf}\equiv_1\mbox{Tot}</math>.
Opäť si vytvoríme <math>\alpha</math>: <math>\varphi_{\alpha(x)}(j)\downarrow \iff \{0, 1, \ldots, j\}\subset W_x</math>. Pre stále väčšie ''j'' je vpravo stále väčšia konjunkcia a <math>\alpha</math> s rastúcim ''j'' kontorluje, či ''j'' patrí do <math>W_x</math>. Ak tam nejaké <math>y_0</math> nepatrí, tak <math>\forall y \geq y_0: \varphi_{\alpha(x)}(y)\uparrow</math> (už sa tam nedostane).
Opačne: <math>\varphi_{\beta(x)}(j)\downarrow</math> práve keď existuje aspoň ''j'' prvkov v <math>W_x</math>. <math>x \in \mbox{Inf} \iff \beta(x) \in \mbox{Tot}</math>. Vezmem <math>W_x</math> a efektívne ho generujem. Keď som vypísal aspoň ''j'' čísel, tak <math>\varphi_{\beta(x)}(j)\downarrow</math>.
<math>\mbox{Fin} = \overline{\mbox{Inf}}</math>.
Platí tiež: <math>\overline{\emptyset^{(2)}} \equiv \mbox{Tot}</math>, teda <math>\emptyset^{(2)} \equiv \overline{\mbox{Tot}} \equiv \mbox{Fin}</math>.
==Aritmetická hierarchia==
Aritmetická hierarchia je klasifikácia množín podľa aritmetickej zložitosti. S hierarchiami sa stretneme vo viacerých oblastiach. Napríklad v analýze sa dá stretnúť s Borelovskou hierarchiou, na zložitosti máme polynomiálnu hierarchiu. Obidve tieto sa trochu podobajú našej (v borelovskej miesto kvantifikátorov by mali byť zjednotenia a prieniky, v polynomiálnej budeme kvantifikátory nejak polynomiálne obmedzovať.
Pozrieme sa na hierarchiu "trochu s nadhľadom" a budeme vynechávať premenné, aby sa nám ľahšie písali a chápali definície.
Definícia: <math>\Sigma_n</math>prefix (respektíve <math>\Pi_n</math> prefix) je konečná skupina kvantifikátorov, ktorá má n podskupín, z ktorých každá je homogénna (t.j v jednej skupine sú len <math>\exists</math> alebo len <math>\forall</math>), skupiny sa striedajú a <math>\Sigma_n</math> začína existenčným a <math>\Pi_n</math> všeobecným kvantifikátorom.
Keby sme tú definíciu chceli napísať aj s premennými, tak si musíme dávať pozor na veci ako rozdielnosť premenných. prípadne na obory platnosti.
Definícia: Prefix sa nazýva redukovaný, ak každá podskupina je jednočlenná (takže sa v prefixe iba striedajú jednotlivé kvantifikátory).
Prečo sa to tu volá aritmetická hierarchia? Pretože kvantifikátory sú cez objekty najnižšieho možného rádu - základné objekty - čísla. Niekedy sa prefixy označujú aj horným indexom <math>\Sigma_n^0</math>, kde nula označuje úroveň kvantifikácie. V analýze jednička je kvantifikácia cez funkcie (pre každú funkciu), prípadne dvojka (operátory: zobrazenie z funkcií do funkcií). Niekedy sa však ako <math>\Sigma_n^p</math> značí polynomiálna hierarchia. V značení je trošku bordel.
Definícia: Predikát patrí do triedy <math>\Sigma_n</math>, resp. <math>\Pi_n</math> (presnejšie <math>\Sigma_n^0</math> a <math>\Pi_n^0</math>ak je vyjadrijateľnýv tvare <math>\Sigma_n</math> prefix na nejaký obecne rekurzívny predikát, resp. <math>\Pi_n</math>prefix na ORP, pre konečné ''n''.
Pre množinu je to to isté.
Trieda <math>\Sigma_0 = \Pi_0</math> sú práve rekurzívne množiny (samotný ORP), teda algoritmicky rozhodnuteľné.
<math>\Sigma_1</math> sú práve rekurzívne spočetné, <math>\Pi_1</math> sú ich negácie.
Triedy môžeme relativizovať (potom trieda <math>\Sigma_n^{0,A}</math> sú práve všetky predikáty (množiny) vyjadriteľné v tvare <math>\Sigma_n</math>prefix na A-ORP (podobne s <math>\Pi_n^{0, A}</math>. Potom <math>\Sigma_0^{0, A}</math> sú práve všetky A-rekurzívne množiny.
Definícia: Predikát je aritmetický, ak je vyjadriteľný pomocou logiky prvého rádu (nekvantifikujeme cez funkcie) cez ORP.
Veta: Predikát je aritmetický práve keď patrí do nejakej <math>\Sigma_n</math> alebo <math>\Pi_n</math>. Jedným smerom to ide priamo, druhým smerom je to cvičenie na prenexné operácie.
Platí: Vždy sa dá vyrobiť redukovaný prefix. Ak mám napríklad <math>\exists x \exists y</math>, tak to prevediem na <math>\exists w</math>, kde ''w'' je kód dvojice a v predikáte miesto ''x'' a ''y'' dáme <math>w_{2,1}</math> a <math>w_{2,2}</math> (prvá zložka z kódu dvojice, resp. druhá zložka z kódu dvojice). Tak isto pre n-tice, prípadne všeobecné kvantifikátory.
Obmedzené kvantifikátory nám tiež nevadia. Majme výraz <math>\forall x\leq t \exists y: R(x,y)</math>, kde R je nejaký ORP. To znamená, že pre každé z konečne mnoha hodnôt premennej x existuje y také, že platí R. Vytvorme si teda najprv t+1-ticu ypsilónov tak, že na i-tom mieste bude to y, ktoré existuje pre i-té x (pre i = 0 ... t). Túto t+1-ticu môžeme kódovať jedným číslom, takže dostaneme nový výraz ekvivalentný s pôvodným: <math>\exists y \forall x\leq t: R(x,(y)_{x+1})</math>. Vyberáme x-tú zložku z ypsilonu (+1 lebo vydeľovanie zložky sa indexuje od jednotky nie od nuly). V tomto príklade okrem inkriminovanej dvojice žiadne ďalšie kvantifikátory vo výraze nie sú, ale presne tak to funguje aj keď tam ešte nejaké, pred alebo za, sú. Pri obmedzenom existenčnom kvantifikátore výraz najprv znegujeme, použijeme "posunutie všeobecného kvantifikátora dovnútra" a znegujeme naspäť. Pomocou popísaného postupu môžeme obmedzené kvantifikátory dostať až k jadru, kde ich zameníme za konečnú konjunkciu alebo disjunkciu a tak sa ich zbavíme úplne.
A ešte na záver: Ak poviem, že niečo je v <math>\Sigma_n</math>, tak to znamená, že sa to dá vyjadriť ako ORP so <math>\Sigma_n</math> prefixom a nás bude zaujímať, ako to vyjadriť čo najlepšie (najkrajšie). A tiež sa pokúsime zistiť, či by nešlo vyjadriť množinu/predikát s kratším prefixom (napríklad K je v <math>\Sigma_1</math>, ale už nie <math>\Sigma_0</math>). Súvisí to so skokmi z <math>\emptyset</math>, ktoré kopírujú <math>\Sigma</math>.
