{{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 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 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 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 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:
Veta (relativizácia)
# Ak ''f'' je A-ORF, tak <math>\lim_s 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 g(x, s)</math>.
#Dokonca <math>\exists a : \forall A : \Phi_z(A')(x) \simeq \lim \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 miesto <math>\emptyset</math> všade napíšeme ''A''. Takže keď sme mali rekurzívne spočetnú <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četná 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}, \lim_{t_1}, \ldots, \lim_{t_n}}_{n+1 \mbox{ limít}} f(z, x, t_0, t_1, \ldots, t_n)</math>, kde vnútorné limity (<math>t_1, \ldots, t_n</math>) existujú a vonkajšia 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četná 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četné.
{{TODO|Síce sa to "dokazuje štandardným spôsobom", ale ten spôsob sa mi vždy zdal nejaký divný}}
Prevoditeľnosť K na B sa dokazuje štandardným spôsobom pomocou "fiktívnej premennej", cez funkciu <math>\alpha</math>, ktorá B na K prevádza (v poznámkach mám takéto niečo: <math>\varphi_{\alpha(x)}\downarrow \iff x \in K \iff \varphi_x(x)\downarrow</math>, <math>x \in K \iff W_{\alpha(x)} \neq \emptyset</math>. <math>\alpha</math> čaká, či <math>x \in K</math>.
Tak isto sa dá ukázať, že K sa dá 1-previesť na Tot (ale opačne nie).
Ešte treba ukázať, že <math>B \leq_1 K</math>. Vytvorme si <math>\gamma</math> tak, že <math>\varphi_{\gamma(x)}(j)\downarrow \iff W_x \neq \emptyset</math>. <math>\gamma</math> čaká, či <math>W_x \neq \emptyset</math>, hľadá také ''y'', ktoré patrí do <math>W_x</math>: Hľadá <math>y, s: y \in W_{x,s}</math>. Potom <math>x\in B \iff \gamma(x) \in K</math>.
Iná možnosť dôkazu <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četná.
Ešte je vhodné si všimnúť, že A aj B majú v definícii jeden kvantifikátor (<math>\exists y</math>, že niečo).
===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.
{{TODO|Tu bolo posúvanie všeobecného kvantifikátora doprava nejak}}
Taktiež nám nevadia obmedzené kvantifikátory. Keď dostaneme <math>\forall x\leq t \exists y</math>, tak existuje ''t+1'' svedkov, takže to nahradíme <math>\exists w</math> (asi tam ten obmedzený existenčný necháme a posunieme doprava od tohto existenčného: <math>\exists w \forall x\leq t</math> neviem) a v predikáte dáme <math>w_{t+1,x}</math>. "Hrnieme obmedzené všeobecné kvantifikátory doprava a v ORP ich anihilujeme".
Pri obmedzenom existenčnom kvantifikátore to najprv znegujeme (z <math>\exists x \leq t \forall y</math> na <math>\forall x \leq t \exists y</math>, kvantifikátor presuniem doprava na <math>\exists w \forall x\leq t</math> a znegujeme späť. Takže aj tieto kvantifikátory viem presúvať doprava. A <math>\exists x\leq t</math> znamená, že žiadna ''t+1''-tica svedkov nie je dobrá.
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>.
