[NTIN073] - Rekurze I

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ě.

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.

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'$