TIN064 Imunní a simple množiny

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Definice imunní a simple množiny

  • Def. Množina M je imunní, pokud je nekonečná a neobsahuje žádnou nekonečnou RSM. To můžeme zapsat třeba takto: $ |M| \notin \mathbb{N} \And (W_x \subseteq M \Rightarrow |W_x| \in \mathbb{N}) $.
  • Def. Množina A je simple (česky prostá), pokud je RS a její doplněk je imunní. Tedy $ A \in RSM \And \overline{A} \mbox{ je imunní} $.

Malý kvíz: Může být konečná množina A simple? Odpověď: A je jistě rekurzivní (tedy i RS). Doplněk rekurzivní množiny je však RS (dle Postovy věty), a tedy doplněk A nemůže být imunní. Ponaučení: Simple množiny nejsou až tak "simple".

Poznámka:

Abychom věděli, co vlastně budujeme, všimněme si souvislosti s důsledkem generátorů množin - nekonečné RSM obsahují nekonečné rekurzivní množiny, nekonečné imunní množiny ale neobsahují nekonečné RSM.

Je zřejmé, že imunní množina nemůže být RS (to by porušila pravidlo, že neobsahuje RSM). 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 \in M $. To je třeba mít na paměti při čtení následující konstrukce imunní množiny.
Tato část je neúplná a potřebuje rozšířit. Předposlední větě nerozumím, imunní množina přece obsahuje také konečně RSM. Nemá být místo "pokud nějaký prvek $ x \in M $" spíše "pro každý prvek $ x \in M $"?

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čnou RSM $ W_x $ lišit od této množiny alespoň v jednom prvku (který je ve $ W_x $, ale v M ne). Tedy $ \forall x (|W_x| \notin \mathbb{N}) \Rightarrow \exists y \in W_x: y \notin M $.

Množinu M a její doplněk budeme konstruovat postupně následujícím postupem: 

Volné := $ \mathbb{N} $; M:=$ \empty $; $ \overline{M} $:=$ \empty $;
for x:= 0 to $ \infty $ do {
  odeber z Volné nějaký prvek q
  přidej q do M
  if ($ W_x\, $ nekonečná){
    nechť $ y \in W_x\, \cap $ Volné
    odeber y z Volné a přidej ho do $ \overline{M} $
  }
}

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 $ W_x\, $ nekonečná. To je totiž neefektivní krok (prostě to nelze zjistit, nejste-li trojjediný...). Zkusíme tedy navrhnout jinou, efektivní konstrukci.pozn1 Tentokrát budeme konstruovat rovnou simple množinu A a jako vedlejší produkt získáme imunní množinu $ \overline{A} $.

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 $ W_x $ "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 $ W_x $ 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) $ Q(x,y) \Leftrightarrow y \in W_x \And y > 2x $. Vidíme, že to je RSP a podle věty o selektoru víme, že selektor na RSP je ČRF $ \varphi $. Hledaná simple množina je pak $ A=rng(\varphi) $. Jak to?

vysvětlení

Pokud $ \varphi(x)\downarrow $, tak vrátí nejmenší y takové, že $ y \in W_x \And y > 2x $. Pokud takové y neexistuje, tak $ \varphi(x)\uparrow $ a množina $ W_x $ je zaručeně konečná. Množina A tedy sestává z takových y, která jsme muselipozn2 "odebrat z $ \overline{A} $", aby $ \overline{A} $ 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 kouknout 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:=$ \empty $; $ \overline{A} $:=$ \mathbb{N} $;
for x:= 0 to $ \infty $ do {
  if ($ \exists y \in W_x: y > 2x $){ // tedy pokud $ \varphi(x)\downarrow $
    nechť $ y_0 $ je nejmenší takové y // tedy $ y_0 $:= $ \varphi(x) $
    if ($ y_0 \in \overline{A} $) přesuň $ y_0 $ z $ \overline{A} $ 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 $ \overline{A} $ je imunní).

  • A je RSM. Platí podle věty, že obor hodnot ČRF je RSM.
  • $ \overline{A} $ je nekonečná. Při konstrukci dáváme do A právě ty hodnoty y, pro které existuje x, že $ y=\varphi(x) $. Jde o to, jestli jich tam nedáváme "moc". Platí, že $ \varphi(x) > 2x $ (pokud $ \varphi(x)\downarrow $). 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: $ \varphi(0),..., \varphi(x-1) $. Nutně tedy muselo zbýt alespoň x + 1 čísel, které jsme do A nezařadili (tato čísla tedy zůstala v $ \overline{A} $).
  • $ \overline{A} $ neobsahuje žádnou nekonečnou RSM. Mějme libovolnou nekonečnou RSM $ W_x $, pak v ní jistě musí existovat y > 2x. No a jedno takové (to nejmenší) y jsme zařadili do A. Dokonce platí $ W_x \subseteq \overline{A} \Rightarrow W_x \subseteq \{0,...,2x\} $.

$ \Box $

* ^ ad pozn1  Ve skriptech Ladislava Strojila se na straně 9 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.

* ^ ad pozn2  Popravdě jsme mnoho takových y vlastně odebrat ani nemuseli, protože jim příslušná množina $ W_x $ třeba byla konečná a pouze obsahovala prvek větší než 2x.

Matijasevičova věta

Definice: Predikát P je diofantický, existují-li dva polynomy $ p_1, p_2 $ a platí-li $ \forall \vec x: P(\vec x) \Leftrightarrow \exists \vec y: p_1(\vec x, \vec y) = p_2(\vec x, \vec y) $. Tedy predikát rozhoduje, jestli se v daném bodě potkají nějaké dva polynomy (s celočíselnými parametry). Rozhodnout, zda takový predikát (algoritmus) existuje, byl dokonce 10. Hilbertův problém.

Věta: Predikát P je diofantický, právě když je rekurzivně spočetný.

Důkaz: Dvě implikace.

  • Diofantický P je RSP. Částečně rekurzivní funkce, která konverguje právě nad kladnými instancemi P, pro vstup $ \vec x $ postupně porovnává hodnoty polynomů p_1 a p_2 pro všechny možné $ \vec y $.
  • Těžký, neříká se. Podle Wikipedie http://en.wikipedia.org/wiki/Matiyasevich%27s_theorem#Matiyasevich.27s_theorem se zběsilým trikem s Fibonacciho čísly ukáže, že diofantické rovnice mohou exponenciálně růst a tak asi pokryjí celý rozsah RSP, což podle nějaké jiné věty stačí.

Důsledek: P není rekurzivní, tedy 10. Hilbertův problém má zápornou odpověď - neexistuje algoritmus, který umí rozhodnout o řešení všech diofantických rovnic.

(XXX: Není jasné, proč se tahle věta říká právě teď.)

Citováno z „http://wiki.matfyz.cz/index.php?title=TIN064_Imunní_a_simple_množiny&oldid=21509“