{{Template:TIN064 Skripta}}
== Definice imunní a simple množiny ==
* '''Def.''' Množina M je '''imunní''', pokud je nekonečná a neobsahuje žádnou RSM. To můžeme zapsat třeba takto: <math>|M| \notin \mathbb{N} \And (W_x \subseteq M \Rightarrow |W_x| \in \mathbb{N})</math>.
* '''Def.''' Množina A je '''simple''' (česky prostá), pokud je RS a její doplněk je simple. Tedy <math>A \in RSM \And \overline{A} \mbox{ je simple}</math>.
=== Poznámka: ===
Je zřejmé, že imunní množina nemůže být RS (jinak by obsahovala sama sebe), a takové množiny bývají "hodně divoké". Pro žádnou imunní množinu M nelze tedy sestrojit program, který by po konečném počtu kroků odpověděl ano, pokud nějaký prvek x je v M. To je třeba mít na paměti při čtení následující konstrukce imunní množiny.
Máme-li naopak množinu A, která je simple, pak pro ni musí takový program existovat (neboť A je RSM). Nepodaří se ale sestrojit program, který by množinu A rozhodoval, tedy po konečném počtu kroků odpověděl ano či ne na otázku, zda nějaký prvek je v A. Simple množina A totiž nemůže být rekurzivní - kdyby byla, tak je i její doplněk rekurzivní, což je z definice vyloučené.
Zbývá ovšem zodpovědět otázku, zda vůbec nějaké imunní a simple množiny existují. Správně tušíte, že ano, jinak by se o nich neučilo... no, i když ono se učí leccos, že.
== Existence imunní a simple množiny ==
=== Neefektivní konstrukce imunní množiny ===
Má-li být M imunní musí se pro každou nekonečné RSM <math>W_x</math> lišit od této množiny alespoň v jednom prvku (který je ve <math>W_x</math>, ale v M ne). Tedy <math>\forall x (|W_x| \notin \mathbb{N}) \Rightarrow \exists y \in W_x: y \notin M</math>.
Množinu M a její doplněk budeme konstruovat postupně následujícím postupem:
Volné := <math>\mathbb{N}</math>; M:=<math>\empty</math>; <math>\overline{M}</math>:=<math>\empty</math>;
for x:= 0 to <math>\infty</math> do {
odeber z Volné nějaký prvek q
přidej q do M
if (<math>W_x\,</math> nekonečná){
nechť <math>y \in W_x\, \cap</math> Volné
odeber y z Volné a přidej ho do <math>\overline{M}</math>
}
}
Nenechte se zmást tím, že je postup zapsán jako program — žádný takový totiž neexistuje. Problémem je zjišťování, zda je <math>W_x\,</math> nekonečná. To je totiž neefektivní krok (prostě to nelze zjistit, nejste-li trojjediný...). Zkusíme tedy navrhnout jinou, efektivní konstrukci.{{Odkaz na poznámku|pozn1}} Tentokrát budeme konstruovat rovnou simple množinu A a jako vedlejší produkt získáme imunní množinu <math>\overline{A}</math>.
=== Efektivní konstrukce simple množiny ===
V doplňku A nesmí zůstat žádná nekonečná RSM, ale to, zda je množina nekonečná zjistit neumíme. Budeme tedy zjišťovat pouze, jestli je množina <math>W_x</math> "dostatečně velká" (podezřelá z nekonečnosti) a pokud ano, tak z ní vezmeme jeden prvek a ten přidáme do A. Množinu <math>W_x</math> budeme považovat za dostatečně velkou, pokud bude obsahovat prvek větší než 2x. A to už umíme zjistit algoritmicky (efektivně). Pokud množina neobsahuje takový prvek, tak náš výpočet samozřejmě nikdy neskončí, ale to nám nevadí — my konstruujeme simple množinu A a potřebujeme, aby se výpočet zastavil pro prvky, které do ní patří, což bude splněno.
==== vlastní konstrukce ====
Mějme predikát (neboli relaci) <math>Q(x,y) \Leftrightarrow y \in W_x \And y > 2x</math>. Vidíme, že to je RSP a podle [[TIN064 Věta o selektoru|věty o selektoru]] víme, že selektor na RSP je ČRF <math>\varphi</math>. Hledaná simple množina je pak <math>A=rng(\varphi)</math>. Jak to?
==== vysvětlení ====
Pokud <math>\varphi(x)\downarrow</math>, tak vrátí nejmenší y takové, že <math>y \in W_x \And y > 2x</math>. Pokud takové y neexistuje, tak <math>\varphi(x)\uparrow</math> a množina <math>W_x</math> je zaručeně konečná. Množina A tedy sestává z takových y, která jsme museli{{Odkaz na poznámku|pozn2}} "odbrat z <math>\overline{A}</math>", aby <math>\overline{A}</math> neobsahovalo žádnou nekonečnou RSM.
Jestli vám to je už jasné, tak rovnou přejděte k důkazu. V opačném případě se můžete zkusit na chvíli kouknou na následující pseudoalgoritmus, ale POZOR: pak na něj radši zapomeňte, protože efektivní konstrukce takto dokazovat nelze (byť je výsledná množina A stejná). K tomu je opravdu potřeba věta o selektoru (která zajistí, že se nezasekneme u prvního x, pro které podmínka neplatí).
A:=<math>\empty</math>; <math>\overline{A}</math>:=<math>\mathbb{N}</math>;
for x:= 0 to <math>\infty</math> do {
if (<math>\exists y \in W_x: y > 2x</math>){ ''// tedy pokud <math>\varphi(x)\downarrow</math>''
nechť <math>y_0</math> je nejmenší takové y ''// tedy <math>y_0</math>:= <math>\varphi(x)</math>''
if (<math>y_0 \in \overline{A}</math>) přesuň <math>y_0</math> z <math>\overline{A}</math> do A
}
}
==== důkaz ====
V důkazu můžeme postupovat podle definice simple množiny, tedy ověříme následující 3 body (z nichž poslední dva říkají, že <math>\overline{A}</math> je imunní).
* '''A je RSM.''' Platí podle věty, že [[TIN064 Věta o selektoru#Obor hodnot ČRF je RSM|obor hodnot ČRF je RSM]].
* '''<math>\overline{A}</math> je nekonečná.''' Při konstrukci dáváme do A právě ty hodnoty y, pro které existuje x, že <math>y=\varphi(x)</math>. Jde o to, jestli jich tam nedáváme "moc". Platí, že <math>\varphi(x) > 2x</math> (pokud <math>\varphi(x)\downarrow</math>). Mějme x libovolné. Z množiny {0,1,...,2x} jsme mohli do A zařadit nejvýše x čísel, a to některé z: <math>\varphi(0),..., \varphi(x-1)</math>. Nutně tedy muselo zbýt alespoň x + 1 čísel, které jsme do A nezařadili (tato čísla tedy zůstala v <math>\overline{A}</math>).
* '''<math>\overline{A}</math> neobsahuje žádnou nekonečnou RSM.''' Mějme libovolnou nekonečnou RSM <math>W_x</math>, pak v ní jistě musí existovat y > 2x. No a jedno takové (to nejmenší) y jsme zařadili do A. Dokonce platí <math>W_x \subseteq \overline{A} \Rightarrow W_x \subseteq \{0,...,2x\}</math>.
<math>\Box</math>
----
{{Poznámka|pozn1| Ve [[TIN06 Skripta Ladislava Strojila|skriptech Ladislava Strojila]] se na straně 9 se píše o efektivní konstrukci v důkazu Lemma 5: ''Existence imunní množiny''. Osobně v tom nemám příliš jasno: Jedná se o efektivní konstrukci imunní množiny? Co to přesně pak znamená efektivní konstrukce? Víme přece, že imunní množina není rekurzivně spočetná, tak jak by mohla existovat její efektivní konstrukce? Nejspíš se tím myslí efektivní konstrukce simple množiny (to už jde), ale pak je to formulováno dost zavádějícím způsobem, kterému se zde snažím vyhnout.}}
{{Poznámka|pozn2| Popravdě jsme mnoho takových y vlastně odebrat ani nemuseli, protože jim příslušná množina <math>W_x</math> třeba byla konečná a pouze obsahovala prvek větší než 2x.}}
