Vyčíslitelnost

přednášející: Doc. RNDr. Antonín Kučera, CSc.

VERZE 1.0

Do formátu TEX převedl Ladislav Strojil Připomínky, dotazy, opravy na emailu: Ladislav@Strojil.cz

Nejnovější verze k nalezení vždy na http://ladislav.strojil.cz/vycislitelnost.php

Obsah

1 Základní definice 2

1.1 Výpočetní model . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Rekurzivně spočetné množiny 3

2.1 1-převeditelnost, m-převeditelnost . . . . . . . . . . . . . . . . . 3 2.2 Generování rekurzivně spočetných množin . . . . . . . . . . . . . 8

3 Věty o rekurzi 11 4 Produktivní a kreativní množiny 13 5 Dvojice množin 16 6 Gödelovy věty 18 7 Reprezentovatelnost ČRF v teoriích ZAS 18 8 Numerace 19 9 Relativní vyčíslitelnost 21 10 Operace skoku 22 11 Limitní vyčíslitelnost 24 12 Aritmetická hierarchie 26

12.1 Definice a základní vlastnosti . . . . . . . . . . . . . . . . . . . . 26 12.2 Σ_{2} a Π_{2} úplné množiny . . . . . . . . . . . . . . . . . . . . . . . 27

1 Základní definice

1.1 Výpočetní model

Definice 1 (Turingův stroj).

Deterministický Turingův stroj (DTS) M s k-páskami, kde k je konstanta, je pětice

M = (Q, Σ, δ, q_{0}, F) (1)

Q = konečná množina stavů řídící jednotky Σ = konečná pásková abeceda δ : Q × Σ^{k} ↦ Q × Σ^{k} × {L, N, R}^{k} je přechodová funkce (částečná) q_{0} ∈ Q = počáteční stav F ⊆ Q = množina přijímajících stavů

Věta 1 (Kleenova o normální formě). Pro každé k ≥ 1 existují

• ČRF Ψ_{k} k + 1 proměnných

• PRP T_{k} k + 2 proměnných

• PRF U jedné proměnné

• PRF s_{k} k + 1 proměnných

takové, že

1) Ψ_{k} je univerzální funkcí pro třídu všech ČRF k proměnných.

Ψ_{k}(e, x_{1}, …, x_{k}) vyčísluje e-tou ČRF k proměnných.

Navíc z odvození ČRF lze efektivně získat e a naopak z e lze efektivně získat odvození příslušné ČRF.

2) Ψ_{k}(e, x_{1}, …, x_{k}) ≃ U(μ_{y}T_{k}(e, x_{1}, …, x_{k}, y))

3) s_{k} jsou prosté funkce rostoucí ve všech proměnných.

λx_{1}, …, x_{k} s_{k}(e, x_{1}, …, x_{k})

4) Ψ_{m+n}(e, z_{1}, …, z_{m}, x_{1}, …, x_{n}) ≃ Ψ_{n}(s_{m}(e, z_{1}, …, z_{m}), x_{1}, …, x_{n})

T_{m+n}(e, z⃗, x⃗) ≡ T_{n}(s_{m}(e, z⃗), x⃗)

5) T_{k}(e, x_{1}, …, x_{k}, y) & T_{k}(e, x_{1}, …, x_{k}, z) ⇒ y = z

Důkaz. Oklikou přes Turingovy stroje (univerzální stroj).

Univerzální TS Y blok1 Y blok2 Δ blok3 ×O_{1} × O_{2} … Y. Čísla kódujeme unárně (x jako x + 1 čar).

Základní idea: bez dat Y M Y blok2 Δ blok3 ×O_{1} × O_{2} … Y (očekáváme data).

Y || … |λ|| … |λ … λ|| … |M Konstrukce s_{m}(e, x_{1}, …, x_{m}). Chceme PRF. Zkontrolujeme, zda e po roz-

kódování obsahuje M, jestliže ne, je výsledkem nulová funkce. Jestliže ano, nejlevější výskyt M nahradíme || … |λ|| … |λ … λ|| … |M.

Věta 2. Predikát Ψ_{k}(e, x_{1}, …, x_{k}) ↓ je rekurzivně spočetný, není rekurzivní, jeho negace není rekurzivně spočetná. Dále Ψ_{k} nelze rozšířit do ORF.

Dokonce pokud α je ČRF, která je rozšířením Ψ_{k}, potom lze efektivně nalézt vstup z⃗ takový, že α(z⃗)↑.

Důkaz. Z definice je zřejmé, že Ψ_{k}(…)↓ je rekurzivně spočetný predikát.

Stačí ukázat, že ¬Ψ_{k}(…)↓ není rekurzivně spočetný. Z toho přímo plyne, že Ψ_{k}(…)↓ není rekurzivní.

Bez újmy na obecnosti uvažujme k = 1. Použijeme Cantorovu diagonální metodu.

Kdyby Ψ_{1}(…)↓ byl rekurzivní, potom by ¬Ψ_{1}(x, x)↓ byl také rekurzivní, tím spíše rekurzivně spočetný. Tedy pro nějakou ČRF φ by platilo ¬Ψ_{1}(x, x)↓⇔ φ(x) ↓. Vezmeme-li index funkce φ (označme jej x_{0}), dostáváme Ψ_{1}(x, x) ↓⇔ Ψ_{1}(x_{0}, x)↓, po dosazení x = x_{0} dostáváme ¬Ψ_{1}(x_{0}, x_{0})↓⇔ Ψ_{1}(x_{0}, x_{0})↓. Spor.

Pro důkaz zbytku tvrzení předpokládejme, že h(e, x) je ORF rozšířením Ψ_{1}(e, x). Potom 1–. h(x, x) je ORF g. Necht’ g má index x_{0}, tj. g(x) ≃ Ψ_{1}(x_{0}, x). Protože g je ORF, pro všechna x platí Ψ_{1}(x_{0}, x)↓, tím spíše Ψ_{1}(x_{0}, x_{0})↓. Tedy dostáváme h(x_{0}, x_{0}) = Ψ_{1}(x_{0}, x_{0}). Což ovšem vede ke sporu: 1–. Ψ_{1}(x_{0}, x_{0}) ≃ h(x_{0}, x_{0}) ≃ Ψ_{1}(x_{0}, x_{0}).

Dodatek: Ke každé ČRF φ(e, x), která je rozšířením univerzální ČRF, lze efektivně najít x_{0} takové, že φ(x_{0}, x_{0})↑. Důkaz je totožný.

Myšlenka obsažená v předchozím důkazu je založená na Cantorově diagonální metodě. Spor na diagonále si vynutí divergenci, nebot’ rovnost funkcí je jenom podmíněná, tedy v případě divergence je vše v pořádku.

Univerzální funkce pro danou třídu funkcí bud’ nemůže patřit do této třídy, nebo nemůže být totální.

2 Rekurzivně spočetné množiny

Definice 2. W_{x} (x-tá rekurzivně spočetná množina) = dom(φ_{x}) = {y : φ_{x}(y)↓}

Definice 3 (K). K = {x : x ∈ W_{x}} = {x : φ_{x}(x)↓} = {x : Ψ_{1}(x, x)↓}

Množina K souvisí s tzv. halting problémem, neboli problémem zastavení Turingova stroje. Platí o ní následující tvrzení.

Věta 3. Množina K je rekurzivně spočetná, není rekurzivní, \overline{K} není rekurzivně spočetná.

Důkaz. K není rekurzivní, nebot’ \overline{K} není rekurzivně spočetná. \overline{K} není rekurzivně spočetná, nebot’ kdyby byla, měla by index x_{0}. Jednoduchou diagonalizací dostáváme x_{0} ∈ \overline{K} ⇔ x_{0} ∈ W_{x_{0}} ⇔ x_{0} ∈ K. Spor.

2.1 1-převeditelnost, m-převeditelnost

Definice 4. Množina A je 1-převedilná na B (značíme A ≤_{1} B), jestliže existuje prostá ORF f taková, že x ∈ A ⇔ f(x) ∈ B.

Množina A je m-převedilná na B (značíme A ≤_{m} B), jestliže existuje ORF f (ne nutně prostá) taková, že x ∈ A ⇔ f(x) ∈ B.

Množina M je 1-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převedilná.

Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni m-převedilná.

Následující věta ukazuje, že halting problem je vzhledem k 1 a m-převoditel-nosti nejtěžší mezi rekurzivně spočetnými problémy. Věta 4. K je 1-úplná. Důkaz. Mějme libovolnou rekurzivně spočetnou množinu W_{x}.

Mějme ČRF α(y, x, w), popisující x-tou rekurzivně spočetnou množinu. Tedy

α(y, x, w)↓ ⇔ y ∈ W_{x} ⇔ Ψ_{1}(x, y)↓ ⇔ φ_{x}(y)↓ .  (2)

Provádíme obvyklý trik s fiktivní proměnnou, funkce α na hodnotě w nezáleží. Z s-m-n věty dostáváme:

α(y, x, w) ≃ Ψ_{3}(a, y, x, w) ≃ Ψ_{1}(s_{2}(a, y, x), w) ≃ φ_{s_{2}(a,y,x)}(w).  (3)

Označme h(y, x) = s_{2}(a, y, x) (s_{2} je PRF, tím spíše ORF).

y ∈ W_{x} ⇔ α(y, x, w)↓ ⇔ φ_{h(y,x)}(w)↓ ⇔ φ_{h(y,x)}(h(y, x))↓ ⇔ h(y, x) ∈ K (4)

Zde jsme mohli za w dosadit h(y, x), nebot’ hodnota α na w nezáleží! Tedy W_{x} ≤_{1} K pomocí funkce λy h(y, x). Lemma 1. K_{0} = {⟨y, x⟩ : y ∈ W_{x}} je 1-úplná. Důkaz. Zřejmé. K ≤_{1} K_{0} a K je 1-úplná. Lemma 2 (Poznámky k 1-převeditelnosti).

1) Relace ≤_{1} a ≤_{m} jsou tranzitivní, reflexivní.

2) A ≤_{1} B ⇒ A ≤_{m} B

3) B rekurzivní, A ≤_{m} B ⇒ A rekurzivní.

4) B rekurzivně spočetná, A ≤_{m} B ⇒ A rekurzivně spočetná. Důkaz.

1) Zřejmé.

2) Zřejmé.

3) Složením funkce dokazující ≤_{m} s procedurou, která rozhoduje o x ∈ B dostaneme proceduru rozhodující o A. Dostáváme c_{A}(x) = c_{B}(f(x)).

4) Stejně.

Důsledek 1. K a \overline{K} jsou m-nesrovnatelné. Důkaz. Plyne z faktu, že K je rekurzivně spočetná, \overline{K} není a z bodu 4 předchozího lemma. Definice 5 (Rekurzivní permutace). Permutace na ℕ, která je ORF, se nazývá rekurzivní permutace.

Definice 6 (Rekurzivní isomorfismus). Množiny A a B jsou rekurzivně isomorfní, jestliže existuje rekurzivní permutace p taková, že p(A) = B. Značíme A ≡ B.

Definice 7.

A ≡_{1} B, jestliže A ≤_{1} B & B ≤_{1} A.

A ≡_{m} B, jestliže A ≤_{m} B & B ≤_{m} A.

Věta 5 (Myhill). A ≡ B ⇔ A ≡_{1} B

Důkaz. Jedná se o efektivní verzi Cantor-Bernsteinovy věty.

⇒ Triviální.

⇐ Z předpokladů máme dvě prosté ORF převádějící vzájemně A na B a opačně. Chceme sestrojit rekurzivní permutaci h takovou, že h(A) = B.

Plán: v krocích budeme generovat graf h tak, že v kroce n bude platit

{0, …, n} ⊆ dom(h), {0, …, n} ⊆ rng(h).

Z toho plyne, že h bude definovaná na celém ℕ a bude na. Současně zajistíme, že h bude prostá.

Navíc budeme chtít, aby platilo y ∈ A ⇔ h(y) ∈ B, tedy aby h převáděla A na B.

Začneme v bodě 0 a položíme h(0) = f(0). Rozlišíme následující případy:

1) f(0) = 0: vše je v pořádku, h(0) = f(0) = 0 a 0 ∈ A ⇔ 0 ∈ B, pokračujeme dalším prvkem.

2) f(0) ≠ 0: rozlišíme dva podpřípady

a) g(0) ≠ 0: vše v pořádku, definujeme h(g(0)) = 0. Tedy 0 ∈ dom(h) ∩ rng(h).

b) g(0) = 0: nemůžeme použít h(g(0)) = 0, protože v bodě 0 je již h definována. Najdeme tedy volný bod. Definujme h(g(f(0))) = 0. Určitě g(f(0)) ≠ 0, protože g je prostá a f(0) ≠ 0. Tímto jsme opět dostali bod 0 do definičního oboru h i oboru hodnot. Zároveň funkci h definujeme podle f a g, tedy převádí vzájemně A na B.

Indukční krok: necht’ v kroce k je z první volný prvek. Všechna čísla menší jak z máme v dom(h)∩rng(h). Podíváme se, zda je f(z) volný. Jestliže ano, položíme h(z) = f(z). Jestliže f(z) není volný, hledám zig-zag další volný. Maximálně z prvků je blokovaných.

Důsledek 2. K ≡ K_{0}

Důkaz. Zřejmé, nebot’ K ≡_{1} K_{0}.

Množin, které jsou ekvivalentní množině K, je však mnohem více. Ještě jich mnoho uvidíme v dalším textu. Ukažme si však nyní alespoň jednu takovou. Uvažme množinu A = {x : W_{x} ≠ ∅}, tedy množinu programů, které konvergují alespoň na jednom vstupu.

A je rekurzivně spočetná, A = {x : ∃y, s (y patří do W_{x} za s kroků)}.

Ukážeme, že A ≡ K. Protože K je 1-úplná, zřejmě platí A ≤_{1} K.

Pro opačný směr chceme prostou ORF h takovou, že

x ∈ W_{x} ⇔ x ∈ K ⇔ h(x) ∈ A ⇔ W_{h(x)} ≠ ∅  (5)

Idea. Vytvoříme program, který čeká, zda x padne do K, jestliže ano, dá φ_{h(x)} všude definované. Jinak nedělá nic.

α(x, w)↓ ⇔ φ_{x}(x)↓  (6)
α(x, w) ≃ φ_{h(x)}(w)  (7)

Tedy x ∈ K znamená W_{h(x)} = ℕ. Naopak x ∉ K znamená W_{h(x)} = ∅.

Lemma 3. Q je ORF, potom ∃yQ je rekurzivně spočetný predikát.

Důkaz. μ_{y}Q je ČRF, její definiční obor je ∃y Q.

Věta 6. Predikát ∃yT_{k}(e, x_{1}, …, x_{k}, y) je univerzálním RSP pro třídu RSP k proměnných.

Důkaz. Z věty o normální formě.

Důsledek 3. Lze definovat index (Gödelovo číslo) rekurzivně spočetného predikátu.

Věta 7. Konjukce a disjunkce zachovávají rekurzivní spočetnost. Tedy průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.

Důkaz. Pro průnik spustíme oba programy současně a čekáme, až se oba zastaví. Pro sjednocení čekáme, až se zastaví alespoň jeden.

Formálně pro průnik.

∃s_{1}T_{1}(x, z, s_{1}) & ∃s_{2}T_{1}(y, z, s_{2}) ⇔ ∃w(T_{1}(x, z, (w)_{2,1}) & T_{1}(y, z, (w)_{2,2})) (8)

Uvedený predikát je rekurzivně spočetný, tedy má nějaký index.

∃sT_{3}(e, x, y, z, s) ⇔ ∃sT_{1}(s_{2}(e, x, y), z, s)

Věta 8. Omezená kvantifikace (∀y)_{y≤t} a existenční kvantifikace (pro k ≥ 2) zachovávají rekurzivní spočetnost.

Důkaz. Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem. Formálně:

(∀y)_{y≤t} ∃s T_{k}(e, x_{1}, …, x_{k−1}, y, s) ⇔  (9)
⇔ ∃ kód (k+1)-tice w (∀y)_{y≤t} T_{k}(e, x_{1}, …, x_{k−1}, y, (w)_{t+1,y})  (10)

Část s omezeným kvantifikátorem je PRP, včetně existenčního kvantifikátoru je to rekurzivně spočetný predikát, tedy má nějaký index b.

∃s T_{k+1}(b, e, x_{1}, …, x_{k−1}, t, s) ⇔ ∃s T_{k}(s_{1}(b, e), x_{1}, …, x_{k−1}, t, s). (11)

Pro existenční kvantifikátor je situace ještě jednodušší. Kvantifikaci přes dvě proměnné převedeme na kvantifikaci přes jednu, kterou budeme považovat za kód dvojice a v predikátu potom vydělíme jednotlivé složky. Dostáváme predikát k−1 proměnných, proto požadavek na minimální velikost k!

∃y∃s T_{k}(e, x_{1}, …, x_{k−1}, y, s) ⇔ ∃w T_{k}(e, x_{1}, …, x_{k−1}, (w)_{2,1}, (w)_{2,2}) (12)
⇔ ∃s T_{k}(d, e, x_{1}, …, x_{k−1}, s) ⇔ ∃s T_{k−1}(s_{1}(d, e), x_{1}, …, x_{k−1}, s) (13)

Věta 9. Něcht’ Q je RSP k + 1 proměnných. Potom existuje ČRF φ k proměnných taková, že

φ(x_{1}, …, x_{k})↓ ⇔ ∃y Q(x_{1}, …, x_{k}, y)  (14)
φ(x_{1}, …, x_{k})↓ ⇒ Q(x_{1}, …, x_{k}, φ(x_{1}, …, x_{k}))  (15)

Důkaz. Věta říká, že pro každý rekurzivně spočetný predikát existuje ČRF taková, že konverguje právě, když existuje y splňující predikát. Tato funkce navíc přímo vrací jedno takové y, pro které predikát platí. Tato φ je selektor na grafu Q.

Pro k = 1. Dáno x, hledáme nejmenší dvojici (y, s) takovou, že za s kroků ověříme, že Q(x, y) (tj. program pro Q konverguje za s kroků). Pak vydáme y.

Obecně: univerzální vyjádření RSP ∃s T_{2}(e, x, y, s), hledáme nejmenší w (kód dvojice) tak, že

φ(x) ≃ (μ_{w}T_{2}(e, x, (w)_{2,1}, (w)_{2,2}))_{2,1}.  (16)

Funkce φ tedy vrací první složku z první dvojice, kterou najde (v uspořádání daném naším kódováním dvojic).

Věta 10. Funkce je ČRF ⇔ má rekurzivně spočetný graf.

Důkaz. Je-li φ ČRF, je její graf rekurzivně spočetný: ⟨x_{1}, …, x_{k}, y⟩ ∈ Graf ⇔ ∃s za s kroků program konverguje.

Opačně, je-li graf funkce φ rekurzivně spočetný, je selektor na něm ČRF, ale selektor na grafu funkce je přímo ona funkce.

Věta 11 (Postova).

Množina M je rekurzivní právě, když M i \overline{M} jsou rekurzivně spočetné. Predikát Q je ORP právě, když Q i ¬Q jsou RSP.

Důkaz. ”⇒”: Triviální.

”⇐”: Intuitivně: M = dom(P_{1}), \overline{M} = dom(P_{2}). Pustíme oba programy současně a čekáme, který se zastaví. Zastaví se právě jeden.

Formálně: (x ∈ M & y = 1) ∨ (x ∈ \overline{M} & y = 0) je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro M.

Lemma 4. Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz. Vytvoříme množinu dvojic R = {⟨z, y⟩ : z ∈ W_{x} & y = z}. Množina R je rekurzivně spočetná, tedy má ČRF selektor φ, platí dom(φ) = rng(φ) = W_{x}.

Myšlenka toho důkazu je, že body, kde φ_{x} konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

Věta 12. Každý obor hodnot ČRF je rekurzivně spočetná množina.

Důkaz. Zkontruujeme pseudoinverzní funkci h k ČRF φ.

2.2 Generování rekurzivně spočetných množin

Definice 8. Funkce f je úseková, jestliže jejím definičním oborem je počáteční úsek ℕ (nebo celé ℕ).

Věta 13. Rekurzivní množiny jsou právě obory hodnot rostoucích úsekových ČRF.

Důkaz. Definujeme ČRF f, která bude rostoucí a úseková.

Začneme f(0) ≃ μ_{x}(x ∈ M).

Dále f(n + 1) ≃ μ_{y}(y > f(n) & y ∈ M)

Opačně. Máme f rostoucí úsekovou ČRF. V případě, že je f konečná (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe D = dom(f) a tedy rng(f) je rekurzivní.

V případě, že je f totální

y ∈ M = rng(f) ⇔ ∃x(f(x) = y)) ⇔ ∃x≤y(f(x) = y)  (17)

Poslední ekvivalence platí, protože f je rostoucí a úseková. Tedy

y ∈ M ⇔ y ∈ {f(0), …, f(y)}.  (18)

Věta 14. Množina M je nekonečná a rekurzivní právě, když je oborem hodnot rostoucí ORF. Tedy M lze generovat prostou ORF.

Důkaz. Důsledek následující věty.

Věta 15. Rekurzivně spočetné množiny jsou právě obory hodnot prostých úsekových ČRF.

Důkaz. ”⇐”: Víme, obor hodnot ČRF je rekurzivně spočetná množina. ”⇒”: Mějme ČRF φ. Důkaz provedeme pomocí rekurzivní množiny

B = {⟨x, s⟩ : φ(x)↓ přesně za s kroků}.  (19)

Množinu B lze, protože je rekurzivní, generovat pomocí rostoucí úsekové ČRF h. Funkce h generuje dvojice, definujeme tedy g(x) ≃ (h(x))_{2,1}. Zřejmě g je prostá, úseková a ČRF (a generuje dom(φ)).

Důsledek 4. Každá nekonečná rekurzivně spočetná množina obsahuje nekonečnou rekurzivní podmnožinu.

Důkaz. Mějme f, která prostě generuje M. Vyber rostoucí podposloupnost. Ta je rekurzivní.

g(0) = f(0)  (20)
g(n + 1) = f(μ_{j}(f(j) > g(n)))  (21)

Obor hodnot g je nekonečné rekurzivní množina a je podmnožinou M.

Definice 9 (Imunní množina). Množina M je imunní, jestliže M je nekonečná a neobsahuje nekonečnou rekurzivně spočetnou podmnožinu.

Definice 10 (Simple množina). Množina A je simple, jestliže A je rekurzivně spočetná a \overline{A} je imunní.

Lemma 5. Existuje imunní množina.

Důkaz. Nejprve neefektivní konstrukce. Budeme požadovat, aby M byla nekonečná a od každé nekonečné rekurzivně spočetné se lišila alespoň v jednom bodě. Naše strategie bude dát do M mnoho prvků a potom, kdykoliv je W_{x} nekonečná, vzít nějaký prvek z W_{x}, který je ještě volný, a ten dát do \overline{M}.

Krok s. Nějaký volný prvek dáme do M. Vezmu W_{s}, zeptám se, zda je W_{s} nekonečná (neefektivní krok!), pokud ano, vezmu nějaký volný prvek z W_{s} a dám jej do \overline{M}. V kroce s je blokováno nejvýše 2s+2 prvků, tedy vždy můžeme volit.

Nyní si ukážeme efektivní konstrukci.

Problém je rozhodnout, zda W_{x} je nekonečná. Nebudeme se tedy ptát, zda je nekonečná, ale odstraníme všechny ”hodně velké” množiny. V kroce s odstraníme množinu W_{s}, jestliže W_{s} obsahuje prvek větší jak 2s.

Q(x, y) ⇔ y ∈ W_{x} & y > 2x  (22)

Q je rekurzivně spočetná relace, její selektor φ je ČRF. Necht’ A = rng(φ), potom \overline{A} je hledaná množina.

Ověření, že \overline{A} splňuje požadované vlastnosti. Pro j ≥ x platí φ(j) > 2x (pokud konverguje). Tedy příspěvky do W_{x}, W_{x+1}, … jsou všechny větší než 2x. Do množiny 0, …, 2x mohou tedy přispět jenom množiny W_{0}, …, W_{x−1}. Máme tedy 2x + 1 čísel, šanci má jenom x, tedy nejméně x + 1 z nich zůstane mimo A, tj. padnou do \overline{A}. Tedy \overline{A} je nekonečná.

Ověřme druhou podmínku. Je-li W_{x} nekonečná, potom nemůže být podmnožinou \overline{A}. Dokonce platí W_{x} ⊆ \overline{A} ⇒ W_{x} ⊆ \{0, …, 2x\}.

Výše uvedená konstrukce dokonce dává konstrukci simple množiny množiny..

Definice 11.

T ot = {x : W_{x} = ℕ}  (23)
Inf = {x : W_{x} nekonečná}  (24)
F in = {x : W_{x} konečná}  (25)

Věta 16. Tot ≡ Inf

Důkaz. Stačí dokázat Tot ≤_{1} Inf a Inf ≤_{1} Tot.

Definujme α(x, w)↓ ⇔ ∀j =0, …, w φ_{x}(j)↓

Z s-m-n věty dostaneme α(x, w) ≃ φ_{h(x)}(w).

Jestliže x∈T ot, potom W_{h(x)} = ℕ. Naopak pro x∉T ot je W_{h(x)} konečná. Naopak, definujme β(x, w)↓ ⇔ W_{x} obsahuje alespoň w prvků. Z s-m-n věty dostaneme β(x, w) ≃ φ_{g(x)}(w). Jestliže w ∈Inf, potom g(x) ∈ T ot. Naopak pro w ∉Inf je g(x) ∉ T ot.

Definice 12 (Hyperimunní množina). Množina B je hyperimunní, jestliže je nekonečná a neexistuje ORF f taková, že majorizuje množinu B.

Definice 13. Říkáme, že ORF f majorizuje nekonečnou množinu B, jestliže B = {x_{0}, x_{1}, x_{2}, …} je rostoucí seznam prvků B a platí f(n) ≥ x_{n}.

Definice 14 (Hypersimple množina). Množina A je hypersimple, jestliže A je simple a \overline{A} je hyperimunní.

Lemma 6. Hyperimunní množina je imunní.

Důkaz. Sporem. Necht’ hyperimunní A není imunní. Potom mám nekonečnou rekurzivně spočetnou množinu W_{z}, kterou A obsahuje.

Definujeme D_{f(i)} = i-tý bod W_{z}. Dostali jsme nekonečnou posloupnost konečných (jednobodových) množin, které všechny protínají A. Spor.

Věta 17. Množina A je hyperimunní ⇔ A je nekonečná a neexistuje ORF f taková, že

∀n(D_{f(n)} ∩ A ≠ ∅) & ∀i, j (i≠j ⇒ D_{f(i)} ∩ D_{f(j)} = ∅).  (26)

Zde D_{x} označuje x-tou konečnou množinu. Požadujeme tedy, aby neexistovala ORF vybírající prostým způsobem konečné množiny tak, aby všechny vybrané měly neprázdný průnik s A.

Důkaz. ”⇒”: Dokážeme, že negace pravé strany implikuje negaci levé strany. Tedy A je konečná nebo existuje ORF taková, že

∀n(D_{f(n)} ∩ A ≠ ∅) & ∀i, j (i≠j ⇒ D_{f(i)} ∩ D_{f(j)} = ∅).  (27)

Je-li A konečná, nemůže být hyperimunní. Existuje-li taková f, zvolme g(n) = max(⋃_{j=0}^{n} D_{f(j)}). Potom g(n) majorizuje A. Zřejmé.

Opačnou implikaci budeme opět dokazovat jako převrácenou implikaci negací. Necht’ A není hyperimunní, tedy máme g, která ji majorizuje. Položme

h(0) = g(0)  (28)
h(n + 1) = g(h(n) + 1)  (platí g(h(n) + 1) ≥ x_{h(n)+1})  (29)

Zvolíme f následovně

D_{f(0)} = {0, …, h(0)}  (30)
D_{f(n+1)} = {h(n) + 1, …, h(n + 1)}  (31)

Protože platí g(h(n) + 1) ≥ x_{h(n)+1}, což je h(n) + 2 prvků, je každá D_{f(n)} neprázdná.

Věta 18 (Existence hypersimple množiny). Existuje hypersimple množina.

Důkaz. Pracný, pokud se provádí přímo diagonalizací.

Věta 19 (Dekker). Necht’ množina A je rekurzivně spočetná, nerekurzivní, potom existuje B hypersimple.

Důkaz. Množina A je zřejmě nekonečná. Existuje f prostá ORF generující A. Definujeme

B = {x : ∃y(y > x ∧ f(y) < f(x))}  (32)
\overline{B} = \{x : ∀y(y > x ⇒ f(y) > f(x))\}  (33)

Lze ukázat, že \overline{B} je nekonečná (plyne to z faktu, že f generuje množinu A prostě).

Neexistuje ORF majorizující B. Kdyby ano, potom by A byla rekurzivní. Tj. g necht’ je ORF majorizující \overline{B}.

x ∈ A ⇔ x ∈ rng(f) ⇔ x ∈ {f(0), …, f(g(x))}.  (34)

Spor.

Ukažme ještě, že A a B jsou stejně složité ve smyslu vyčíslitelnosti, tedy že z jedné vypočítám druhou.

Mám-li B a potřebuji rozhodnout o x ∈ A, najdu prvních x + 1 prvků z \overline{B}, necht’ poslední z nich je w.

x ∈ A ⇔ z ∈ {f(0), …, f(w)}  (35)

Naopak, mám-li A a rozhoduji, zda x ∈ B.

x ∈ B ⇔ ∃y(y > x ∧ f(y) < f(x))  (36)
x ∈ B ⇔ ({0, …, f(x)} \ {f(0), …, f(x)}) ∩ A ≠ ∅.  (37)

Věta 20 (Matijasevič). Predikát P je rekurzině spočetný právě, když je diofantický, tj. existují 2 polynomy s přirozenými koeficienty p_{1}, p_{2} takové, že

P (y_{1}, …, y_{n}) ⇔ ∃x_{1}, …, x_{k}(p_{1}(y⃗, x⃗) = p_{2}(y⃗, x⃗))  (38)

3 Věty o rekurzi

Věta 21 (O rekurzi). Jestliže f je ČRF jedné proměnné, potom existuje a takové, že φ_{f(a)}(x) ≃ φ_{a}(x) pro všechna x.

Důkaz.

λz,x (φ_{f(s_{1}(z,z))}(x)) ≃ Ψ_{2}(e, z, x) ≃ φ_{s_{1}(e,z)}(x)  (39)

Dosadíme z = e a dostáváme hledané a = s_{1}(e, e). Platí totiž

φ_{f(s_{1}(e,e))}(x) ≃ Ψ_{2}(e, e, x) ≃ φ_{s_{1}(e,e)}(x).  (40)

Funkce f zobrazuje program na program. Bod a je pevný bodem zobrazení f. Jak vypadají programy a a f(a)? Který z nich počítá déle? Uvidíme, že program a počítá déle, než f(a).

Co dělá program e na datech (z, x)? Počítá φ_{f(s_{1}(z,z))}, tj. vezme z a spočítá neprve s_{1}(z, z), potom f(s_{1}(z, z)), který ale nemusí konvergovat. Jestliže f(s_{1}(z, z))↓, spustí se na vstup x.

Co dělá program a? Program a vznikne jako s_{1}(e, e). Mějme na vstupu x. Program a vezme e a přidá ho k x a spustí program e na (e, x). Co udělá program e na těchto datech? Spočítá s_{1}(e, e) (tedy spočítá a), potom f(s_{1}(e, e)) = f(a) a spustí program f(a) na x.

Program a tedy neprve spočítá a, potom spočítá f(a) (pokud konverguje) a ten simuluje na vstupu x. Program a je tedy složitější než f(a) a počítá déle.

Věta 22 (O generování pevných bodů). Pro každou f ∈ ČRF existuje prostá rostoucí PRF g taková, že platí:

φ_{f(g(j))}(x) ≃ φ_{g(j)}(x) (41)

Tedy g rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce f.

Důkaz. φ_{f(s_{2}(z,z,j))}(x) ≃ ψ(e, z, j, x) ≃ φ_{s_{2}(e,z,j)}(x).

Zvolme g(j) = s_{2}(e, e, j).

Věta 23 (??). Necht’ h je ČRF n+1 proměnných. Potom existuje číslo a takové, že a je indexem funkce λ_{x_{1},...,x_{n}}h(a, x_{1}, …, x_{n}), tedy platí φ_{a}(x_{1}, …, x_{n}) ≃ h(a, x_{1}, …, x_{n})

Důkaz. h(v, x_{1}, …, x_{n}) ≃ ψ_{n+1}(b, v, x_{1}, …, x_{n}) ≃ φ_{s_{1}(b,v)}(x_{1}, …, x_{n})

Následně aplikujeme větu o rekurzi na s_{1}(b, v) v proměnné v a dostáváme hledané a.

Věta 24 (Věta o rekurzi v závislosti na parametrech). Jestliže f je ČRF n + 1 proměnných, potom existuje PRF g n proměnných taková, že

φ_{h(g(y_{1},...,y_{n}),y_{1},...,y_{n})}(x) ≃ φ_{g(y_{1},...,y_{n})}(x)

Důkaz.

φ_{h(s_{n+1}(z,z,y_{1},...,y_{n}),y_{1},...,y_{n})}(x) ≃ ψ_{n+2}(e, z, y_{1}, …, y_{n}, x) ≃ φ_{s_{n+1}(e,z,y_{1},...,y_{n})}(x)

Zvolme g(y_{1}, …, y_{n}) = s_{n+1}(e, e, y_{1}, …, y_{n}).

Věta 25 (Rice). Jestliže A je třída ČRF (jedné proměnné), která je netriviální, potom A_{A} = {x : φ_{x} ∈ A} je nerekurzivní.

Důkaz. Sporem. Necht’ A je rekurzivní. Potom lze vytvořit ORF f takovou, že všechny prvky z A zobrazí na nějaký prvek b ∉ A a všechny prvky mimo A zobrazí na nějaký prvek a ∈ A. Podle věty o rekurzi existuje pevný bod f u_{0}, tedy platí:

φ_{u_{0}} = φ_{f(u_{0})} (42)

Tedy

u_{0} ∈ A ⇒ f(u_{0}) = b ∉ A  (43)
u_{0} ∉ A ⇒ f(u_{0}) = a ∈ A  (44)

To je ovšem spor, protože u_{0} a f(u_{0}) jsou indexy stejné funkce, a tedy bud’ obě čísla v A leží nebo obě neleží.

Pozor, nejedná se o třídu programů, ale třídu funkcí. Tedy i pro jednoprvkovou A bude A_{A} nekonečná a nerekurzivní (každá funkce je vyčíslovaná nekonečně mnoha programy a rozhodnout o jejich ekvivalenci je nelze efektivně). Viz následující důsledek.

Důsledek 5. Necht’ A = {φ_{e}}, potom A = {x : φ_{x} = φ_{e}} je nerekurzivní. Rozhodnout o rovnosti funkcí vyčíslovaných dvěma programy nelze algoritmicky.

4 Produktivní a kreativní množiny

Definice 15 (Produktivní množina). Množina B je produktivní, jestliže existuje ČRF φ taková, že W_{x} ⊆ B ⇒ φ(x)↓ & φ(x) ∈ B \ W_{x}

Definice 16 (Kreativní množina). Množina A je kreativní, jestliže A je rekurzivně spočetná a \overline{A} je produktivní.

Věta 26 (O produktivní funkci). Každá produktivní množina má produktivní funkci, která je ORF.

Důkaz. Mějme nějakou ČRF f produktivní pro B.

W_{g(y)} = \{ \begin{matrix}W_{y} & jestliže f(g(y))↓ \\ ∅ & jestliže f(g(y))↑ \end{matrix}

f(g(y)) nemůže divergovat, protože potom by W_{g(y)} bylo rovno prázdné množině, která je ale triviálně podmnožinou B. Tedy by f(g(y)) muselo konvergovat a vracet prvek mimo B. Což by byl spor.

f(g(y)) tedy konverguje a W_{g}(y) = W_{y}, tedy pokud W_{y} ⊆ B, potom také W_{g(y)} ⊆ B a tedy f(g(y)) musí konvergovat a vracet prvek mimo W_{g(y)} (což je rovno W_{y}), tedy nový prvek f(g(y)) ∈ B \ W_{y}.

Konstrukci g provedeme pomocí věty o rekurzi. Mějme pomocnou ORF h takovou, že platí

W_{h(x,y)} = \{ \begin{matrix}W_{y} & jestliže f(x)↓ \\ ∅ & jestliže f(x)↑ \end{matrix}  (45)

Takovou h získáme pomocí s-m-n věty následovně.

α(x, y, w)↓⇔ f(x)↓ & w ∈ W_{y}  (46)

Aplikací s-m-n věty dostaneme h. Nyní použijeme větu o rekurzi.

∃ PRF g : W_{g(y)} = W_{h(g(y),y)} = \{ \begin{matrix}W_{y} & jestliže f(g(y))↓ \\ ∅ & jestliže f(g(y))↑ \end{matrix}  (47)

Věta 27. Každá produktivní množina obsahuje nekonečnou rekursivně spočetnou množinu.

Důkaz. Neformálně. Mějme množinu A a její produktivní funkci f. Začneme s W_{z_{0}} = ∅ a aplikujeme f. Dostáváme první prvek f(z_{0}) ∈ A. W_{z_{1}} = {f(z_{0})} atd.

Důsledek 6. Produktivní množiny nejsou imunní, imunní nejsou produktivní.

Věta 28 (O rekurzivní permutaci). Každá produktivní množina má produktivní funkci, která je rekurzivní permutací, tj. je prostá a na.

Důkaz. Mějme funkci f produktivní pro množinu A.

Dvě strategie, jedna pro na a jedna pro prostá.

na:

Snadno nalezneme nekonečnou rekurzivní množinu M takovou, že x ∈ M ⇒ W_{x} = ℕ a tedy jistě x ∈ M ⇒ W_{x} ⊈ A.

Definujeme

g(x) = \{ \begin{matrix}f(x) & x ∉ M \\ j & x ∈ M & x je j-tým prvkem M. \end{matrix}  (48)

Takto definovaná g je jistě produktivní (W_{x} ⊆ A ⇒ x ∉ M a tedy platí g(x) = f(x)) a na (M je nekonečná).

prostá:

h(0) = f(0)  (49)
h(n + 1) = \{ \begin{matrix}f(n + 1) & f(n + 1) ∉ \{h(0), …, h(n)\} \\ ? & f(n + 1) ∈ \{h(0), …, h(n)\} \end{matrix}  (50)

V případě, že je f(n + 1) již blokovaná, přidáme k W_{n+1} prvek f(n + 1) a aplikujeme na index této množiny funkci f. V případě, že platilo W_{n+1} ⊆ A, dostáváme iterací tohoto postupu prostou posloupnost prvků, z nichž maximálně n je blokovaných. První neblokovaný zvolíme jako h(n + 1). V případě, že opakováním nedostaneme neblokovaný prvek, muselo platit W_{n+1} ⊈ A, tedy můžeme volit libovolně (ale prostě).

Spojením těchto dvou strategií dostáváme funkci, která je na a prostá.

Věta 29 (O ekvivalenci pojmů). A je kreativní ⇔ A je 1-úplná ⇔ A je m-úplná.

Důkaz. Plyne přímo z následující věty.

Věta 30 (O ekvivalenci pojmů II). B je produktivní ⇔ \overline{K} ≤_{1} B ⇔ K̄ ≤_{m} B

Důkaz. 2 ⇒ 3: triviální 3 ⇒ 1:

Lemma 7. Jestliže množina C je produktivní a C ≤_{m} B, potom i B je produktivní. Produktivita se tedy zachovává směrem vzhůru při ≤_{m}.

Důkaz. Neformálně: necht’ W_{x} ⊆ B, hledáme nový bod mimo W_{x}. Vezmeme vzor W_{x} při f, kde h je funkce dokazující ≤_{m}.

Platí h^{−1}(W_{x}) ⊆ C, protože h musí převádět C na B. Tedy můžeme na index množiny h^{−1}(W_{x}) aplikovat funkci f, která je produktivní pro C. Dostáváme bod mimo h^{−1}(W_{x}) a tedy jeho obraz při h musí padnout mimo W_{x}.

Formálně: Existuje ORF g taková, že složení h ∘ f ∘ g je hledaná produktivní funkce pro B. (Funkce g vrací index množiny h^{−1}(W_{x}).) W_{g(x)} = h^{−1}(W_{x}) = {y : h(y) ∈ W_{x}} (g ze s-m-n věty)

W_{x} ⊆ B ⇒ W_{g(x)} ⊆ C ⇒ f(g(x)) ∈ C \ W_{g(x)} ⇒ hfg(x) ∈ B \ W_{x} (51)

Protože \overline{K} je produktivní, je i B dle předchozího lemma produktivní.

1 ⇒ 2: (B produktivní ⇒ \overline{K} ≤_{1} B) Cíl: prostá ORF g taková, že

W_{g(x)} = \{ \begin{matrix}\{f(g(x))\} & x ∈ K \\ ∅ & x ∉ K \end{matrix} (52)

Potom platí:

x ∈ \overline{K} ⇒ W_{g(x)} = ∅ ⊆ B ⇒ fg(x) ∈ B \ W_{g(x)} ⇒ fg(x) ∈ B  (53)
x ∈ K ⇒ W_{g(x)} = {f(g(x))}  (54)

Situace f(g(x)) ∈ B nemůže nastat, protože potom by

W_{g(x)} ⊆ B ⇒ f(g(x)) ∈ B \ W_{g(x)},  (55)

ale protože platí W_{g(x)} = {f(g(x))}, muselo by platit f(g(x)) ∈ B \ {f(g(x))}, což nelze. Proto musí platit f(g(x)) ∈ \overline{B}.

Tedy h = f ∘ g 1-převádí \overline{K} do B.

Pro pořádek ukážeme konstrukci g. Pomocí s-m-n věty a věty o rekurzi.

W_{α(x,y)} = \{ \begin{matrix}\{f(y)\} & x ∈ K \\ ∅ & x ∉ K \end{matrix} (56)

Potřebné α dostaneme pomocí s-m-n věty následovně.

β(x, y, w)↓ ⇔ y ∈ K & w = f(y) (57)

Nyní použijeme větu o rekurzi.

W_{g(x)} = W_{α(x,g(x))} = \{ \begin{matrix}\{f(g(x))\} & x ∈ K \\ ∅ & x ∉ K \end{matrix} (58)

Definice 17 (Úplně produktivní množina). Množinu A nazveme úplně produktivní množinou, když existuje ORF f taková, že

f(x) ∈ A \ W_{x} nebo f(x) ∈ W_{x} \ A (59)

Lemma 8. Úplná produktivita implikuje produktivitu.

Důkaz. Zřejmé. Jestliže platí W_{x} ⊆ A, potom W_{x} \ A = ∅ a tedy musí nastat případ f(x) ∈ A \ W_{x}, což dokazuje produktivitu A.

Věta 31 (O úplné produktivitě). A je produktivní ⇔ A je úplně produktivní.

Důkaz. Produktivita se zachovává při ≤_{m} a ≤_{1}. Stejně tak se zachovává úplná produktivita (důkaz je totožný).

\overline{K} je úplně produktivní (a to dokonce při identické funkci - snadno se ověří, že (x ∈ \overline{K} \ W_{x}) ∨ (x ∈ W_{x} \ \overline{K}). Zbytek je zřejmý.

Důsledek 7. Protože \overline{K} ≤_{m} T ot = \{x : φ_{x} totální \} = \{x : W_{x} = ℕ\}, platí T ot je produktivní.

5 Dvojice množin

Definice 18 (Rekurzivní neoddělitelnost). Dvojice množin A, B (A ∩ B = ∅) je rekurzivně neoddělitelná, jestliže neexistuje rekurzivní množina M taková, že

A ⊆ M, M ∩ B = ∅ (tj. B ⊆ \overline{M}) (60)

Definice 19 (Efektivní neoddělitelnost). Dvojice množin A, B (A∩B = ∅) je efektivně neoddělitelná, jestliže existuje ČRF φ taková, že

\begin{matrix}A ⊆ W_{x} \\ B ⊆ W_{y} \\ W_{x} ∩ W_{y} = ∅ \end{matrix} \} ⇒ φ(x, y)↓ & φ(x, y) ∉ W_{x} ∪ W_{y} (61)

Jinými slovy, z indexů aproximace A a B efektivně naleznu další bod, který leží mimo tuto aproximaci.

Lemma 9. Efektivní neoddělitelnost je silnější než rekurzivní neoddělitelnost

Důkaz. Sporem. Zvolme W_{x} = M a W_{y} = \overline{M}, kde M je rekurzivní množina vyvracející rekurzivní neoddělitelnost. Funkce dokazující efektivní neoddělitelnost by musela nelézt bod mimo M ∪ \overline{M}, což nelze.

Lemma 10. Existuje dvojice rekurzivně spočetných disjunktních množin A, B taková, že A, B jsou rekurzivně neoddělitelné, ale nejsou efektivně neoddělitelné.

Důkaz. Těžký.

Věta 32 (Existence efektivně neoddělitelné dvojice). Existují disjunktní rekurzivně spočetné množiny A a B, které jsou efektivně neoddělitelné.

Důkaz. Definujeme:

A = {x : φ_{x}(x) ≃ 0}  B = {x : φ_{x}(x) ≃ 1}  (62)

A a B jsou zřejmě disjunktní a rekurzivně spočetné. Podle s-m-n věty existuje PRF α taková, že

φ_{α(x,y)}(w) ≃ \{ \begin{matrix}1 & w padne dříve do W_{x} než do W_{y} \\ 0 & w padne dříve do W_{y} než do W_{x} \\ ↑ & w ∉ W_{x} ∪ W_{y} \end{matrix} (63)

Prostou diagonalizací nalezneme bod, na kterém musí φ_{α(x,y)} divergovat, protože jinak bychom došli ke sporu. Divergence α ale znamená, že daný bod leží mimo W_{x} ∪ W_{y}.

Formálně. Co udělá φ_{α(x,y)}(α(x, y))? Kdyby α(x, y) padlo do W_{x}, potom zřejmě padne dříve do W_{x} než do W_{y}, φ_{α(x,y)}(α(x, y)) by zakonvergovalo a vrátilo 1 a tedy by muselo α(x, y) padnout do B. To nelze. Symetricky se ukáže, že α(x, y) nemůže padnout do W_{y}. Tedy padne mimo tyto dvě množiny.

Definice 20 (1-úplnost dvojic). Disjunktní dvojice rekurzivně spočetných množin A, B je 1-úplná, jestliže pro libovolnou disjunktní dvojici rekurzivně spočetných množin C, D existuje prostá ORF f taková, že

x ∈ C ⇔ f(x) ∈ A  (64)
x ∈ D ⇔ f(x) ∈ B  (65)
x ∉ C ∪ D ⇔ f(x) ∉ A ∪ B  (66)

Značíme (C, D) ≤_{1} (A, B).

Věta 33 (Dvojná forma věty o rekurzi). Pro libovolné ORF f, g existují m a n takové, že

φ_{m} = φ_{f(m,n)}  φ_{n} = φ_{g(m,n)}  (67)

Obecnější znění: pro libovolné ORF f, g obě k+2 proměnných existují PFR ω_{1}, ω_{2} obě k proměnných takové, že

φ_{ω_{1}(y_{1},...,y_{k})} = φ_{f(ω_{1}(y_{1},...,y_{k}),ω_{2}(y_{1},...,y_{k}),y_{1},...,y_{k})}  (68)
φ_{ω_{2}(y_{1},...,y_{k})} = φ_{g(ω_{1}(y_{1},...,y_{k}),ω_{2}(y_{1},...,y_{k}),y_{1},...,y_{k})}  (69)

Důkaz. Mějme φ_{f(x,y)}, pomocí věty o rekurzi dostaneme funkci α takovou, že φ_{f(α(y),y)} = φα(y). Vezmeme φ_{g(α(y),y)}, aplikujeme na g větu o rekurzi a dostáváme n takové, že φ_{n} = φ_{g(α(n),n)}. Nyní stačí volit m = α(n).

Jinými slovy, nalezneme funkci α, která nám bude počítat pevné body v závilosti na druhé proměnné. Potom opětovnou aplikací věty o rekurzi získáme pevný bod této funkce. Jako m volíme hodnotu α v pevném bodě.

Věta 34. 1-úplné dvojice rekurzivně spočetných množin jsou právě efektivně neoddělitelné dvojice rekurzivně spočetných množin.

Důkaz. 1-úplnost ⇒ efektivní neoddělitelnost

Mějme (A, B) efektivně neoddělitelné (s funkcí f, která to dokazuje), (C, D) 1-úplná, tedy platí (A, B) ≤_{1} (C, D) (via h). Vezmeme vzory W_{x} a W_{y} při h, aplikujeme f a opět aplikujeme h.

efektivní neoddělitelnost ⇒ 1-úplnost

Necht’ (A, B) jsou efektivě neoddělitelné, tj. existuje ČRF f, která to dokazuje. Budeme hledat dvojici ORF funkcí ω_{1}, ω_{2} takové, že

W_{ω_{1}(x)} = \{ \begin{matrix}A ∪ \{f(ω_{1}(x), ω_{2}(x))\} & x ∈ D \\ A & x ∉ D \end{matrix}  (70)

W_{ω_{2}(x)} = \{ \begin{matrix}B ∪ \{f(ω_{1}(x), ω_{2}(x))\} & x ∈ C \\ B & x ∉ C \end{matrix}  (71)

Snadno se nahlédne, že potom platí:

x ∉ C ∪ D ⇒ \begin{matrix}W_{ω_{1}(x)=A} \\ W_{ω_{2}(x)=B} \end{matrix} \} ⇒ f(ω_{1}(x), ω_{2}(x)) ∉ A ∪ B  (72)

x ∈ C ⇒ x ∉ D ⇒ \begin{matrix}W_{ω_{1}(x)=A} \\ W_{ω_{2}(x)=B∪\{f(ω_{1}(x),ω_{2}(x))\}} \end{matrix}  (73)

Kdyby f(ω_{1}(x), ω_{2}(x)) ∉ A, potom by W_{ω_{1}(x)}, W_{ω_{2}(x)} byly korektní nadobaly množin A a B, tedy by funkce f na jejich indexech musela vracet nový bod, tj.

f(ω_{1}(x), ω_{2}(x)) ∉ W_{ω_{1}(x)} ∪ W_{ω_{2}(x)},  (74)

ale to je spor, protože f(ω_{1}(x), ω_{2}(x)) ∈ W_{ω_{2}(x)}. Tedy platí f(ω_{1}(x), ω_{2}(x)) ∈ A. Analogicky se ukáže případ x ∈ D. Zbývá ukázat konstrukci funkcí ω_{1} a ω_{2}. Ty dostaneme pomocí dvojné formy

věty o rekurzi.

W_{α(y_{1},y_{2},x)} = \{ \begin{matrix}A ∪ \{f(y_{1}, y_{2})\} & x ∈ D \\ A & x ∉ D \end{matrix}  (75)
W_{β(y_{1},y_{2},x)} = \{ \begin{matrix}B ∪ \{f(y_{1}, y_{2})\} & x ∈ C \\ B & x ∉ C \end{matrix}  (76)

6 Gödelovy věty

Věta 35 (Gödelova věta o neúplnosti - 1. část). V rozumných teoriích je množina dokazatelných a vyvratitelných formulí efektivně neoddělitelná dvojice.

Definice 21 (Základní aritmetická síla). Jazyk prvního řádu:

\overline{0} - numerál pro nulu

\overline{1} - numerál pro jedničku (aby neexistoval jednoprvkový model)

+, × - funkční symboly

konečně mnoho axiomů

Definice 22 (Axiomatizovatelnost). Teorie T je axiomatizovatelná, jestliže množina dokazatelných formulí v T je rekurzivně spočetná.

Věta 36 (Gödelova věta). Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak

1) množina formulí dokazatelných v T není rekurzivní

2) je-li T navíc axiomatizovatelná, pak

a) existuje uzavřená formule F taková, že F je nerozhodnutelná v T (tj. T ⊬ F, T ⊬ ¬F)

b) v T nelze dokázat vlastní bezespornost (za nepatrně silnějších předpokladů o teorii T).

7 Reprezentovatelnost ČRF v teoriích ZAS

Definice 23 (Reprezentovatelnost). ČRF f je reprezentovatelná v teorii T, která má základní aritmetickou sílu, jestliže existuje formule F taková, že

f(x_{1}, …, x_{n}) ≃ y ⇒ ⊢_{T} F (\overline{x_{1}}, …, \overline{x_{n}}, \overline{y})  (77)
⊢_{T} F (α_{1}, …, α_{n}, β) & ⊢_{T} F (α_{1}, …, α_{n}, γ) ⇒ β = γ  (78)

Věta 37 (O reprezentovatelnosti). Každá ČRF je reprezentovatelná v libovolné teorii ZAS, dokonce existuje pro každou ČRF formule, která ji reprezentuje ve všech teoriích ZAS současně, je to dokonce Σ_{1}-formule.

Důkaz. Pomocí Matijasevičovy věty.

Důsledek 8. Jsou-li A a B disjunktní rekurzivně spočetné množiny, potom existuje Σ_{1}-formule G taková, že

x ∈ A ⇒ ⊢_{T} G(\overline{x})  (79)
x ∈ B ⇒ ⊢_{T} ¬G(\overline{x})  (80)

Důkaz. Návod:

φ(x) ≃ \{ \begin{matrix}1 & x ∈ A \\ 0 & x ∈ B \\ ↑ & x ∉ A ∪ B \end{matrix} (81)

Důkaz. Nyní dokážeme Gödelovu větu. Vezmeme A, B rekurzivně spočetné, efektivně neoddělitelné. Mějme formuli G, která je popisuje ve smyslu předchozího lemmatu.

A_{1} = \{x : ⊢_{T} G(\overline{x})\} (A ⊆ A_{1})  (82)
B_{1} = \{x : ⊢_{T} ¬G(\overline{x})\} (B ⊆ B_{1})  (83)

Z bezespornosti plyne, že A_{1} ∩ B_{1} = ∅, navíc ani jedna nemůže být rekurzívní, protože by separovala A, B a tedy vztah dokazatelnosti v T není rekurzivní.

Přidáme-li navíc předpoklad axiomatizovatelnosti T, jsou A_{1}, B_{1} rekurzivně spočetné a tedy z předpokladu efektivní neoddělitelnosti A, B dostáváme, že lze efektivně nalézt bod k ∉ A_{1} ∪ B_{1}. Číslo k je kódem formule, která není dokazatelná v T a od které není v T dokazatelná ani její negace.

Částí 2b, která patří spíše do matematické logiky, se zde nezabýváme.

8 Numerace

Definice 24 (Numerace). Mějme spočetnou třídu funkcí F. Numerací rozumíme indexaci funkcí z F, tj. {φ_{i}}_{i}.

Definice 25 (Vlastnosti numerací).

• Numerace je vyčíslitelná, jestliže existuje ČRF α taková, že platí

α(i, x) ≃ φ_{i}(x).

• Numerace je přípustná, jestliže existuje ORF h taková, že

φ_{h(i,j)} = φ_{i} ∘ φ_{j}

• Numerace je hlavní, jestliže libovolná jiná numerace ČRF je na ni 1převedilná, tj. existuje prostá ORF g: κ_{i} = φ_{g(i)}.

Lemma 11. Lze ukázat, že je-li {φ_{i}}_{i} vyčíslitelná, pak je následující ekvivatelní:

1) je přípustná; 2) je hlavní;

3) platí pro ni s-m-n věta;

4) je rekurzivně isomorfní nějaké standardní numeraci ČRF vzniklé efektivním očíslováním programů.

Věta 38. Necht’ F je třída ČRF. Potom

1) ∃f ∈ F ∃g ⊇ f g ∉ F

2) F ≠ ∅ a neobsahuje žádnou ORF

3) f ∈ F, ale pro každé p f ↾ p ∉ F

Každá z těchto podmínek implikuje \overline{K} ≤_{1} G(F) = \{x : φ_{x} ∈ F\}. Speciálně to znamená, že G(F) není rekursivně spočetná.

Důkaz.

1) Máme f ∈ F, máme g ČRF, g ⊇ f, g ∉ F. Chceme nalézt ORF h takovou, že

z ∉ K ⇒ φ_{h(z)} = f  (84)
z ∈ K ⇒ φ_{h(z)} = g  (85)

Pomocí s-m-n věty:

φ_{h(z)}(x) ≃ y ⇔ (f(x) ≃ y) ∨ (z ∈ K & g(x) ≃ y)  (86)

Funkce h převádí \overline{K} na G(F). Poznámka: φ_{h(z)} je definovaná tak, že pro z ∉ K musí platit f(x) ≃ y, pro z ∈ K bude rozšířena o body g(x). Jedná se o korektní definici, protože z předpokladů je g rozšířením f, tedy nemůže dojít ke kolizi.

2) Mějme nějakou f z F, která z předpokladu není ORF (pouze ČRF). Definujeme rekurzivně spočetnou relaci

P (z, x, y) ⇔ (f(x) ≃ y) ∨ (z ∈ K & y = 0)  (87)

Vezmeme selektor, tedy prostou ORF h.

z ∉ K ⇒ φ_{h(z)} = f  (88)
z ∈ K ⇒ φ_{h(z)}totální  (89)

Opět platí, že h převádí \overline{K} na G(F). Poznámka: zde vystupuje v roli g z předchozího bodu nulová funkce. Ta ale není rozšířením funkce f, tedy musíme postupovat opatrněji, nelze přímo definovat funkci h(x) jako v předchozím bodě. Místo toho použijeme graf relace (může obsahovat kolize, tedy dvě různá y pro jedno x (a to při z ∈ K)), na grafu vezmeme selektor, který existuje podle věty 9. V případě, že z ∈ K, bude tento selektor totální (protože nulová funkce je totální, ale nebude obecně roven nulové funkci). Totální funkce určitě padne mimo F, protože F neobsahuje žádnou ORF. V případě z ∉ K bude selektor roven funkci f, tedy padne do F.

3) Mějme f ∈ F, s-m-n věta (prostá) ORF h.

φ_{h(z)}(x) ≃ y ⇔ f(x) ≃ y & z ∉ K_{x}  (90)

Poznámka: v případě, že z ∉ K, je φ_{h(z)} = f a tedy padne do F. V případě, že z ∈ K, je φ_{h(z)} = f↾p pro nějaké p a tedy φ_{h(z)} nepadne do F. Tedy h(z) převádí \overline{K} na G(F).

Důsledek 9. Tedy pokud platí, že G(F) je rekurzivně spočetná, potom musí F s každou f obsahovat i všechna její rozšíření (plyne z podmínky 1) a pro každou f musí obsahovat nějaký její počáteční úsek (podmínka 3).

9 Relativní vyčíslitelnost

Definice 26 (B-ČRF). φ je B-ČRF, jestliže existuje B-odvození. A je Brekurzivní, jestliže c_{A} je B-ORF. A je B-rekurzivně spočetná, jestliže A je definiční obor α, kde α je nějaká B-ČRF.

Definice 27 (String). String (řetízek) je konečná posloupnost nul a jedniček. Označení

σ ∗ τ  konkatenace  (91)
σ ⊆ τ  σ je prefixem τ  (92)
σ ⊆ B  σ je prefixem c_{B}  (93)

Definice 28 (Funkcionální vlastnost). Rekurzivně spočetná množina Φ má funkcionální vlastnost, jestliže

⟨σ, x, y⟩ ∈ Φ ∧ ⟨\overline{σ}, x, \overline{y}⟩ ∈ Φ ∧ σ ⊆ \overline{σ} ⇒ y = \overline{y}  (94)

Definice 29 (Částečně rekurzivní funkcionál). Částečně rekurzivní funkcionál Φ je rekurzivně spočetná množina s funkcionální vlastností. Částečně rekurzivní funkcionál určuje zobrazení (parciální):

Φ(σ)(x) ≃ y ⇔ ⟨σ, x, y⟩ ∈ Φ  (95)
Φ(τ)(x) ≃ y ⇔ pro nějaké σ ⊆ τ Φ(σ)(x) ≃ y  (96)
Φ(B)(x) ≃ y ⇔ pro nějaké σ ⊆ B Φ(σ)(x) ≃ y  (97)

Lemma 12 (Regularizační funkce). Existuje PRF ϱ taková, že pro libovolné z platí, že W_{ϱ(z)} má funkcionální vlastnost a navíc platí, že je-li W_{z} již regulární, potom W_{z} = W_{ϱ(z)}.

Důkaz. Idea. Efektivně generujeme W_{z} a každý prvek kontrolujeme, zda není v kolizi s nějakým již přidaným do W_{ϱ(z)}.

Definice 30 (Numerace částečně rekurzivních funkcionálů). Φ_{i}(B)(x) ≃ y ⇔ ∃σ (⟨σ, x, y⟩ ∈ W_{ϱ(i)} ∧ σ ⊆ B)

Definice 31 (B-rekurzivita). A je B-rekurzivní (značíme A ≤_{T} B), jestliže pro nějaké i platí A = Φ_{i}(B), tj. ∀x c_{A}(x) = Φ_{i}(B)(x)

A je B-rekursivně spočetná, jestliže A = dom(Φ_{i}(B)).

Definice 32 (Značení).

Φ_{i,s}(σ)(x) je výsledek za s kroků.

Φ_{i,s}(σ)(x) ↓ ⇔ ∃τ, y (⟨τ, x, y⟩ ∈ W_{ϱ(i),s} ∧ length(τ) ≤ s ∧ τ ⊆ σ)

Φ_{i,s}(σ)(x) ≃ y ⇔ ∃τ (⟨τ, x, y⟩ ∈ W_{ϱ(i),s} ∧ length(τ) ≤ s ∧ τ ⊆ σ)

Definice 33 (Numerace B-r.s.).

W_{z}^{B} = dom(Φ_{z}(B))

W_{z,s}^{B} = dom(Φ_{z,s}(B))

Věta 39. Φ_{z}(B)(x_{1}, …, x_{n}) je univerzální funkce pro třídu všech B-ČRF k proměnných a platí s-m-n věta. To znamená, že existují PRF \overline{s_{m}} takové, že pro libovolnou B platí:

Φ_{\overline{s_{m}}(z,x_{1},...,x_{m})}(B)(y_{1}, …, y_{n}) ≃ Φ_{z}(B)(x_{1}, …, x_{m}, y_{1}, …, y_{n}).  (98)

Důkaz. Důkaz pro jednoduchost jenom pro m = n = 1. Vypočítáme pomocnou rekurzivně spočetnou množinu

W = {⟨σ, y, t⟩ : ⟨σ, ⟨x, y⟩ , t⟩ ∈ W_{ϱ(z)}}  (99)

Tedy máme ČRF α

α(z, x, w)↓ ⇔ w = ⟨σ, y, t⟩ ∧ ⟨σ, ⟨x, y⟩ , t⟩ ∈ W_{ϱ(z)}  (100)

Zbývá ukázat:

Φ_{\overline{s}_{1}(z,x)}(B)(y) ≃ Φ_{z}(B)(x, y)  (101)

Necht’

α(z, x, w) ≃ φ_{s_{2}(a,z,x)}(w)  (102)

Protože W_{ϱ(z)} je regulární, je regulární i W_{s_{2}(a,z,w)}.

\overline{s}_{1}(z, x) = s_{2}(a, z, x)  (103)
W_{ϱ(s_{2}(a,z,x))} = W_{s_{2}(a,z,x)}  (104)

Jelikož s-m-n věta platí absolutně (stejnoměrně), dostáváme okamžitě platnost věty o rekurzi.

Věta 40 (O rekurzi II). Necht’ f je ČRF dvou proměnných, potom existuje PRF p taková, že ∀B∀x Φ_{f(p(y),y)}(B)(x) ≃ Φ_{p(y)}(B, x).

10 Operace skoku

Definice 34 (Relativizovaný halting problem).

A′ = {x : Φ_{x}(A)(x) ↓} = {x : x ∈ W_{x}^{A}}  (105)

Dále induktivně definujeme

A^{0} = A  (106)
A^{n+1} = (A^{n})′  (107)

Věta 41. 1) A′ je A-rekursivně spočetná 2) A′ ≰_{T} A (A′ není A-rekurzivní)

3) B je A-rekursivně spočetná ⇔ B ≤_{1} A′

4) A je B-rekrusivně spočetná a B ≤_{T} C ⇒ A je C-rekurzivně spočetná

5) A ≤_{T} B ⇔ A′ ≤_{1} B′

6) A ≡_{T} B ⇔ A′ ≡_{1} B′

Důkaz. 1) z definice A′ = {x : Φ_{x}(A)(x) ↓}

2) Cantorova diagonální metoda

3) ⇐ zřejmé

⇒ stejně jako u K

Φ_{a}(A)(x, w) ↓⇔ x ∈ B …  (použití fiktivní proměnné) (108)

4) A je definičním oborem nějaké B-ČRF f, B je rekurzivní v C (via g), tedy s pomocí f a g dostáváme, že A je definičním oborem nějaké C-ČRF.

A = dom(Φ_{z}(B)), B ≤_{T} C ⇒ A = dom(Φněco(C))  (109)

5) Necht’ A ≤_{T} B. Potom z faktu, že A′ je A-rekurzivně spočetná, a A ≤_{T} B dostáváme, že A′ je B-rekurzivně spočetná (podle bodu 4 této věty). A protože B′ je úplná pro B-rekurzivně spočetné, dostáváme okamžitě A′ ≤_{1} B′.

Opačný směr. Mějmě A′ ≤_{1} B′. Zřejmě platí, že A i \overline{A} jsou A-rekurzivní, tím spíše jsou A-rekurzivně spočetné. Tedy jsou obě 1-převedilné na A′. Ale dle předpokladu A′ ≤_{1} B′ a tedy A ≤_{1} B′ i \overline{A} ≤_{1} B′ a tedy dle relativizované Postovy věty je A B-rekurzivní.

6) Plyne okamžitě z bodu 5.

Důsledek 10. Operace skoku je korektně definována na T-stupních. Tedy platí

A ≡_{T} B ⇒ A′ ≡_{1} B′ (⇒ A′ ≡_{T} B′)  (110)

Lze tedy definovat skok stupně a jako stupeň obsahující skok libovolného prvku stupně a.

Věta 42 (Stejnoměrnost). Existuje z_{0} takové, že A′ = W_{z_{0}}^{A} pro všechna A.

Důkaz.

W_{z_{0}} = {⟨σ, x, y⟩ : ⟨σ, x, y⟩ ∈ W_{ϱ(x)}}  (111)

Protože W_{ϱ(x)} je regulární, je i W_{z_{0}} je regulární a tedy W_{z_{0}} = W_{ϱ(z_{0})}.

x ∈ A′ ⇔ Φ_{x}(A)(x)↓ ⇔ ∃σ ⊆A (Φ_{x}(σ)(x)↓) ⇔
⇔ ∃σ ⊆A∃y (Φ_{x}(σ)(x) ≃ y) ⇔
⇔ ∃σ ⊆A∃y (⟨σ, x, y⟩ ∈ W_{ϱ(x)}) ⇔
⇔ x ∈ W_{z_{0}}^{A}

Tato složitě vypadající konstrukce je přirozeným zobecněním definice množiny K = {x : x ∈ W_{x}}. Akorát nyní konstruujeme množinu trojic obsahujících aproximaci orákula σ, proměnné x a y. Navíc musíme aplikovat regularizační funkci ϱ. Jinak zapsáno

W_{z_{0}} = {w : w ∈ W_{ϱ((w)_{3,2})}}.  (112)

Lemma 13. ∅′ ≡ K

Důkaz. 1) K je rekurzivně spočetná a tedy K ≤_{1} ∅′

2) ∅′ = {x : x ∈ W_{x}^{∅}} ⇒ ∅′ je rekurzivně spočetná v ∅, ale ∅ je rekurzivní a tedy ∅′ je absolutně rekurzivně spočetná a tedy je ≤_{1} K, protože K je 1-úplná.

11 Limitní vyčíslitelnost

Definice 35 (Limitní vyčíslitelnost). Množina M je limitně vyčíslitelná, jestliže existuje ORF h taková, že M(x) ≃ lim_{s} h(x, s).

Funkce f je limitně vyčíslitelná, jestliže existuje ORF h taková, že f(x) ≃ lim_{s} h(x, s).

Věta 43. M je rekurzivní v ∅′ právě, když M je limitně vyčíslitelná.

Důkaz.

”⇒” M ≤_{T} ∅′ ⇒ ∃z M(x) = Φ_{z}(∅′)(x). Tedy existuje program z, který z ∅′ počítá M. K tomu používá nerekurzivní orákulum, které ale můžeme efektivně generovat. Definujeme

h(x, s) = \{ \begin{matrix}Φ_{z,s}(∅′_{s})(x) & jestliže Φ_{z,s}(∅′_{s})(x)↓ \\ 0 & jinak \end{matrix}  (113)

Ukážeme, že M(x) = lim_{s} h(x, s). Je-li pro dané x M(x) definováno, znamená to, že Φ_{z}(∅′)(x)↓ a tedy existuje počáteční úsek σ ⊆ ∅′, pro který platí Φ_{z}(σ)(x)↓.

Z σ ⊆ ∅′ plyne, že existuje t_{0} takové, že ∀t > t_{0} ∅′_{t_{0}}↾ lh(σ) = ∅′_{t}↾ lh(σ), tedy od určitého kroku t_{0} počáteční úsek aproximace ∅′ o délce řetízku σ již pravdivě aproximuje ∅′.

Dále existuje t_{1} takové, že Φ_{z,t_{1}}(σ)(x)↓, tedy vlastní výpočet se σ jako aproximací orákula konverguje za t_{1} kroků.

Položme s_{0} = max(t_{0}, t_{1}). Od kroku s_{0} už nemůže dojít ke změně, nebot’ aproximace (v tuto chvíli již pravdivá) se již nemění a výpočet již zakonvergoval.

”⇐” Necht’ M(x) je limitně vyčíslitelná. Chceme s pomocí ∅′ vyčíslovat M. While cyklem najdeme nejmenší s_{0} takové, že ∀s ≥ s_{0} h(x, s) = h(x, s_{0}). Jedná se o otázku rekurzivní v ∅′. Tedy máme μ_{s_{0}}(∅′-rekurzivní otázka). To je ∅′- ČRF, navíc M(x) je totální, tedy tato minimalizace je ∅′-ORF. Z toho plyne, že M ≤_{T} ∅′.

V předchozí větě bylo podstatné, že M je totální. Nyní tvrzení pro parciální funkce.

Věta 44.

1) Jestliže f je ORF, potom lim_{s} f(x, s) je ∅′-ČRF.

2) Jestliže F je ∅′-ČRF, pak existuje ORF f taková, že F (x) ≃ lim_{s}f(x, s).

Přesněji: Φ_{z}(∅′)(x) ≃ lim_{s} h(z, x, s) pro nějakou ORF h.

Důkaz. 1) Provedeme stejnou minimalizaci s jako v důkazu předchozí věty. Tentokrát ale nemusí minimalizace konvergovat.

2) V tomto případě použijeme stejnou ideu, ale musíme dát pozor, aby F (x)↓. Naším cílem bude stabilizace celého výpočtu. Definujeme

h_{0}(z, x, s) = \{ \begin{matrix}⟨σ, x, y⟩ & jestliže ⟨σ, x, y⟩ ∈ W_{ϱ(z),s} & σ ⊆ ∅′_{s} \\ s + 1 & jinak \end{matrix} (114)

Nelze pouze vydělit y a stabilizovat y (výsledek výpočtu), je třeba stabilizovat celý výpočet, protože se může stát, že se mění aproximace orákula.

h(z, x, s) = \{ \begin{matrix}(h_{0}(x, z, s))_{3,3} & jestliže h_{0}(z, x, s) = h_{0}(z, x, s + 1) \\ s & jinak \end{matrix} (115)

lim_{s} h(z, x, s) existuje právě, když existuje lim_{s} h_{0}(z, x, s).

F (x)↓ ⇒ Φ_{z}(σ)(x)↓ pro nějaké σ ⊆ ∅′.

Tedy lim_{s} h(z, x, s) = F (x).

Jestliže existuje lim_{s} h(z, x, s), potom existuje lim_{s} h_{0}(z, x, s) a tedy máme nějaké ⟨σ, x, y⟩ a s_{0} takové, že ∀s ≥ s_{0} je ⟨σ, x, y⟩ stabilní. Z toho plyne Φ_{z,s}(σ)(x) ≃ y & σ ⊆ ∅′_{s}. Jinými slovy ⟨σ, x, y⟩ a s_{0} je limitní výpočet a Φ_{z}(∅′)(x)↓ & = y.

Ukažme si případ, který demonstruje, proč je potřeba trvat na stabilizaci celého výpočtu a nejen výsledku. Snadno vytvoříme program z takový, že

Φ_{z}(A)(x)↓ ⇔ ∅′ \ A ≠ ∅ (a Φ_{z}(A)(x)↓ ⇒ výsledek = 0)  (116)

Program pracuje tak, že postupně generuje ∅′ a pro každý nový prvek w se ptá, zda w ∈ A. V okamžiku, kdy nějaký takový nalezne, zastaví se a vydá ∅.

Je zřejmé, že Φ_{z}(∅′)(…) ↑, zatímco ∀s Φ_{z}(∅′_{s})(…) ↓. Plyne to z toho, že žádná aproximace ∅′ nemůže zajistit, aby program nenalezl prvek, který do této aproximace nepatří. Tedy neexistuje limitní výpočet, ale prostou stabilizací výsledku (vždy ∅) bychom dostali, že limita existuje, což by bylo špatně.

Věta 45. Pro každé n existuje ORF h taková, že

Φ_{z}(∅^{n+1})(x) ≃ lim_{s_{0}} … lim_{s_{n}} h(z, x, s_{0}, …, s_{n}),  (117)

kde všechny limity s_{1}, …, s_{n} existují, limita pro s_{0} nemusí.

12 Aritmetická hierarchie

12.1 Definice a základní vlastnosti

Definice 36 (Σ_{n}, Π_{n} prefix). Σ_{n} (resp. Π_{n}) prefix je skupina kvantifikátorů, která má n skupin stejných kvantifikátorů, sousední skupiny se střídají a začíná ∃ (resp. ∀).

Definice 37. Predikát patří do třídy Σ_{n} (resp. Π_{n}), jestliže lze vyjádřit ve tvaru Σ_{n} prefix na rekurzivní základ (resp. Π_{n} prefix).

Lemma 14. Σ_{0} = Π_{0} jsou právě rekurzivní predikáty.

Důkaz. Zřejmé.

Definice 38. Prefikát je aritmetický, jestliže jej lze vyjádřit pomocí spojek predikátového počtu nad rekurzivními relacemi.

Lemma 15. Aritmetické predikáty jsou právě všechny predikáty ve třídách Σ_{n}, Π_{n}, n ∈ ℕ.

Důkaz. ⇐ Zřejmé.

⇒ Úprava logického výrazu do prenexního tvaru.

Lemma 16 (Základní vlastnosti).

1) A ∈ Σ_{n} ⇔ \overline{A} ∈ Π_{n}

2) Σ_{n} ∪ Π_{n} ⊆ Σ_{m} ∩ Π_{m} pro m > n.

3) A ≤_{m} B a B ∈ Σ_{n} (resp. Π_{n}), potom A je Σ_{n} (resp. Π_{n}).

Důkaz.

1) Zřejmé.

2) Kvantifikací přes fiktivní proměnnou přidáme potřebný kvantifikátor bud’ na konec nebo na začátek.

3) Transformace převodní funkcí nezmění aritmetickou složitost.

Věta 46 (O numeraci, univerzálním predikátu). Pro každou třídu Σ_{n} (resp. Π_{n}) pro n ≥ 1 existuje univerzální Σ_{n} (resp. Π_{n}) predikát.

Důkaz. Nejprve případ Σ_{n}, kde n je liché. Máme predikát tvaru ∃∀ … ∃(rek). Kvantifikátory kromě posledního odřízneme. Dostáváme Σ_{1} predikát, tj. rekurzivně spočetný predikát. Pro něj existuje univerzální predikát ∃T_{n}(e, x, …). Nyní vrátíme kvantifikátory ∃∀ … ∃T_{n}(e, x, …).

Případ pro Σ_{n} a n sudé. Po odříznutí dostáváme ∀(rek), negací ∃T_{n}, opětovnou negací ∀¬T_{n}.

Pro případ Π_{n} analogicky (obráceně).

Důsledek 11. Pro n ≥ 1 platí Σ_{n} \ Π_{n} ≠ ∅.

Důkaz. Máme univerzální Σ_{n} predikát U(e, x) ∈ Σ_{n}. Kdyby U(e, e) ∈ Π_{n}, potom by ¬U(e, e) ∈ Σ_{n}, vezmeme jeho index a a dosadíme e = a. Dostáváme spor (U(a, a) ⇔ ¬U(a, a)), U(e, e) tedy musí být mimo Π_{n}.

Věta 47 (O hierarchii).

1) A je rekurzivně spočetná v ∅^{(n)} ⇔ A ∈ Σ_{n+1}

2) ∅^{n+1} je Σ_{n+1}-úplná

3) B ≤_{T} ∅^{(n)} ⇔ B ∈ Σ_{n+1} ∩ Π_{n+1}

Důkaz.

1) Pro n = 0 to víme. Indukcí pro všechna n. Necht’ A ∈ Σ_{n+1}, tedy A je tvaru ∃(Π_{n}). Negace toho Π_{n} je Σ_{n} a dle indukčního předpokladu je tedy rekurzivně spočetná v ∅^{(n−1)}. Z toho plyne ≤_{1} ∅^{(n)} ⇒≤_{T} ∅^{(n)} ⇒ původní predikát (před negací) je ≤_{T} ∅^{(n)}. Dostáváme ∃(rekurzivní v ∅^{(n)}), což je rekurzivně spočetné v ∅^{(n)}.

Nyní necht’ A je rekurzivně spočetná v ∅^{(n)}, tedy A je definiční obor nějaké g, která je ∅^{(n)}-ČRF. Dle věty o limitní vyčíslitelnosti je g ≃ lim_{s} f(x, s), kde f je ∅^{(n−1)}-ORF.

x ∈ A ⇔ g(x)↓ ⇔ ∃s_{0}∀s≥s_{0} (f(x, s) = f(x, s_{0}))

Výraz v závorkách je rekurzivní v ∅^{(n−1)} a tedy podle bodu 3 této věty patří do Σ_{n} ∩ Π_{n}. Dostáváme tedy ∃∀Π_{n}, což je ∃Π_{n}, tedy Σ_{n+1}.

2) Plyne z bodu 1.

3) Plyne z bodu 1 pomocí Postovy věty.

Poznámka: v důkazu bodu 1 se odvoláváme na bod 3, který naopak dokazujeme z bodu 1. Nejde ale o nekorektní důkaz, protože v bodě 1 použijeme platnost bodu 3 pro n−1 a důkaz stavíme induktivně, tedy platnost pro m < n už máme zaručenu.

Věta 48 (O úplnosti). Pro n ≥ 1 je ∅^{(n)} Σ_{n}-úplná

Důkaz. Necht’ M je Σ_{n}, potom M je ∅^{(n−1)}-rekurzivně spočetná a dle vlastnosti operace skoku je ≤_{1} ∅^{(n)}.

12.2 Σ_{2} a Π_{2} úplné množiny

Věta 49 (Tot je Π_{2}-úplná). Tot= {x : φ_{x} je totální} je Π_{2}-úplná.

Důkaz. Tot je zřejmě Π_{2}. Mějmě B ∈ Π_{2}, tedy

x ∈ B ⇔ ∀y∃s Q(x, y, s).  (118)

Chceme nalézt ORF f takovou, že

x ∈ B ⇔ f(x) ∈ T ot ⇔ φ_{f(x)} je totální  (119)

Zkonstruujeme funkci, která bude pro y vracet s (Σ_{1} svědka).

α(x, y) ≃ μ_{s}Q(x, y, s) ≃ Ψ_{2}(a, x, y) ≃ Ψ_{1}(s_{1}(a, x), y) ≃ φ_{f(x)}(y)  (120)

Je zřejmé, že x ∈ B ⇔ f(x) ∈ Tot.

Σ_{2}-úplné množiny: ∅^{(2)}, Fin Π_{2}-úplné množiny: \overline{∅^{(2)}}, Tot, Inf

Věta 50 (Relativizace). A je Σ_{n+1}^{B} ⇔ A je rekurzivně spočetná v B^{(n)}

A ≤_{T} B^{(n)} ⇔ A ∈ Σ_{n+1}^{B} ∩ Π_{n+1}^{B} Lemma 17. Fin = {x|W_{x} je končená} je Σ_{2} úplná. Důkaz. Množina je konečná, jestliže má horní závoru, tedy prvek, pro který platí, že všechny větší jsou mimo tuto množinu.

x ∈ F in ⇔ ∃y ∀y′>y ∀s ¬(y′ ∈ W_{x,s})  (121)

Mějme libovolnou A ∈ Σ_{2}. Platí

x ∈ A ⇔ ∃z ∀y Q(x, z, y).  (122)

Definujeme

α(x, z)↓⇔ ∀j ≤z ∃y (¬Q(x, z, y)).  (123)

Podle s-m-n věty:

α(x, z) ≃ φ_{f(x)}(z)  (124)
x ∈ A ⇒ ∃z ∀z′ >z φ_{f(x)}(z′)↑  (125)

a tedy W_{f(x)} je konečný počáteční úsek.

x ∉ A ⇒ ∀zφ_{f(x)}(z)↓ ⇒ W_{f(x)} = ℕ  (126)