Detailansicht
Propositional logic, complexity theory and a nontrivial hierarchy of theories of weak fragments of peano arithmetic
Christoph Schöller
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Sy-David Friedman
DOI
10.25365/thesis.15067
URN
urn:nbn:at:at-ubw:1-29769.06719.421463-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit betrachte ich einige Arbeiten von Paris, Wilky [key-1] und Ajati [key-3, key-4] welche einen Zusammenhang zwischen Komplexitäts- und Beweistheorie herstellen.
J. Paris und A. Wilkie [key-1] betrachteten die Fragen ob jede \Delta_{0}- Teilmenge A von \mathbb{N} auch eine \Delta_{0} definierbare Zählfunktion \{<n,m>|m=|A\cap n|\} besitzt. Eine damit eng verwanndte Fragestellung ist, ob das Schubfachprinzip PHP in einer schwachen Teiltheorie I\Delta_{0} der Peano Arithmetik bewiesen werden kann. I\Delta_{0} umfasst die selben Axiome wie die Peano Arithmetik. Das Axiomenschema der Induktion ist jedoch nur für beschränkte Formeln gegeben. Paris und Wilky konnten mithilfe der Forcing-Technik die Konsistenz von I\exists_{1}(F)+\exists xF:x\mapsto x-1 zeigen. Weiters konnten sie unter Verwendung der Cook-Reckhov Vermutung, die Konsistenz von I\Delta_{0}(F)+\exists xF:x\mapsto x-1 zeigen. Die Cook-Reckhov Vermutung besagt, dass ein Beweis der aussagenlogischen Form PHP_{n} von PHP ”schwer” ist. Dieser zweite Beweis benutzt einen Zusammenhang zwischen I\Delta_{0} und Frege Systemen.
Ajtai [key-3] verband die Verwendung der Forcing-Technik und dieses Zusammenhangs um die Konsistenz von I\Delta_{0}(F)+\exists xF:x\mapsto x-1 , ohne der Verwendung der Cook-Reckhov Vermutung, zu zeigen. Dazu nahm er an, dass in einem nicht-standard Modell \mathcal{M} von I\Delta_{0} ein ”einfacher” Beweis von PHP_{n} für ein n existiert. Dieses \mathcal{M} beschränkte er auf die Substruktur M_{n}=\mathcal{M}\upharpoonright n , welche er dann durch Forcing zu einem M[G] erweiterte in welchem PHP auf natürliche Weise nicht wahr sein kann. Eine kombinatorische Überlegung zeigt, dass in M[G] aber das Axiomenschema der vollständigen Induktion bis n wahr ist. Damit kann man nun den ”einfachen” Beweis von PHP_{n} Schritt für Schritt prüfen, was zu einem Widerspruch führt.
Später [key-4] verallgemeinerte Ajtai diese Art der Beweisführung, um zu zeigen, dass PHP\Delta_{0}\not\vdash PAR , wobei PHP\Delta_{0}=I\Delta_{0}\cup PHP und PAR folgende Aussage ist: Keine Menge mit einer ungeraden Anzahl von Elementen kann in Teilmengen mit genau zwei Elementen partitioniert werden. PAR kann weiter zum ”module p Counting Principle” CP_{p} verallgemeinert werden [key-4]. Schlussendlich zeigte Ajtai für alle Primzahlen p\neq q , dass die CP_{p} paarweise unabhängig sind.
Als Konsequenz dieser Erkenntnisse bekommen wir eine Hierarchie von schwachen Theorien der Peano Arithmetik:
I\exists_{1}\subset I\Delta_{0}\subset PHP\Delta_{0}\subset CP_{p}\Delta_{0}\mbox{ für alle Primzahlen }p
Schlagwörter
Schlagwörter
(Deutsch)
Aussagenlogik Beschränkte Arithmetik Forcing Komplexitätstheorie
Autor*innen
Christoph Schöller
Haupttitel (Englisch)
Propositional logic, complexity theory and a nontrivial hierarchy of theories of weak fragments of peano arithmetic
Publikationsjahr
2011
Umfangsangabe
55 S.
Sprache
Englisch
Beurteiler*in
Sy-David Friedman
Klassifikation
31 Mathematik > 31.10 Mathematische Logik, Mengenlehre
AC Nummer
AC08705042
Utheses ID
13521
Studienkennzahl
UA | 405 | | |