Propositional logic, complexity theory and a nontrivial hierarchy of theories of weak fragments of peano arithmetic

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 \{|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 }