{{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 (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 (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 a samozřejmě nemůžeme sestrojit f, která by střílela mimo .
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:
,
Idea: Máme pro zadané a , že a najít bod mimo . To uděláme tak, že pro a vyrobíme divergující právě tehdy, když . Sporem ukážeme, že sama na sebe také oddiverguje, a proto , a tedy bod můžeme použít.
*Provedení: snadno (s-m-n větou) nahlédneme, že existuje nějaká funkce taková, že vrátí 1, pokud padne dříve do než do , vrátí 0, pokud padne dříve do než do a diverguje, pokud . Pokud za dosadíme , funkce jistě diverguje a bod tedy leží mimo . Proč diverguje?
Kdyby padlo do , tak vrátí 1, takže - spor, jelikož jsme předpokládali, že a tedy průnik .
Symetricky pro .
Souvislost efektivní neoddělitelnosti s kreativitou
Pozorování: Efektivně neoddělitelné r.s. množiny A, B a jsou kreativní množiny.
Důkaz: Pro sjednocení rekurzivně spočetných množin : Mějme a neoddělitelné, ukážeme, že je produktivní. Mějme nějakou RSM , jako rekurzivně spočetnou obálku zvolíme , jako obálku zvolíme . Protože jsou neoddělitelné, funkce, která to dokazuje, vrátí prvek mimo tyto obálky - speciálně tedy v .
A je kreativní (pro B bude důkaz symetrický): úplně stejně, jen . Jako rekurzivně spočetnou obálku opět zvolíme , jako obálku zvolíme .
1-úplnost
*Def: Nechť (A,B), (C,D) jsou dvě dvojice disjunktních množin, definujeme 1-převoditelnost , pokud existuje prostá ORF h taková, že , , .
*Def: Disjunktní dvojice (A,B) je 1-úplná, pokud pro každou disjunktní (C,D) platí .
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 a , která je 1-úplná. Lze na ni tedy převést jakoukoliv jinou dvojici množin, včetně takové dvojice množin , , která je efektivně neoddělitelná (předchozí věta zaručuje existenci nějaké takové dvojice a existenci funkce , která jejich neoddělitelnost dokazuje). Platí pomocí funkce .
Nyní nechť existují nějaké množiny a , které oddělují a . Potom vezmeme vzory těchto množin (při ) a aplikujeme na ně . Tím dostaneme bod mimo tyto vzory a opětovnou aplikací získáme bod mimo a .
Dvojná věta o rekurzi
Věta: Velmi hrubě: Pro ORF f,g existují m,n takové, že , . (Pro více parametrů f,g je srazíme s-m-n větou.)
Důkaz: Dokážeme, že existují tak, že , .
Mějme . Pomocí věty o rekurzi (té poslední, co funguje v závislosti na parametrech) získáme funkci takovou, že .
Nyní si vezmeme funkci . To je funkce v jedné proměnné, takže na ni můžeme aplikovat větu o rekurzi (tentokrát tu první) a dostaneme tak, že . Tím jsme hotoví, jelikož můžeme volit jako .
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 funkci , která neoddělitelnost dokazuje) a nějakou dvojici nadefinujeme množiny a takto:
Pokud , tak , v opačném případě . Stejně tak, pokud , tak , v opačném případě .
Nyní je snadné vidět, že pokud , tak a , takže .
Co se stane v případě, kdy (a tedy )? Ukážeme, že potom - kdyby tomu totiž bylo jinak, byly by a nadmnožinami a . To znamená, že by funkce musela vracet nějaký bod mimo ně, platilo by tedy . To je ovšem spor, protože .
Případ, kdy , se dokáže úplně stejně.
Zbývá jen rozmyslet si, kdo nám zaručí existenci šikovných funkcí , 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í.