{{TIN064 Skripta}} {{TODO|Je potřeba k těm základním kefrům připsat pořádné důkazy (snad se stalo, ale někdo jiný by je teď měl všechny zkontrolovat ;-D)}}

Rekurzivně a efektivně neoddělitelné množiny

*Def: disjunktní množiny A a B jsou rekurzivně neoddělitelné, jestliže neexistuje rekurzivní M taková, že AMBMA \subseteq M \land B \subseteq \overline M (tedy ORF neumějí rozhodnout, jestli je prvek v A či B)

*Def: disjunktní RS množiny A a B jsou efektivně neoddělitelné, jestliže existuje ČRF f taková, že (AWx)(BWy)(WxWy=)f(x,y)(f(x,y)WxWy)(A \subseteq W_x) \land (B \subseteq W_y) \land (W_x \cap W_y = \emptyset) \Longrightarrow f(x,y) \downarrow \land \, (f(x,y) \notin W_x \cup W_y) (tedy "W-aproximace" množin A a B umožňují efektivně generovat body mimo tuto aproximaci)

Poznámka: Čo ale teda znamená, že množiny A a B sú efektívne oddeliteľné? Dá sa povedať, že v takom prípade sa dá celý priestor ℕ rozdeliť na W<sub>x</sub> ⊇ A, W<sub>y</sub> ⊇ B a nejakú "škárku" ℕ(W<sub>x</sub> ∪ W<sub>y</sub>), do ktorej už ale "nedočiahne" naša ČRF f s parametrami (x,y). Pozor na to, že najprv fixujeme funkciu f a až potom môžeme začať uvažovať všetky kombinácie x,y. Na rozdiel od rekurzívnej oddeliteľnosti, kde intuícia je "obaliť množinu A", pri tejto oddeliteľnosti rozdeľujeme celý priestor na dve sekcie plus nejaký nedosiahnuteľný zvyšok.

Pozorování: Efektivně neoddělitelné množiny jsou rekurzivně neoddělitelné.

Důkaz: Mějme A, B efektivně neoddělitelné. Pro spor nechť je odděluje rekurzivní množina M, pak ale najdeme (Wx=M)(Wy=M)(WxWy=N)(W_x = M) \land (W_y = \overline M) \Rightarrow (W_x \cup W_y = \mathbb{N}) a samozřejmě nemůžeme sestrojit f, která by střílela mimo N\mathbb{N}.

Existence neoddělitelných množin

Věta: Rekurzivně neoddělitelné množiny nemusejí být efektivně neoodělitelné.

Důkaz: Prý je těžký.

Věta: Existují disjunktní rekurzivně spočetné množiny A, B, které jsou efektivně neoddělitelné.

Důkaz:

  • A={x:φx(x)0}A = \{ x: \varphi_x(x) \simeq 0 \}, B={x:φx(x)1}B = \{ x : \varphi_x(x) \simeq 1 \}

  • Idea: Máme pro zadané WxW_x a WyW_y, že AWxA \subseteq W_x a BWyB \subseteq W_y najít bod mimo WxWyW_x \cup W_y. To uděláme tak, že pro xx a yy vyrobíme φα(x,y)(w)\varphi_{\alpha(x,y)}(w) divergující právě tehdy, když wABw \notin A \cup B. Sporem ukážeme, že sama na sebe také oddiverguje, a proto α(x,y)WxWy\alpha(x,y) \notin W_x \cup W_y, a tedy bod α(x,y)\alpha(x,y) můžeme použít.

*Provedení: snadno (s-m-n větou) nahlédneme, že existuje nějaká funkce φα(x,y)(w)\varphi_{\alpha(x,y)}(w) taková, že vrátí 1, pokud ww padne dříve do WxW_x než do WyW_y, vrátí 0, pokud ww padne dříve do WyW_y než do WxW_x a diverguje, pokud wWxWyw \notin W_x \cup W_y. Pokud za ww dosadíme α(x,y)\alpha(x,y), funkce jistě diverguje a bod tedy leží mimo WxWyW_x \cup W_y. Proč φα(x,y)(α(x,y))\varphi_{\alpha(x,y)}(\alpha(x,y)) diverguje?

  • Kdyby α(x,y)\alpha(x,y) padlo do WxW_x, tak φα(x,y)(α(x,y))\varphi_{\alpha(x,y)}(\alpha(x,y)) vrátí 1, takže α(x,y)B\alpha(x,y)\in B - spor, jelikož jsme předpokládali, že AWxA \subseteq W_x a tedy průnik WxWyW_x \cap W_y \neq\empty.

  • Symetricky pro WyW_y.

Souvislost efektivní neoddělitelnosti s kreativitou

Pozorování: Efektivně neoddělitelné r.s. množiny A, B a ABA \cup B jsou kreativní množiny.

Důkaz: Pro sjednocení rekurzivně spočetných množin ABA \cup B: Mějme AA a BB neoddělitelné, ukážeme, že AB\overline{A \cup B} je produktivní. Mějme nějakou RSM ZABZ \subset \overline{A \cup B}, jako rekurzivně spočetnou obálku AA zvolíme AA, jako obálku BB zvolíme BZB \cup Z. Protože A,BA, B jsou neoddělitelné, funkce, která to dokazuje, vrátí prvek mimo tyto obálky - speciálně tedy v ABZ\overline{A \cup B} \setminus Z.

A je kreativní (pro B bude důkaz symetrický): úplně stejně, jen ZAZ \subset \overline{A}. Jako rekurzivně spočetnou obálku AA opět zvolíme AA, jako obálku BB zvolíme BZB \cup Z.

1-úplnost

*Def: Nechť (A,B), (C,D) jsou dvě dvojice disjunktních množin, definujeme 1-převoditelnost (A,B)1(C,D)(A,B) \le_1 (C,D), pokud existuje prostá ORF h taková, že xAh(x)Cx \in A \Leftrightarrow h(x) \in C, xBh(x)Dx \in B \Leftrightarrow h(x) \in D, xABh(x)CDx \notin A \cup B \Leftrightarrow h(x) \notin C \cup D.

*Def: Disjunktní dvojice (A,B) je 1-úplná, pokud pro každou disjunktní (C,D) platí (C,D)1(A,B)(C,D) \le_1 (A,B).

Ekvivalence 1-úplnosti a efektivní neoddělitelnosti

Dokážeme dvě implikace: doprava je to docela snadné, doleva použijeme dvojnou větu o rekurzi.

1-úplná dvojice je efektivně neoddělitelná

Důkaz: Mějme dvojici množin CC a DD, která je 1-úplná. Lze na ni tedy převést jakoukoliv jinou dvojici množin, včetně takové dvojice množin AA, BB, která je efektivně neoddělitelná (předchozí věta zaručuje existenci nějaké takové dvojice a existenci funkce ff, která jejich neoddělitelnost dokazuje). Platí (A,B)1(C,D)(A, B) \le_1 (C, D) pomocí funkce hh.

Nyní nechť existují nějaké množiny WxW_x a WyW_y, které oddělují CC a DD. Potom vezmeme vzory těchto množin (při hh) a aplikujeme na ně ff. Tím dostaneme bod mimo tyto vzory a opětovnou aplikací hh získáme bod mimo WxW_x a WyW_y.

Dvojná věta o rekurzi

Věta: Velmi hrubě: Pro ORF f,g existují m,n takové, že φm=φf(m,n)\varphi_m = \varphi_{f(m,n)}, φn=φg(m,n)\varphi_n = \varphi_{g(m,n)}. (Pro více parametrů f,g je srazíme s-m-n větou.)

Důkaz: Dokážeme, že existují m,nm, n tak, že φm=φf(m,n)\varphi_m = \varphi_{f(m,n)}, φn=φg(m,n)\varphi_n = \varphi_{g(m,n)}.

Mějme φf(x,y)\varphi_{f(x,y)}. Pomocí věty o rekurzi (té poslední, co funguje v závislosti na parametrech) získáme funkci α\alpha takovou, že φf(α(y),y)=φα(y)\varphi_{f(\alpha(y),y)} = \varphi_{\alpha(y)}.

Nyní si vezmeme funkci φg(α(y),y)\varphi_{g(\alpha(y),y)}. To je funkce v jedné proměnné, takže na ni můžeme aplikovat větu o rekurzi (tentokrát tu první) a dostaneme nn tak, že φg(α(n),n)=φn\varphi_{g(\alpha(n),n)} = \varphi_{n}. Tím jsme hotoví, jelikož můžeme volit mm jako α(n)\alpha(n).

Efektivně neoddělitelná dvojice je 1-úplná

Důkaz: Použijeme podobný trik, jako když jsme dokazovali existenci ORF produktivní funkce, jen teď budeme pracovat s dvěma funkcemi (a dvojnou větou o rekurzi). Pro efektivně neoddělitelnou dvojici (A,B)(A, B) (a funkci ff, která neoddělitelnost dokazuje) a nějakou dvojici (C,D)(C, D) nadefinujeme množiny Wω1(x)W_{\omega_1(x)} a Wω2(x)W_{\omega_2(x)} takto:

Pokud xDx \in D, tak Wω1(x)=A{f(ω1(x),ω2(x))}W_{\omega_1(x)} = A \cup \{f(\omega_1(x), \omega_2(x))\}, v opačném případě Wω1(x)=AW_{\omega_1(x)} = A. Stejně tak, pokud xCx \in C, tak Wω2(x)=B{f(ω1(x),ω2(x))}W_{\omega_2(x)} = B \cup \{f(\omega_1(x), \omega_2(x))\}, v opačném případě Wω2(x)=BW_{\omega_2(x)} = B.

Nyní je snadné vidět, že pokud x∉CDx \not\in C \cup D, tak Wω1(x)=AW_{\omega_1(x)} = A a Wω2(x)=BW_{\omega_2(x)} = B, takže f(ω1(x),ω2(x))∉AB f(\omega_1(x), \omega_2(x)) \not\in A \cup B.

Co se stane v případě, kdy xCx \in C (a tedy x∉D x \not\in D)? Ukážeme, že potom f(ω1(x),ω2(x))A f(\omega_1(x), \omega_2(x)) \in A - kdyby tomu totiž bylo jinak, byly by Wω1(x)=AW_{\omega_1(x)} = A a Wω2(x)=B{f(ω1(x),ω2(x))}W_{\omega_2(x)} = B \cup \{f(\omega_1(x), \omega_2(x))\} nadmnožinami AA a BB. To znamená, že by funkce ff musela vracet nějaký bod mimo ně, platilo by tedy f(ω1(x),ω2(x))∉Wω1(x)Wω2(x)f(\omega_1(x), \omega_2(x)) \not\in W_{\omega_1(x)} \cup W_{\omega_2(x)}. To je ovšem spor, protože f(ω1(x),ω2(x))Wω2(x)f(\omega_1(x), \omega_2(x)) \in W_{\omega_2(x)}.

Případ, kdy xDx \in D, se dokáže úplně stejně.

Zbývá jen rozmyslet si, kdo nám zaručí existenci šikovných funkcí ω\omega, to by ale pro čtenáře, který se dostal až sem, mělo být jednoduché cvičení na použití dvojné věty o rekurzi.

Bonus

Věta: Rekurzivně neoddělitelné dvojice jsou mezi sebou všechny navzájem rekurzivně izomorfní.