Title: Model constructions for bounded arithmetic Author: Michal Garlík Abstract: We study constructions of models of bounded arithmetic theories. Us- ing basic techniques of model theory we give a new proof of Ajtai's completeness theorem for nonstandard finite structures. Working in the framework of restricted reduced powers (a generalization of the ultrapower construction) we devise two methods of constructing models of bounded arithmetic. The first one gives a new proof of Buss's witnessing theorem. Using the second method we show that the theory R1 2 is stronger than its variant strictR1 2 under a plausible computational assumption (the existence of a strong enough one-way permutation), and that the theory PV1 + Σb 1(PV ) − LLIND is stronger than PV1 + strictΣb 1(PV ) − LLIND under the same assumption. Considering relativized theories, we show that R1 2(α) is stronger than strictR1 2(α) (unconditionally). 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:351010 |
| Date | January 2015 |
| Creators | Garlík, Michal |
| Contributors | Krajíček, Jan, Buss, Samuel, Thapen, Neil |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0019 seconds