|
|
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
|
host ::
RSS.