TIN064 Neoddělitelné množiny: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(1-úplná dvojice je efektivně neoddělitelná: Spor to neni, naopak jsme sli podle definice ef. neodd. mnozin a overili jsme, ze pri splnene premise plati zaver)
(Existence neoddělitelných množin)
Řádka 23: Řádka 23:
  
 
*'''Provedení:''' snadno (s-m-n větou) nahlédneme, že existuje nějaká funkce <math>\varphi_{\alpha(x,y)}(w)</math> taková, že vrátí 1, pokud <math>w</math> padne dříve do <math>W_x</math> než do <math>W_y</math>, vrátí 0, pokud <math>w</math> padne dříve do <math>W_y</math> než do <math>W_x</math> a diverguje, pokud <math>w \notin W_x \cup W_y</math>. Pokud za <math>w</math> dosadíme <math>\alpha(x,y)</math>, funkce jistě diverguje a bod tedy leží mimo <math>W_x \cup W_y</math>. Proč <math>\varphi_{\alpha(x,y)}(\alpha(x,y))</math> diverguje?  
 
*'''Provedení:''' snadno (s-m-n větou) nahlédneme, že existuje nějaká funkce <math>\varphi_{\alpha(x,y)}(w)</math> taková, že vrátí 1, pokud <math>w</math> padne dříve do <math>W_x</math> než do <math>W_y</math>, vrátí 0, pokud <math>w</math> padne dříve do <math>W_y</math> než do <math>W_x</math> a diverguje, pokud <math>w \notin W_x \cup W_y</math>. Pokud za <math>w</math> dosadíme <math>\alpha(x,y)</math>, funkce jistě diverguje a bod tedy leží mimo <math>W_x \cup W_y</math>. Proč <math>\varphi_{\alpha(x,y)}(\alpha(x,y))</math> diverguje?  
** Kdyby <math>\alpha(x,y)</math> padlo do <math>W_x</math>, tak <math>\varphi_{\alpha(x,y)}(\alpha(x,y))</math> vrátí 1, takže <math>\alpha(x,y)\in B</math> - spor, jelikož jsme předpokládali, že <math>W_x \subseteq A</math> a tedy průnik <math>W_x \cap W_y \neq\empty</math>.  
+
** Kdyby <math>\alpha(x,y)</math> padlo do <math>W_x</math>, tak <math>\varphi_{\alpha(x,y)}(\alpha(x,y))</math> vrátí 1, takže <math>\alpha(x,y)\in B</math> - spor, jelikož jsme předpokládali, že <math>A \subseteq W_x</math> a tedy průnik <math>W_x \cap W_y \neq\empty</math>.  
 
** Symetricky pro <math>W_y</math>.
 
** Symetricky pro <math>W_y</math>.
  

Verze z 13. 5. 2012, 15:00

Tato část je neúplná a potřebuje rozšířit. 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 $ 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)

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

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

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 $.

TODO: Ukázat, že A je kreativní (pro B bude důkaz symetrický).

1-úplnost

  • 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

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 $ 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

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á

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

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