# [NTIN073] - Rekurze I

<{ForumPost(poster="Davpe", timestamp=2015-02-04 13:49:39)}>
04.02.2015:  
1) Věta o nízké bázi  
2) Výběr z:   
(a) Pod 1-generickou nejsou nerekurzivní množiny  
(b) 1-generická neobsahuje nekonečnou rekurzivně spočetnou podmnožinu  
  
U 2a jsem se trochu zamotal ale bez problémů mi to uznal s tím že myšlenka je správně ale za detaily neručí. Celkově ty papíry četl docela bleskově.
<{/ForumPost}>

<{ForumPost(poster="exa", timestamp=2015-02-05 12:36:47)}>
Za sebe: dukazy obou veci jsem spis obkreslil, druhy jsem si pamatoval asi tak z 1%, nicmene znamka je spis za pochopeni a schopnost pouzit nez za topeni se v technickych drobnostech.  
  
Pridavam seznam moznych otazek co se ucit, protoze moc nikde jinde detailnejsi sylabus najit nejde, predpokladam ze ale bude zkouset jen ty "zajimavejsi".  

* - ekvivalence definice $\Pi^0_1$ trid pomoci jednokvantifikatorovy formule a jako "tridy nekonecnych vetvi binarnich stromu"  
- Izolovane prvky $\Pi^0_1$ trid jsou rekurzivni  
- Schoenfield: Kazda neprazdna $\Pi^0_1$ trida ma prvek rekurzivni v $\emptyset'$  
- Low basis theorem: Kazda neprazdna $\Pi^0_1$ trida ma Low prvek  
- Kazda neprazdna $\Pi^0_1$ trida ma skoro rekurzivni (computably dominated, s O.R. majorantou) prvek  
- definice mod(x) a wmod(x)  
- ekvivalence: $a \gg \emptyset$ <=> a je stupen 0-1 DiagonallyNonComputable funkce <=> a je stupen kompletniho rozsireni Peanovy aritmetiky  
- Arshlanovo kriterium (jediny RS stupen obsahujici DNC funkci je $\emptyset'$  
- Bairova veta o kategoriich: Uplny metricky prostor je v sobe co-meager. (coz je tosame jako "spocetny otevreny husty prunik je neprazdny", z cehoz je cca 666x lip videt vyhoda pro 1-gen forcing)  
- 1-gen mnozina: neni rekurzivni, existuje 1-gen mnozina $\lt \emptyset'$, 1-gen mnozin je co-meager ("hodne")  
- Kleene-Post: Existuji $A,B < \emptyset'$ ktere jsou T-neporovnatelne (finite extension method)  
- 1-gen mnozina neobsahuje nekonecnou RS podmnozinu a nejsou pod ni nerekurzivni r.s. mnoziny  
- Friedberg: obor hodnot skoku je horni konus halting problemu ($\forall A > \emptyset' \exists B: B'=A$)  
- Definice 1-gen pomoci $\Pi^0_1$ mnozin stringu (a ekvivalentni n-genericnost)  
- Kuriozita: Pod kazdou r.s. a nerekurzivni mnozinou je 1-gen mnozina  
- Reseni postova problemu pomoci finite injury method (existuje r.s. stupen $\emptyset < A < \emptyset'$)  
- nejakej nahled na to ze existuje i infinite injury method  
- Avoiding upper cone: Pro kazde C existuje neporovnatelne r.s. A (coz je Low Basis Theorem akorat s podminkou toho C navic)  
- Pod kazdou DNC funkci mensi nez halting problem je nejaka nerekurzivni a r.s. mnozina.

<{/ForumPost}>

<{ForumPost(poster="Davpe", timestamp=2015-02-05 16:03:36)}>
S dovolením doplním poslední přednášku;)

* Pro neprázdnou $\Pi^0_1$ třídu $A$ která je podmnožinou (0,1)-DNR existuje $x_0$    t.ž. $A \cap \{f : f(x_0) = i \} 
eq \emptyset$ pro  $i = 0,1$  
Pro neprázdnou $\Pi^0_1$ třídu $A$ která je podmnožinou (0,1)-GNR existuje $x_0$    t.ž. $A \cap \{f : f(<x_0, j>) = B(j)\  \forall j \} 
eq \emptyset$ pro lib. $B \in 2^\omega$ .

A v sešitě mám ještě náznak důkazu Posta pro dvě množiny:

* Existují r.s. množiny A, B které jsou T-neporovnatelné a  $\emptyset < A, B < \emptyset'$

<{/ForumPost}>