|
|
Teorie a algebry formulí
Garlík, Michal ; Mlček, Josef (vedoucí práce) ; Glivický, Petr (oponent)
V předložené práci studujeme teorie prvého řádu a jejich Lindenbaumovy algebry zkoumáním vlastností řetězu BnT n<ω, nazvaného B-řetěz, kde BnT je podalgebra Lindenbaumovy algebry daná formulemi s nejvýše n volnými proměnnými. Obohatíme strukturu Lindenbaumovy algebry, abychom zachytili rozdíly mezi teoriemi, jejichž B-řetězy jsou člen po členu izomorfní. Podáme několik příkladů teorií a spočítáme jejich B-řetězy. Zkonstruujeme model Robin- sonovy aritmetiky s n-tou algebrou definovatelných množin izomorfní kartézskému součinu spočetné atomární saturované Booleovy algebry a spočetné bezatomární Booleovy algebry. 1
|
|
|
Model constructions for bounded arithmetic
Garlík, Michal ; Krajíček, Jan (vedoucí práce) ; Buss, Samuel (oponent) ; Thapen, Neil (oponent)
Název práce: Konstrukce modelů omezené aritmetiky Autor: Michal Garlík Abstrakt: Studujeme konstrukce modelů teorií omezené aritmetiky. Pomocí základních technik teorie modelů podáme nový důkaz Ajtaiovy věty o úplnosti pro nestandardně konečné struktury. Za použití omezené redukované mocniny (zobecnění ultraproduktu) navrhneme dvě nové metody konstrukce modelů ome- zené aritmetiky. První dá nový důkaz Bussovy dosvědčující věty. Druhou metodou ukážeme, že teorie R1 2 je silnější než její varianta strictR1 2 za věrohodného výpo- četně-složitostního předpokladu (existence dostatečně silné jednosměrné permu- tace) a že za stejného předpokladu je teorie PV1 + Σb 1(PV ) − LLIND silnější než PV1 + strictΣb 1(PV ) − LLIND. Pro relativizované teorie dokážeme, že R1 2(α) je silnější strictR1 2(α) (bez dodatečného předpokladu). 1
|
|
|
Model constructions for bounded arithmetic
Garlík, Michal ; Krajíček, Jan (vedoucí práce) ; Buss, Samuel (oponent) ; Thapen, Neil (oponent)
Název práce: Konstrukce modelů omezené aritmetiky Autor: Michal Garlík Abstrakt: Studujeme konstrukce modelů teorií omezené aritmetiky. Pomocí základních technik teorie modelů podáme nový důkaz Ajtaiovy věty o úplnosti pro nestandardně konečné struktury. Za použití omezené redukované mocniny (zobecnění ultraproduktu) navrhneme dvě nové metody konstrukce modelů ome- zené aritmetiky. První dá nový důkaz Bussovy dosvědčující věty. Druhou metodou ukážeme, že teorie R1 2 je silnější než její varianta strictR1 2 za věrohodného výpo- četně-složitostního předpokladu (existence dostatečně silné jednosměrné permu- tace) a že za stejného předpokladu je teorie PV1 + Σb 1(PV ) − LLIND silnější než PV1 + strictΣb 1(PV ) − LLIND. Pro relativizované teorie dokážeme, že R1 2(α) je silnější strictR1 2(α) (bez dodatečného předpokladu). 1
|
|
|
Teorie a algebry formulí
Garlík, Michal ; Mlček, Josef (vedoucí práce) ; Glivický, Petr (oponent)
V předložené práci studujeme teorie prvého řádu a jejich Lindenbaumovy algebry zkoumáním vlastností řetězu BnT n<ω, nazvaného B-řetěz, kde BnT je podalgebra Lindenbaumovy algebry daná formulemi s nejvýše n volnými proměnnými. Obohatíme strukturu Lindenbaumovy algebry, abychom zachytili rozdíly mezi teoriemi, jejichž B-řetězy jsou člen po členu izomorfní. Podáme několik příkladů teorií a spočítáme jejich B-řetězy. Zkonstruujeme model Robin- sonovy aritmetiky s n-tou algebrou definovatelných množin izomorfní kartézskému součinu spočetné atomární saturované Booleovy algebry a spočetné bezatomární Booleovy algebry. 1
|
|
| |
host ::
RSS.