{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke <Státnice> z <Státnice_-Informatika-Vyčíslitelnost> pro obory <Státnice-Informatika-_I3:Matematická_lingvistika> a <Státnice-Informatika-_I2:_Softwarové_systémy>, pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze <Studnice%20vědomostí> -- User:Tuetschek 14:01, 17 Aug 2010 (CEST)

}}

Rekurzivně spočetné množiny

Definice (Rekurzivní a rekurzivně spočetná množina)

Charakteristická funkce množiny MM označuje charakteristickou funkci predikátu náležení do množiny, tj. funkci cM(x)c_M(x), kde cM(x)=↓1c_M(x) = \downarrow 1 pro x∈Mx\in M a cM(x)↓=0c_M(x) \downarrow = 0 pro x∉Mx\notin M.

Analogicky se definuje částečná charakteristická funkce množiny -- cM(x)=↓1c_M(x) = \downarrow 1 pro x∈M x \in M a cM(x)↑c_M(x)\uparrow pro x∉Mx \notin M.

Množina M  ⁣ M\,\! je rekurzivní, je-li její charakteristická funkce obecně rekurzivní (každá char. fce je totální, takže ČRF by bylo totéž). Množina M  ⁣ M\,\! je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF (neboli jestliže je její částečná char. funkce částečně rekurzivní).

Množina je rekurzivní, jestliže existuje program, který se na libovolném vstupu zastaví a rozhodne, zda do ní vstup patří. Množina je rekurzivně spočetná, jestliže existuje program, který se zastaví právě na jejích prvcích. Je-li množina rekurzivní, je i rekurzivně spočetná, opačně to neplatí.

Definice (dom,rng  ⁣ dom, rng\,\!)

V následujícím dom  ⁣ dom\,\! značí definiční obor, rng  ⁣ rng\,\! obor hodnot.

Definice (x  ⁣ x\,\!-tá rekurzivně spočetná množina)

Wx  ⁣ W_x\,\! (x  ⁣ x\,\!-tá rekurzivně spočetná množina) =dom(φx)={y:φx(y) ⁣ ⁣↓}  ⁣ = dom(\varphi_x) = \{y:\varphi_x(y)\!\!\downarrow\}\,\!

Definice (K)

K={x:x∈Wx}={x:φx(x) ⁣ ⁣↓}={x:Ψ1(x,x) ⁣ ⁣↓}  ⁣ K = \{x:x\in W_x\} = \{x:\varphi_x(x)\!\!\downarrow\} = \{x:\Psi_1(x,x)\!\!\downarrow\}\,\!

Množina K  ⁣ K\,\! vlastně odpovídá <Státnice%20-%20Algoritmicky%20nerozhodnutelné%20problémy>. Platí o ní následující tvrzení.

Věta (Rekurzivní spočetnost K  ⁣ K\,\!)

Množina K  ⁣ K\,\! je rekurzivně spočetná, není rekurzivní, K‾  ⁣ \overline K\,\! není rekurzivně spočetná.

Důkaz

K  ⁣ K\,\! není rekurzivní, neboť K‾  ⁣ \overline K\,\! není rekurzivně spočetná. K‾  ⁣ \overline K\,\! není rekurzivně spočetná, neboť kdyby byla, měla by index x0  ⁣ x_0\,\!. Jednoduchou diagonalizací dostáváme x0∈K‾⇔x0∈Wx0⇔x0∈K  ⁣ x_0 \in \overline{K} \Leftrightarrow x_0 \in W_{x_0} \Leftrightarrow x_0 \in K\,\!. Spor.

1-převeditelnost, m-převeditelnost

Definice (1  ⁣ 1\,\!-převeditelnost, m  ⁣ m\,\!-převeditelnost, 1  ⁣ 1\,\!-úplnost, m  ⁣ m\,\!-úplnost)

  • Množina A  ⁣ A\,\! je 1-převedilná na B  ⁣ B\,\! (značíme A≤1B  ⁣ A\leq_1 B\,\!), jestliže existuje prostá ORF f  ⁣ f\,\! taková, že x∈A⇔f(x)∈B  ⁣ x \in A \Leftrightarrow f(x) \in B\,\!.

  • Množina A  ⁣ A\,\! je m  ⁣ m\,\!-převedilná na B  ⁣ B\,\! (značíme A≤mB  ⁣ A\leq_m B\,\!), jestliže existuje ORF f  ⁣ f\,\! (ne nutně prostá) taková, že x∈A⇔f(x)∈B  ⁣ x \in A \Leftrightarrow f(x) \in B\,\!.

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

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

Věta (1-úplnost K  ⁣ K\,\!)

K  ⁣ K\,\! je 1-úplná. Tedy halting problem je vzhledem k 1  ⁣ 1\,\! a m  ⁣ m\,\!-převoditelnosti nejtěžší mezi rekurzivně spočetnými problémy.

Důkaz

Mějme libovolnou rekurzivně spočetnou množinu Wx  ⁣ W_x\,\!.

Mějme ČRF α(y,x,w)  ⁣ \alpha(y,x,w)\,\!, popisující x  ⁣ x\,\!-tou rekurzivně spočetnou množinu. Tedy α(y,x,w) ⁣ ⁣↓⇔y∈Wx⇔Ψ1(x,y) ⁣ ⁣↓⇔φx(y) ⁣ ⁣↓. \alpha(y,x,w)\!\!\downarrow \Leftrightarrow y \in W_x \Leftrightarrow \Psi_1(x,y)\!\!\downarrow \Leftrightarrow \varphi_x(y)\!\!\downarrow. ww je tady fiktivní proměnná, funkce α  ⁣ \alpha\,\! na její hodnotě nezáleží. Z s-m-n věty dostáváme: α(y,x,w)≃Ψ3(a,y,x,w)≃Ψ1(s2(a,y,x),w)≃φs2(a,y,x)(w). \alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w). Označme h(y,x)=s2(a,y,x)  ⁣ h(y,x)=s_2(a,y,x)\,\! (s2  ⁣ s_2\,\! je PRF, tím spíše ORF). y∈Wx⇔α(y,x,w) ⁣ ⁣↓⇔φh(y,x)(w) ⁣ ⁣↓⇔φh(y,x)(h(y,x)) ⁣ ⁣↓⇔h(y,x)∈K y \in W_x \Leftrightarrow \alpha(y,x,w)\!\!\downarrow \Leftrightarrow \varphi_{h(y,x)}(w)\!\!\downarrow \Leftrightarrow \varphi_{h(y,x)}(h(y,x))\!\!\downarrow \Leftrightarrow h(y,x) \in K Zde jsme mohli za w  ⁣ w\,\! dosadit h(y,x)  ⁣ h(y,x)\,\!, neboť hodnota α  ⁣ \alpha\,\! na w  ⁣ w\,\! nezáleží! Tedy Wx≤1 ⁣K  ⁣ W_x \leq_1\!K\,\! pomocí funkce λy:h(y,x)  ⁣ \lambda y:h(y,x)\,\!.

Lemma (K0  ⁣ K_0\,\! je 1-úplná)

K0={⟨y,x⟩:y∈Wx}  ⁣ K_0 = \{\langle y,x\rangle: y \in W_x\}\,\! je 1-úplná.

Důkaz

Zřejmé. K≤1K0  ⁣ K \leq_1 K_0\,\! a K  ⁣ K\,\! je 1  ⁣ 1\,\!-úplná.

Lemma (Poznámky k 1-převeditelnosti)

  1. Relace ≤1  ⁣ \leq_1\,\! a ≤m  ⁣ \leq_m\,\! jsou tranzitivní, reflexivní.

  2. A≤1B⇒A≤mB  ⁣ A \leq_1 B \Rightarrow A \leq_m B\,\!

  3. B  ⁣ B\,\! rekurzivní, A≤mB⇒A  ⁣ A \leq_m B \Rightarrow A\,\! rekurzivní.

  4. B  ⁣ B\,\! rekurzivně spočetná, A≤mB⇒A  ⁣ A \leq_m B \Rightarrow A\,\! rekurzivně spočetná.

Důkaz

  1. Zřejmé.

  2. Zřejmé.

  3. Složením funkce dokazující ≤m  ⁣ \leq_m\,\! s procedurou, která rozhoduje o x∈B  ⁣ x \in B\,\!, dostaneme proceduru rozhodující o x∈A  ⁣x\in A\,\!. Dostáváme cA(x)=cB(f(x))  ⁣ c_A(x)=c_B(f(x))\,\!.

  4. Stejně.

Důsledek

K  ⁣ K\,\! a K‾  ⁣ \overline K\,\! jsou m  ⁣ m\,\!-nesrovnatelné.

Důkaz

Plyne z faktu, že K  ⁣ K\,\! je rekurzivně spočetná, K‾  ⁣ \overline K\,\! není, a z bodu 4 předchozího lemma.

Definice (Rekurzivní permutace)

Permutace na N  ⁣ \mathbb{N}\,\!, která je ORF, se nazývá rekurzivní permutace.

Definice (Rekurzivní isomorfismus)

Množiny A  ⁣ A\,\! a B  ⁣ B\,\! jsou rekurzivně isomorfní, jestliže existuje rekurzivní permutace p  ⁣ p\,\! taková, že p(A)=B  ⁣ p(A)=B\,\!. Značíme A≡B  ⁣ A \equiv B\,\!.

Definice (1-ekvivalence a m-ekvivalence)

  • A≡1B  ⁣ A \equiv_1 B\,\!, jestliže A≤1B∧B≤1A  ⁣ A \leq_1 B \wedge B\leq_1 A\,\!.

  • A≡mB  ⁣ A \equiv_m B\,\!, jestliže A≤mB∧B≤mA  ⁣ A \leq_m B \wedge B\leq_m A\,\!.

Věta (Myhillova)

A≡B⇔A≡1B  ⁣ A \equiv B \Leftrightarrow A \equiv_1 B\,\!

Důkaz

Jedná se o vlastně o obdobu wen:Cantor–Bernstein–Schroeder%20theorem.

⇒  ⁣ \Rightarrow\,\! Triviální.

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

Plán: v krocích budeme generovat graf h  ⁣ h\,\! tak, že v kroku n  ⁣ n\,\! bude platit {0,…,n}⊆dom(h),{0,…,n}⊆rng(h).\{0,\ldots,n\} \subseteq dom(h), \{0,\ldots,n\} \subseteq rng(h).

Z toho plyne, že h  ⁣ h\,\! bude definovaná na celém N  ⁣ \mathbb{N}\,\! a bude na. Současně zajistíme, že h  ⁣ h\,\! bude prostá.

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

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

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

  2. f(0)≠0  ⁣ f(0)\neq 0\,\!: rozlišíme dva podpřípady

    1. g(0)≠0  ⁣ g(0)\neq 0\,\!: definujeme h(g(0))=0  ⁣ h(g(0))=0\,\!. Tedy 0∈dom(h)∩rng(h)  ⁣ 0 \in dom(h) \cap rng(h)\,\!.

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

Indukční krok: nechť v kroku k  ⁣ k\,\! je z  ⁣ z\,\! první volný prvek. Všechna čísla menší než z  ⁣ z\,\! máme v dom(h)∩rng(h)  ⁣ dom(h)\cap rng(h)\,\!. Podíváme se, zda je f(z)  ⁣ f(z)\,\! volný. Jestliže ano, položíme h(z)=f(z)  ⁣ h(z)=f(z)\,\!. Jestliže f(z)  ⁣ f(z)\,\! není volný, hledám "cik-cak" další volný (podobně jako pro 00, maximálně z  ⁣ z\,\! prvků je blokovaných, tj. maximálně po zz iteracích tohoto postupu dojdu k volnému prvku).

Důsledek

K≡K0  ⁣ K \equiv K_0\,\!.

Důkaz

Zřejmé, neboť K≡1K0  ⁣ K \equiv_1 K_0\,\! (obě množiny jsou 1-úplné).

Rekurzivně spočetné predikáty

Lemma (ORF →  ⁣ \to\,\! RSP)

Je-li Q  ⁣ Q\,\! obecně rekurzivní predikát, potom ∃y:Q  ⁣ \exists y: Q\,\! je rekurzivně spočetný predikát.

Důkaz

μyQ  ⁣ \mu_y Q\,\! je ČRF, její definiční obor je {∃y:Q}  ⁣\{ \exists y:Q \}\,\!.

Věta (Univerzální RSP)

Predikát ∃yTk(e,x1,…,xk,y)  ⁣ \exists y T_k(e,x_1,\ldots,x_k,y)\,\! je univerzálním RSP pro třídu RSP k  ⁣ k\,\! proměnných, tj. lze definovat index (Gödelovo číslo) rekurzivně spočetného predikátu.

Důkaz

Z věty o normální formě -- numerace ČRF nám dává numeraci predikátů.

Věta (Log. spojky a rek. spočetnost)

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 ((w)2,1  ⁣ (w)_{2,1}\,\! znamená to, že w  ⁣ w\,\! kóduje usp. dvojici a vybíráme z ní první prvek; to je PRF): ∃s1Tk(a,x⃗,w1)∧∃s2Tk(b,x⃗,w2)⇔∃w(Tk(a,x⃗,(w)2,1)∧Tk(b,x⃗,(w)2,2)) \exists s_1 T_k(a,\vec{x},w_1) \wedge \exists s_2 T_k(b,\vec{x},w_2) \Leftrightarrow \exists w (T_k(a,\vec{x},(w)_{2,1}) \wedge T_k(b,\vec{x},(w)_{2,2})) . Uvedený predikát je rekurzivně spočetný, tedy má nějaký index, tj. ekvivalence pokračuje: ∃wTk+2(e,a,b,x⃗,w)⇔∃wTk(s2(e,a,b),x⃗,w)\exists w T_{k+2}(e,a,b,\vec{x},w) \Leftrightarrow \exists w T_k(s_2(e,a,b),\vec{x},w)

Poznámka

Konjunkce a disjunkce tedy rek. spočetnost zachovávají, o negaci (tj. doplňku) to ale už samozřejmě neplatí.

Věta (Kvantifikace a rek. spočetnost)

Omezená kvantifikace (∀y)y≤t  ⁣ (\forall y)_{y \leq t}\,\! a existenční kvantifikace (pro k≥2  ⁣ k\geq 2\,\!) zachovávají rekurzivní spočetnost.

Důkaz

Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem.

Formálně: (∀y)y≤t ∃s:Tk(e,x1,…,xk−1,y,s)⇔∃ (\forall y)_{y \leq t}\ \exists s: T_k(e,x_1,\ldots,x_{k-1},y,s) \Leftrightarrow \exists kód (t ⁣+ ⁣1)(t\!+\!1)-tice w: (∀y)y≤t Tk(e,x1,…,xk−1,y,(w)t+1,y) w:\ (\forall y)_{y \leq t}\ T_k(e,x_1,\ldots,x_{k-1},y,(w)_{t+1,y}) .

yy můžeme zkoušet primitivní rekurzí, ww minimalizací, dostáváme tedy rekurzivně spočetný predikát, který má nějaký index b  ⁣ b\,\!, dále můžeme použít S-m-n větu. ∃s:Tk+1(b,e,x1,…,xk−1,t,s)⇔∃s:Tk(s1(b,e),x1,…,xk−1,t,s). \exists s: T_{k+1}(b,e,x_1,\ldots,x_{k-1},t,s) \Leftrightarrow \exists s: T_k(s_1(b,e),x_1,\ldots,x_{k-1},t,s).

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 (a použijeme opět S-m-n větu). Dostáváme predikát k ⁣− ⁣1  ⁣ k\!-\!1\,\! proměnných, proto je ve větě požadavek na minimální velikost k≥2  ⁣ k\geq 2\,\!.

:∃y:∃s:Tk(e,x1,…,xk−1,y,s)⇔∃w:Tk(e,x1,…,xk−1,(w)2,1,(w)2,2) \exists y: \exists s: T_k(e,x_1,\ldots,x_{k-1},y,s) \Leftrightarrow \exists w: T_k(e,x_1,\ldots,x_{k-1},(w)_{2,1},(w)_{2,2}) :⇔∃s:Tk(b,e,x1,…,xk−1,s)⇔∃s:Tk−1(s1(b,e),x1,…,xk−1,s) \Leftrightarrow \exists s: T_k(b,e,x_1,\ldots,x_{k-1},s) \Leftrightarrow \exists s: T_{k-1}(s_1(b,e),x_1,\ldots,x_{k-1},s)

Poznámka

Neomezená obecná kvantifikace (∀  ⁣ \forall\,\!) rekurzivní spočetnost nezachovává.

Věta (O selektoru)

Nechť Q  ⁣ Q\,\! je RSP k+1  ⁣ k+1\,\! proměnných. Potom existuje ČRF φ  ⁣ \varphi\,\! k  ⁣ k\,\! proměnných taková, že:

:φ(x1,…,xk) ⁣ ⁣↓⇔∃y:Q(x1,…,xk,y) \varphi(x_1,\ldots,x_k)\!\!\downarrow \Leftrightarrow \exists y: Q(x_1,\ldots,x_k,y) :φ(x1,…,xk) ⁣ ⁣↓⇒Q(x1,…,xk,φ(x1,…,xk))\varphi(x_1,\ldots,x_k)\!\!\downarrow \Rightarrow Q(x_1,\ldots,x_k,\varphi(x_1,\ldots,x_k))

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

Důkaz

Dáno x⃗  ⁣ \vec{x}\,\!, hledáme nejmenší dvojici (y,s)  ⁣ (y,s)\,\! takovou, že za s  ⁣ s\,\! kroků ověříme, že Q(x⃗,y)  ⁣ Q(\vec{x},y)\,\! (tj. program pro Q  ⁣ Q\,\! konverguje za s  ⁣ s\,\! kroků). Pak vydáme y  ⁣ y\,\!.

Obecně: univerzální vyjádření RSP ∃s:Tk+1(e,x⃗,y,s)  ⁣ \exists s: T_{k+1}(e,\vec{x},y,s)\,\!, hledáme nejmenší w  ⁣ w\,\! (kód dvojice) takové, že φ(x⃗)≃(μwTk+1(e,x⃗,(w)2,1,(w)2,2))2,1. \varphi(\vec{x}) \simeq (\mu_w T_{k+1}(e,\vec{x},(w)_{2,1},(w)_{2,2}))_{2,1}. Funkce φ  ⁣ \varphi\,\! vrací první složku z první dvojice, kterou najde (v uspořádání daném naším kódováním dvojic).

Věta (Vztah ČRF a RS grafů)

Funkce je ČRF ⇔  ⁣ \Leftrightarrow\,\! má rekurzivně spočetný graf.

Důkaz

Je-li φ  ⁣ \varphi\,\! ČRF, je její graf rekurzivně spočetný:

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 37: …k,y\rangle \in \̲m̲b̲o̲x̲{Graf} \Leftrig…

za s  ⁣ s\,\! kroků program konverguje.

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

Věta (Postova)

Množina M  ⁣ M\,\! je rekurzivní, právě když M  ⁣ M\,\! i M‾  ⁣ \overline M\,\! jsou rekurzivně spočetné.

Predikát Q  ⁣ Q\,\! je ORP, právě když Q  ⁣ Q\,\! i ¬Q  ⁣ \neg Q\,\! jsou RSP.

Důkaz

"⇒  ⁣ \Rightarrow\,\!": Triviální.

"⇐  ⁣ \Leftarrow\,\!": Intuitivně: M=dom(P1)  ⁣ M=dom(P_1)\,\!, M‾=dom(P2)  ⁣ \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∈M‾∧y=0)  ⁣ (x \in M \wedge y=1) \lor (x \in \overline M \wedge y=0)\,\! je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro M  ⁣ M\,\!.

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

Lemma (Rek. spočetná množina je obor hodnot ČRF)

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

Důkaz

Pro každou množinu WxW_x vytvoříme množinu dvojic R={⟨y,y⟩:y∈Wx}  ⁣ R=\{\langle y,y\rangle:y \in W_x\}\,\!. Množina R  ⁣ R\,\! je rekurzivně spočetná, tedy má ČRF selektor φ  ⁣ \varphi\,\!, platí dom(φ)=rng(φ)=Wx  ⁣ dom(\varphi)=rng(\varphi)=W_x\,\!.

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

Věta (ČRF odpovídá Rek. spočetným množinám)

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

Důkaz

Máme ČRF g  ⁣ g\,\! a její obor hodnot. Zkonstruujeme pseudoinverzní funkci h  ⁣ h\,\! k ČRF g  ⁣ g\,\!, tj. funkci takovou, že dom(h)=rng(g)  ⁣ dom(h)=rng(g)\,\! a to tak, že vyrobíme RS predikát Q(x,y)⇔g(x)≃y  ⁣ Q(x,y)\Leftrightarrow g(x)\simeq y\,\! a to má ČRF selektor, který hledáme -- h  ⁣ h\,\!.

Definice (Úseková funkce)

Funkce f  ⁣ f\,\! je úseková, jestliže jejím definičním oborem je počáteční úsek N  ⁣ \mathbb N\,\! (nebo celé N  ⁣ \mathbb N\,\!).

Věta (Rek. množiny a úsekové ČRF)

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

Důkaz

⇒  ⁣ \Rightarrow\,\!: Definujeme ČRF f  ⁣ f\,\!, která bude rostoucí a úseková.

  • Začneme f(0)≃μx(x∈M)  ⁣ f(0) \simeq \mu_x(x\in M)\,\!.

  • Dále f(n+1)≃μy(y>f(n)∧y∈M)  ⁣ f(n+1) \simeq \mu_y(y > f(n) \wedge y \in M)\,\!

⇐  ⁣ \Leftarrow\,\!: Máme f  ⁣ f\,\! rostoucí úsekovou ČRF.

  1. V případě, že je f  ⁣ f\,\! má konečné dom  ⁣ dom\,\! (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe D=dom(f)  ⁣ D=dom(f)\,\! a tedy rng(f)  ⁣ rng(f)\,\! je rekurzivní.

  2. V případě, že je f  ⁣ f\,\! je všude definovaná (totální): y∈M=rng(f)⇔∃x:(f(x)=y))⇔∃x ⁣≤ ⁣y:(f(x)=y) y \in M=rng(f) \Leftrightarrow \exists x:(f(x)=y)) \Leftrightarrow \exists x\!\leq\!y: (f(x)=y) Poslední ekvivalence platí, protože f  ⁣ f\,\! je rostoucí a úseková. Tedy y∈M⇔y∈{f(0),…,f(y)}. y \in M \Leftrightarrow y \in \{f(0),\ldots,f(y)\}.

Věta (O generování)

Mějme nekonečnou množinu M  ⁣ M\,\!. Potom:

  • Množina M  ⁣ M\,\! je rekurzivní, právě když M  ⁣ M\,\! lze generovat rostoucí ORF.

  • Množina M  ⁣ M\,\! je rekurzivně spočetná, právě když M  ⁣ M\,\! lze generovat prostou ORF.

Důkaz

Důsledek předchozí, resp. následující věty.

Věta (Rek. spočetné množiny a prosté úsekové ČRF)

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

Důkaz

"⇐  ⁣ \Leftarrow\,\!": Víme, obor hodnot ČRF je rekurzivně spočetná množina (z věty <#ČRF%20odpovídá%20Rek.%20spočetným%20množinám>).

"⇒  ⁣ \Rightarrow\,\!": Mějme ČRF φ  ⁣ \varphi\,\! (M=rng(φ)  ⁣ M=rng(\varphi)\,\! pro nějaké φ  ⁣ \varphi\,\!, z lemmatu <#Lemma%20%28Rek.%20spočetná%20množina%20je%20obor%20hodnot%20ČRF%29>).

Důkaz provedeme pomocí rekurzivní množiny B={⟨x,s⟩:φ(x) ⁣ ⁣↓ B=\{\langle x,s\rangle:\varphi(x)\!\!\downarrow přesně za s  ⁣s\,\! kroků }   \}\,\;. Je vidět, že každé xx bude pouze v jednom z párů ⟨x,s⟩\langle x,s\rangle.

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

Důsledek

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

Důkaz

Mějme f  ⁣ f\,\!, která prostě generuje M  ⁣ M\,\!. Vyber rostoucí podposloupnost. Ta je rekurzivní.

:g(0)=f(0)  ⁣ g(0)=f(0)\,\! :g(n+1)=f(μj(f(j)>g(n)))  ⁣g(n+1)=f(\mu_j (f(j)>g(n)))\,\!

Obor hodnot g  ⁣ g\,\! je nekonečná rekurzivní množina a je podmnožinou M  ⁣ M\,\!.

{{Statnice I3}}