TIN065 Prednáška 10
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
|
Na tejto prednáške se si povedali niečo o 1generických množinách a o aritmetickom forcingu.
Aritmetický forcing si môžeme predstaviť, ako hľadanie niečoho, čoho je v topologickom zmysle "hodně" alebo čo je topologicky typické vzhľadom k nejakej triede podmienok. Ide o akýsi skoro ekvivalent analýznického skoro všade.
Historická vsuvka[editovat | editovat zdroj]
Z teórií množín bol dlho problém, či množina reálnych čísel je svojou mohutnosťou hneď po prirodzených číslach alebo je medzi nimi ešte nejaká iná. Najprv Gödel zistil, že sa to nedá vyvrátiť a potom prišiel Cohen a zistil, že sa to nedá ani dokázať. Metóda, ktorú v dôkaze použil sa nazýva forcing.
Cohenov dôkaz bol komplikovaný a na konci boli chyby. Prvá reakcia bola, že je zlý. Keď sa chyby opravili, tak bola všeobecná reakcia, že je zbytočne zložitý a nemá prílišné praktické použitie. Dôkaz však bol s obľubou skúmaný mladými matematikmi a tí zistili, že ide iba o zobecnenie Bairovej vety o kategóriách.
Cohen použil metódu zvanú množinový forcing. V teórií rekurzie bol ale už skôr známy aritmetický forcing.
Aritmetický forcing a generičnosť[editovat | editovat zdroj]
Každú množinu $ X $ môžeme vyjadriť jej charakteristickou funkciou (teda postupnosťou núl a jedničiek) a tieto množiny tvoria metrický priestor $ 2^{\omega} $, kde metrika je $ \rho(f, g) = 2^{-y_0} $ pre rôzne $ f $ a $ g $ a nulová pre rovnaké. $ y_0 $ je najmenšíe také $ y $, kde $ f(y)\neq g(y) $.
Vezmime si ČRFál $ \Phi $ a k nemu triedu množín $ \{ X: \Phi(X)(x_0)\!\!\downarrow\} $. Na $ x_0 $ nám teraz príliš nezáleží, tak nech to bude nula. Na črfál sa budeme pozerať ako na program, ktorého vstupom je len množina.
Táto trieda je otvorená - s každým bodom tam leží jeho okolie z úplného metrického systému $ 2^{\omega} $. To, že ČRFál konverguje znamená, že konverguje vďaka konečne veľa prvkom v tejto množine, teda vďaka konečnému začiatku $ \delta $. Ak teda ČRFál $ \Phi $ konverguje pre nejaké $ \delta \leq X $, tak pre všetky $ (\gamma \geq \delta) \Phi(\gamma)(x_0)\!\!\downarrow $. Takže konverguje pre všetky množiny s rovnakým konečným začiatkom.
Naopak trieda množín $ \{X: \Phi(X)(x_0)\!\!\uparrow\} $ je uzavretá, neexistuje začiatok $ X $, ktorý rozhodne o patričnosti k triede. Pre ľubovoľnú rekurzívnu množinu $ B $ urobíme $ \Phi(X)(\emptyset)\!\!\downarrow \iff X \not= B $. $ \Phi $ diverguje iba na izolovanom bode. Žiadny retiazok nezaručuje, že od neho to bude divergovať. Stále môže prísť prvok, ktorým sa vstup $ \Phi $ bude líšiť od $ B $ a $ \Phi $ bude konvergovať. Žiadne okolie nerozhodne o divergencii. $ \Phi $ je program, ktorý vlastne iba hľadá najmenšie $ z $, kde by sa $ B $ líšilo od $ X $.
Program, ktorý by zastavil len na množine $ B $ sa zostrojiť nedá. Ak zastavuje na množine $ B $, tak skontroloval iba konečne veľa prvkov a preto pre každú množinu, ktorá by bola na týchto prvkoch s $ B $ rovnaká, by program zastavil (to je práve tvrdenie o otvorenosti definičného oboru $ \Phi $).
Triedy množín $ \mathcal{A}=\{X:\Phi(X)(x_0)\uparrow\} $ sú topologicky uzavreté. Ale vnútro takejto triedy (označované $ \mbox{Int }\mathcal{A} $) je v poriadku, tj. body ktoré sú vnútri, sú tam s okolím. Vnútri triedy $ \mathcal{A} $ závisí divergenicia $ \Phi $ len na konečnom začiatku vstupnej množiny.
Fakt: Množín (bodov) na hranici je topologicky málo (množina prvej kategórie).
Idea generickosti je konečná aproximácia pravdy (vlastnosti, splnenie podmienky), tj. rozhodnutie (prípadne vynútenie - odtiaľ forcing) konečným začiatkom. Preto ich definujeme a vyberáme od nevhodných.
Vynútiť splnenie podmienky len konečným začiatkom množiny nejde vždy, ale množín, kde to nefunguje je topologicky málo.
Def.: $ A $ je 1-generická ak $ (\forall e) (\exists \alpha_e \leq A) [(\Phi_e(\alpha_e)(e)\!\!\downarrow) \lor ((\forall \gamma \geq \alpha_e) \Phi_e(\gamma)(e)\!\!\uparrow)] $
Poznámka: Pre $ (\forall \gamma \geq \alpha_e) \Phi_e(\gamma)(e)\!\!\uparrow $ hovoríme, že silno diverguje. $ \Phi_e(\alpha_e)(e)\!\!\downarrow $ znamená $ (\forall \gamma\geq\alpha_e)\Phi(\gamma)(e)\!\!\downarrow $. $ \alpha_e $ robí aritmetický forcing, že núti od tohoto bodu všetky stringy s rovnakým počiatkom buď divergovať, alebo konvergovať.
1-generické množiny sa pekne správajú a sú typické (a v topologickom zmysle je ich väčšina).
Pozorovanie: Žiadna rekurzívna množina nie je 1-generická.
Podmienky $ \Phi(X)(x_0)\downarrow $ a $ \Phi(X)(x_0)\uparrow $ sú jednokvantifikátorové vlastnosti (existuje počet krokov, pre všetky počty krokov). Z toho vznikol názov 1-generické. Dajú sa zobecniť na 2-generické, n-generické, prípadne ariteticky generické, ale týmto smerom sa nebudeme uberať.
Veta: Existuje 1-generická $ A \leq_T \emptyset' $
Dôkaz: Indukciou, prvý krok $ \alpha_0 = \emptyset $. Následne budeme generovať $ \alpha_0 \leq \alpha_1 \leq \alpha_2 \leq \cdots $, pre $ \Phi_1, \Phi_2, \cdots $
Máme $ \alpha_e \in 2^{\leq \omega} $ konečný retiazok, pre $ \Phi_e $. Hľadáme pre $ \Phi_{e+1} $, otázkou
$ (\exists \gamma \geq \alpha_e) (\Phi_{e+1}(\gamma)(e+1)\!\!\downarrow) $
čo je ekvivalentné s $ (\exists \gamma \geq \alpha_e) (\exists s) (\Phi_{e+1,s}(\gamma)(e+1)\!\!\downarrow) $, vnútri máme rekurzívny predikát, preto táto otázka je $ \Sigma_1^0 $, čo je $ \leq_T \emptyset' $
Halting problém nám odpovie. Ak odpovie áno, tak dosadíme prvý taký retiazok $ \alpha_{e+1} = \gamma $, za ním už všetky budú konvergovať. Ak nie, tak $ \alpha_{e+1} = \alpha_e $ a vieme, že forcuje silnú divergenciu.
Takto si vygenerujeme postupne celé $ A $, pomocou $ \emptyset' $. $ A = \cup_e \alpha_e $.
Tejto metóde sa hovorí Cohenov forcing alebo tiež metóda konečného predĺženia (finite extension). Máme spočetne mnoho podmienok ($ \forall e $) a tie sa snažíme vyriešiť tak, aby po splnení e-tej podmienky sme mali dosť miesta na riešenie ďalších.
