od exa » 5. 2. 2015 12:36
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".
[list]
- ekvivalence definice [latex]\Pi^0_1[/latex] trid pomoci jednokvantifikatorovy formule a jako "tridy nekonecnych vetvi binarnich stromu"
- Izolovane prvky [latex]\Pi^0_1[/latex] trid jsou rekurzivni
- Schoenfield: Kazda neprazdna [latex]\Pi^0_1[/latex] trida ma prvek rekurzivni v [latex]\emptyset'[/latex]
- Low basis theorem: Kazda neprazdna [latex]\Pi^0_1[/latex] trida ma Low prvek
- Kazda neprazdna [latex]\Pi^0_1[/latex] trida ma skoro rekurzivni (computably dominated, s O.R. majorantou) prvek
- definice mod(x) a wmod(x)
- ekvivalence: [latex]a \gg \emptyset[/latex] <=> a je stupen 0-1 DiagonallyNonComputable funkce <=> a je stupen kompletniho rozsireni Peanovy aritmetiky
- Arshlanovo kriterium (jediny RS stupen obsahujici DNC funkci je [latex]\emptyset'[/latex]
- 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 [latex]\lt \emptyset'[/latex], 1-gen mnozin je co-meager ("hodne")
- Kleene-Post: Existuji [latex]A,B < \emptyset'[/latex] 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 ([latex]\forall A > \emptyset' \exists B: B'=A[/latex])
- Definice 1-gen pomoci [latex]\Pi^0_1[/latex] 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 [latex]\emptyset < A < \emptyset'[/latex])
- 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.
[/list]