{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke státnicovým okruhům z vyčíslitelnosti pro obory Matematická lingvistika a 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 -- Tuetschek 14:01, 17 Aug 2010 (CEST)

}}

Rekurzivně spočetné množiny

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

Charakteristická funkce množiny <math>M</math> označuje charakteristickou funkci predikátu náležení do množiny, tj. funkci <math>c_M(x)</math>, kde <math>c_M(x) = \downarrow 1</math> pro <math>x\in M</math> a <math>c_M(x) \downarrow = 0</math> pro <math>x\notin M</math>.

Analogicky se definuje částečná charakteristická funkce množiny -- <math>c_M(x) = \downarrow 1</math> pro <math> x \in M</math> a <math>c_M(x)\uparrow</math> pro <math>x \notin M</math>.

Množina <math> M\,\!</math> je rekurzivní, je-li její charakteristická funkce obecně rekurzivní (každá char. fce je totální, takže ČRF by bylo totéž). Množina <math> M\,\!</math> 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 (<math> dom, rng\,\!</math>)

V následujícím <math> dom\,\!</math> značí definiční obor, <math> rng\,\!</math> obor hodnot.

Definice (<math> x\,\!</math>-tá rekurzivně spočetná množina)

<math> W_x\,\!</math> (<math> x\,\!</math>-tá rekurzivně spočetná množina) <math> = dom(\varphi_x) = \{y:\varphi_x(y)\!\!\downarrow\}\,\!</math>

Definice (K)

<math> K = \{x:x\in W_x\} = \{x:\varphi_x(x)\!\!\downarrow\} = \{x:\Psi_1(x,x)\!\!\downarrow\}\,\!</math>

Množina <math> K\,\!</math> vlastně odpovídá halting problému. Platí o ní následující tvrzení.

Věta (Rekurzivní spočetnost <math> K\,\!</math>)

Množina <math> K\,\!</math> je rekurzivně spočetná, není rekurzivní, <math> \overline K\,\!</math> není rekurzivně spočetná.

Důkaz

<math> K\,\!</math> není rekurzivní, neboť <math> \overline K\,\!</math> není rekurzivně spočetná. <math> \overline K\,\!</math> není rekurzivně spočetná, neboť kdyby byla, měla by index <math> x_0\,\!</math>. Jednoduchou diagonalizací dostáváme <math> x_0 \in \overline{K} \Leftrightarrow x_0 \in W_{x_0} \Leftrightarrow x_0 \in K\,\!</math>. Spor.

1-převeditelnost, m-převeditelnost

Definice (<math> 1\,\!</math>-převeditelnost, <math> m\,\!</math>-převeditelnost, <math> 1\,\!</math>-úplnost, <math> m\,\!</math>-úplnost)

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

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

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

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

Věta (1-úplnost <math> K\,\!</math>)

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

Důkaz

Mějme libovolnou rekurzivně spočetnou množinu <math> W_x\,\!</math>.

Mějme ČRF <math> \alpha(y,x,w)\,\!</math>, popisující <math> x\,\!</math>-tou rekurzivně spočetnou množinu. Tedy <math> \alpha(y,x,w)\!\!\downarrow \Leftrightarrow y \in W_x \Leftrightarrow \Psi_1(x,y)\!\!\downarrow \Leftrightarrow \varphi_x(y)\!\!\downarrow. </math> <math>w</math> je tady fiktivní proměnná, funkce <math> \alpha\,\!</math> na její hodnotě nezáleží. Z s-m-n věty dostáváme: <math> \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). </math> Označme <math> h(y,x)=s_2(a,y,x)\,\!</math> (<math> s_2\,\!</math> je PRF, tím spíše ORF). <math> 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 </math> Zde jsme mohli za <math> w\,\!</math> dosadit <math> h(y,x)\,\!</math>, neboť hodnota <math> \alpha\,\!</math> na <math> w\,\!</math> nezáleží! Tedy <math> W_x \leq_1\!K\,\!</math> pomocí funkce <math> \lambda y:h(y,x)\,\!</math>.

Lemma (<math> K_0\,\!</math> je 1-úplná)

<math> K_0 = \{\langle y,x\rangle: y \in W_x\}\,\!</math> je 1-úplná.

Důkaz

Zřejmé. <math> K \leq_1 K_0\,\!</math> a <math> K\,\!</math> je <math> 1\,\!</math>-úplná.

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

  1. Relace <math> \leq_1\,\!</math> a <math> \leq_m\,\!</math> jsou tranzitivní, reflexivní.

  2. <math> A \leq_1 B \Rightarrow A \leq_m B\,\!</math>

  3. <math> B\,\!</math> rekurzivní, <math> A \leq_m B \Rightarrow A\,\!</math> rekurzivní.

  4. <math> B\,\!</math> rekurzivně spočetná, <math> A \leq_m B \Rightarrow A\,\!</math> rekurzivně spočetná.

Důkaz

  1. Zřejmé.

  2. Zřejmé.

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

  4. Stejně.

Důsledek

<math> K\,\!</math> a <math> \overline K\,\!</math> jsou <math> m\,\!</math>-nesrovnatelné.

Důkaz

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

Definice (Rekurzivní permutace)

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

Definice (Rekurzivní isomorfismus)

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

Definice (1-ekvivalence a m-ekvivalence)

  • <math> A \equiv_1 B\,\!</math>, jestliže <math> A \leq_1 B \wedge B\leq_1 A\,\!</math>.

  • <math> A \equiv_m B\,\!</math>, jestliže <math> A \leq_m B \wedge B\leq_m A\,\!</math>.

Věta (Myhillova)

<math> A \equiv B \Leftrightarrow A \equiv_1 B\,\!</math>

Důkaz

Jedná se o vlastně o obdobu Cantor-Bernsteinovy věty.

<math> \Rightarrow\,\!</math> Triviální.

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

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

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

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

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

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

  2. <math> f(0)\neq 0\,\!</math>: rozlišíme dva podpřípady

    1. <math> g(0)\neq 0\,\!</math>: definujeme <math> h(g(0))=0\,\!</math>.
      Tedy <math> 0 \in dom(h) \cap rng(h)\,\!</math>.

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

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

Důsledek

<math> K \equiv K_0\,\!</math>.

Důkaz

Zřejmé, neboť <math> K \equiv_1 K_0\,\!</math> (obě množiny jsou 1-úplné).

Rekurzivně spočetné predikáty

Lemma (ORF <math> \to\,\!</math> RSP)

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

Důkaz

<math> \mu_y Q\,\!</math> je ČRF, její definiční obor je <math>\{ \exists y:Q \}\,\!</math>.

Věta (Univerzální RSP)

Predikát <math> \exists y T_k(e,x_1,\ldots,x_k,y)\,\!</math> je univerzálním RSP pro třídu RSP <math> k\,\!</math> 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 (<math> (w)_{2,1}\,\!</math> znamená to, že <math> w\,\!</math> kóduje usp. dvojici a vybíráme z ní první prvek; to je PRF): <math> \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})) </math>. Uvedený predikát je rekurzivně spočetný, tedy má nějaký index, tj. ekvivalence pokračuje: <math>\exists w T_{k+2}(e,a,b,\vec{x},w) \Leftrightarrow \exists w T_k(s_2(e,a,b),\vec{x},w) </math>

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 <math> (\forall y)_{y \leq t}\,\!</math> a existenční kvantifikace (pro <math> k\geq 2\,\!</math>) zachovávají rekurzivní spočetnost.

Důkaz

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

Formálně: <math> (\forall y)_{y \leq t}\ \exists s: T_k(e,x_1,\ldots,x_{k-1},y,s) \Leftrightarrow \exists </math> kód <math>(t\!+\!1)</math>-tice <math> w:\ (\forall y)_{y \leq t}\ T_k(e,x_1,\ldots,x_{k-1},y,(w)_{t+1,y}) </math>.

<math>y</math> můžeme zkoušet primitivní rekurzí, <math>w</math> minimalizací, dostáváme tedy rekurzivně spočetný predikát, který má nějaký index <math> b\,\!</math>, dále můžeme použít S-m-n větu. <math> \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). </math>

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 <math> k\!-\!1\,\!</math> proměnných, proto je ve větě požadavek na minimální velikost <math> k\geq 2\,\!</math>.

:<math> \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})</math> :<math> \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) </math>

Poznámka

Neomezená obecná kvantifikace (<math> \forall\,\!</math>) rekurzivní spočetnost nezachovává.

Věta (O selektoru)

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

:<math> \varphi(x_1,\ldots,x_k)\!\!\downarrow \Leftrightarrow \exists y: Q(x_1,\ldots,x_k,y)</math> :<math>\varphi(x_1,\ldots,x_k)\!\!\downarrow \Rightarrow Q(x_1,\ldots,x_k,\varphi(x_1,\ldots,x_k)) </math>

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

Důkaz

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

Obecně: univerzální vyjádření RSP <math> \exists s: T_{k+1}(e,\vec{x},y,s)\,\!</math>, hledáme nejmenší <math> w\,\!</math> (kód dvojice) takové, že <math> \varphi(\vec{x}) \simeq (\mu_w T_{k+1}(e,\vec{x},(w)_{2,1},(w)_{2,2}))_{2,1}. </math> Funkce <math> \varphi\,\!</math> 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 <math> \Leftrightarrow\,\!</math> má rekurzivně spočetný graf.

Důkaz

Je-li <math> \varphi\,\!</math> ČRF, je její graf rekurzivně spočetný: <math>\langle x_1,\ldots,x_k,y\rangle \in \mbox{Graf} \Leftrightarrow \exists s:\,\!</math> za <math> s\,\!</math> kroků program konverguje.

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

Věta (Postova)

Množina <math> M\,\!</math> je rekurzivní, právě když <math> M\,\!</math> i <math> \overline M\,\!</math> jsou rekurzivně spočetné.

Predikát <math> Q\,\!</math> je ORP, právě když <math> Q\,\!</math> i <math> \neg Q\,\!</math> jsou RSP.

Důkaz

"<math> \Rightarrow\,\!</math>": Triviální.

"<math> \Leftarrow\,\!</math>": Intuitivně: <math> M=dom(P_1)\,\!</math>, <math> \overline M=dom(P_2)\,\!</math>. Pustíme oba programy současně a čekáme, který se zastaví. Zastaví se právě jeden.

Formálně: <math> (x \in M \wedge y=1) \lor (x \in \overline M \wedge y=0)\,\!</math> je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro <math> M\,\!</math>.

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 <math>W_x</math> vytvoříme množinu dvojic <math> R=\{\langle y,y\rangle:y \in W_x\}\,\!</math>. Množina <math> R\,\!</math> je rekurzivně spočetná, tedy má ČRF selektor <math> \varphi\,\!</math>, platí <math> dom(\varphi)=rng(\varphi)=W_x\,\!</math>.

Myšlenka toho důkazu je, že body, kde <math> \varphi_x\,\!</math> 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 <math> g\,\!</math> a její obor hodnot. Zkonstruujeme pseudoinverzní funkci <math> h\,\!</math> k ČRF <math> g\,\!</math>, tj. funkci takovou, že <math> dom(h)=rng(g)\,\!</math> a to tak, že vyrobíme RS predikát <math> Q(x,y)\Leftrightarrow g(x)\simeq y\,\!</math> a to má ČRF selektor, který hledáme -- <math> h\,\!</math>.

Definice (Úseková funkce)

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

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

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

Důkaz

<math> \Rightarrow\,\!</math>: Definujeme ČRF <math> f\,\!</math>, která bude rostoucí a úseková.

  • Začneme <math> f(0) \simeq \mu_x(x\in M)\,\!</math>.

  • Dále <math> f(n+1) \simeq \mu_y(y > f(n) \wedge y \in M)\,\!</math>

<math> \Leftarrow\,\!</math>: Máme <math> f\,\!</math> rostoucí úsekovou ČRF.

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

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

Věta (O generování)

Mějme nekonečnou množinu <math> M\,\!</math>. Potom:

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

  • Množina <math> M\,\!</math> je rekurzivně spočetná, právě když <math> M\,\!</math> 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

"<math> \Leftarrow\,\!</math>": Víme, obor hodnot ČRF je rekurzivně spočetná množina (z věty že ČRF odpovídají RSM).

"<math> \Rightarrow\,\!</math>": Mějme ČRF <math> \varphi\,\!</math> (<math> M=rng(\varphi)\,\!</math> pro nějaké <math> \varphi\,\!</math>, z lemmatu že RSM je obor hodnot ČRF).

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

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

Důsledek

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

Důkaz

Mějme <math> f\,\!</math>, která prostě generuje <math> M\,\!</math>. Vyber rostoucí podposloupnost. Ta je rekurzivní.

:<math> g(0)=f(0)\,\!</math> :<math>g(n+1)=f(\mu_j (f(j)>g(n)))\,\!</math>

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

{{Statnice I3}}