|
|
Models of bounded arithmetic
Narusevych, Mykyta ; Krajíček, Jan (vedoucí práce) ; Šaroch, Jan (oponent)
Práce zkoumá vzájemné vztahy různých verzí zásuvkového principu (tež princip hol- ubníku) nad teorií omezené aritmetiky T1 2 (R). Základní dvě varianty jsou obyčejný PHPn+1 n (R), formalizující že R není grafem injektivní funkce z [n + 1] do [n], a jeho slabší verze, WPHP2m m (S), formalizující že S není grafem injektivní funkce z [2m] do [m]. Je známo, že teorie T1 2 (R) nedokazuje PHPn+1 n (R). Práce zobecňuje známe metody a ukazuje, že teorie T1 2 (R) plus ∀mWPHP2m m (□p 1(R)) nedokazuje PHPn+1 n (R) (kde □p 1(R) označuje relace polynomiálně definovatelné z R). Plyne to z jíž známých faktů, náš důkaz je ale elementárnější a umožňuje nám dokázat částečný výsledek směrem k otevřenému problému, který zmínil M. Ajtai (1990). 1
|
|
|
Strongly compact cardinals and SCH
Narusevych, Mykyta ; Šaroch, Jan (vedoucí práce) ; Krajíček, Jan (oponent)
Práce je věnována kardinální aritmetice. Prvním krokem je formulace Hypotézy sin- gulárních kardinálů (SCH), jež zjednodušuje kardinální mocnění singulárních kardinálů. Dále zavádíme pojem stacionární množiny a uzavřené neomezené podmnožiny ordinálního čísla. Hlavním cílem je pak důkaz Silverovy věty a jejího důsledku pro SCH, který říká, že SCH platí pro všechny kardinály, pokud platí pro singulární kardinály se spočetnou kofinalitou. V poslední části zavádíme pojem silně kompaktního kardinálu a ukazujeme několik užitečných vlastnosti takových kardinálů. Nakonec dokážeme Solovayovu větu, jež tvrdí, že SCH platí všude nad silně kompaktním kardinálem. 1
|
host ::
RSS.