TIN064 Neoddělitelné množiny
| Wiki-skripta pro Vyčíslitelnost I |
| Obsah |
|---|
|
Rekurzivně a efektivně neoddělitelné množiny[editovat | editovat zdroj]
- Def: disjunktní množiny A a B jsou rekurzivně neoddělitelné, jestliže neexistuje rekurzivní M taková, že $ A \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 $ (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 Wx ⊇ A, Wy ⊇ B a nejakú "škárku" ℕ\(Wx ∪ Wy), 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 $ (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 $ \mathbb{N} $.
Existence neoddělitelných množin[editovat | editovat zdroj]
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: \varphi_x(x) \simeq 0 \} $, $ B = \{ x : \varphi_x(x) \simeq 1 \} $
- Idea: Máme pro zadané $ W_x $ a $ W_y $, že $ A \subseteq W_x $ a $ B \subseteq W_y $ najít bod mimo $ W_x \cup W_y $. To uděláme tak, že pro $ x $ a $ y $ vyrobíme $ \varphi_{\alpha(x,y)}(w) $ divergující právě tehdy, když $ w \notin A \cup B $. Sporem ukážeme, že sama na sebe také oddiverguje, a proto $ \alpha(x,y) \notin W_x \cup W_y $, a tedy bod $ \alpha(x,y) $ můžeme použít.
- Provedení: snadno (s-m-n větou) nahlédneme, že existuje nějaká funkce $ \varphi_{\alpha(x,y)}(w) $ taková, že vrátí 1, pokud $ w $ padne dříve do $ W_x $ než do $ W_y $, vrátí 0, pokud $ w $ padne dříve do $ W_y $ než do $ W_x $ a diverguje, pokud $ w \notin W_x \cup W_y $. Pokud za $ w $ dosadíme $ \alpha(x,y) $, funkce jistě diverguje a bod tedy leží mimo $ W_x \cup W_y $. Proč $ \varphi_{\alpha(x,y)}(\alpha(x,y)) $ diverguje?
- Kdyby $ \alpha(x,y) $ padlo do $ W_x $, tak $ \varphi_{\alpha(x,y)}(\alpha(x,y)) $ vrátí 1, takže $ \alpha(x,y)\in B $ - spor, jelikož jsme předpokládali, že $ A \subseteq W_x $ a tedy průnik $ W_x \cap W_y \neq\empty $.
- Symetricky pro $ W_y $.
Souvislost efektivní neoddělitelnosti s kreativitou[editovat | editovat zdroj]
Pozorování: Efektivně neoddělitelné r.s. množiny A, B a $ A \cup B $ jsou kreativní množiny.
Důkaz: Pro sjednocení rekurzivně spočetných množin $ A \cup B $: Mějme $ A $ a $ B $ neoddělitelné, ukážeme, že $ \overline{A \cup B} $ je produktivní. Mějme nějakou RSM $ Z \subset \overline{A \cup B} $, jako rekurzivně spočetnou obálku $ A $ zvolíme $ A $, jako obálku $ B $ zvolíme $ B \cup Z $. Protože $ A, B $ jsou neoddělitelné, funkce, která to dokazuje, vrátí prvek mimo tyto obálky - speciálně tedy v $ \overline{A \cup B} \setminus Z $.
A je kreativní (pro B bude důkaz symetrický): úplně stejně, jen $ Z \subset \overline{A} $. Jako rekurzivně spočetnou obálku $ A $ opět zvolíme $ A $, jako obálku $ B $ zvolíme $ B \cup Z $.
1-úplnost[editovat | editovat zdroj]
- Def: Nechť (A,B), (C,D) jsou dvě dvojice disjunktních množin, definujeme 1-převoditelnost $ (A,B) \le_1 (C,D) $, pokud existuje prostá ORF h taková, že $ x \in A \Leftrightarrow h(x) \in C $, $ x \in B \Leftrightarrow h(x) \in D $, $ x \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) \le_1 (A,B) $.
Ekvivalence 1-úplnosti a efektivní neoddělitelnosti[editovat | editovat zdroj]
Dokážeme dvě implikace: doprava je to docela snadné, doleva použijeme dvojnou větu o rekurzi.
1-úplná dvojice je efektivně neoddělitelná[editovat | editovat zdroj]
Důkaz: Mějme dvojici množin $ C $ a $ D $, která je 1-úplná. Lze na ni tedy převést jakoukoliv jinou dvojici množin, včetně takové dvojice množin $ A $, $ B $, která je efektivně neoddělitelná (předchozí věta zaručuje existenci nějaké takové dvojice a existenci funkce $ f $, která jejich neoddělitelnost dokazuje). Platí $ (A, B) \le_1 (C, D) $ pomocí funkce $ h $.
Nyní nechť existují nějaké množiny $ W_x $ a $ W_y $, které oddělují $ C $ a $ D $. Potom vezmeme vzory těchto množin (při $ h $) a aplikujeme na ně $ f $. Tím dostaneme bod mimo tyto vzory a opětovnou aplikací $ h $ získáme bod mimo $ W_x $ a $ W_y $.
Dvojná věta o rekurzi[editovat | editovat zdroj]
Věta: Velmi hrubě: Pro ORF f,g existují m,n takové, že $ \varphi_m = \varphi_{f(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, n $ tak, že $ \varphi_m = \varphi_{f(m,n)} $, $ \varphi_n = \varphi_{g(m,n)} $.
Mějme $ \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 $ \varphi_{f(\alpha(y),y)} = \varphi_{\alpha(y)} $.
Nyní si vezmeme funkci $ \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 $ n $ tak, že $ \varphi_{g(\alpha(n),n)} = \varphi_{n} $. Tím jsme hotoví, jelikož můžeme volit $ m $ jako $ \alpha(n) $.
Efektivně neoddělitelná dvojice je 1-úplná[editovat | editovat zdroj]
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 funkci $ f $, která neoddělitelnost dokazuje) a nějakou dvojici $ (C, D) $ nadefinujeme množiny $ W_{\omega_1(x)} $ a $ W_{\omega_2(x)} $ takto:
Pokud $ x \in D $, tak $ W_{\omega_1(x)} = A \cup \{f(\omega_1(x), \omega_2(x))\} $, v opačném případě $ W_{\omega_1(x)} = A $. Stejně tak, pokud $ x \in C $, tak $ W_{\omega_2(x)} = B \cup \{f(\omega_1(x), \omega_2(x))\} $, v opačném případě $ W_{\omega_2(x)} = B $.
Nyní je snadné vidět, že pokud $ x \not\in C \cup D $, tak $ W_{\omega_1(x)} = A $ a $ W_{\omega_2(x)} = B $, takže $ f(\omega_1(x), \omega_2(x)) \not\in A \cup B $.
Co se stane v případě, kdy $ x \in C $ (a tedy $ x \not\in D $)? Ukážeme, že potom $ f(\omega_1(x), \omega_2(x)) \in A $ - kdyby tomu totiž bylo jinak, byly by $ W_{\omega_1(x)} = A $ a $ W_{\omega_2(x)} = B \cup \{f(\omega_1(x), \omega_2(x))\} $ nadmnožinami $ A $ a $ B $. To znamená, že by funkce $ f $ musela vracet nějaký bod mimo ně, platilo by tedy $ 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(\omega_1(x), \omega_2(x)) \in W_{\omega_2(x)} $.
Případ, kdy $ x \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[editovat | editovat zdroj]
Věta: Rekurzivně neoddělitelné dvojice jsou mezi sebou všechny navzájem rekurzivně izomorfní.
