You are here: University of Vienna PHAIDRA Detail o:1328051
Title (eng)
Jan Krajíček's forcing construction and pseudo proof systems
Parallel title (deu)
Jan Krajicek's Forcingkonstruktion und Pseudobeweissysteme
Author
Jan Felix Maly
Adviser
Moritz Müller
Assessor
Moritz Müller
Abstract (deu)
Diese Arbeit behandelt eine Forcing Methode, die Jan Krajíček in dem Buch ‘Forcing with random variables and proof complexity’ 2010 vorgestellt hat und richtet sich an Leser mit grundlegenden Kentnissen in Logik und Komplexitätstheorie. Die Forcingmethode erlaubt es Modelle für verschiedene Theorien aus dem Bereich der ‘Bounded Arithemtic’ zu konstruieren. Es werden die mathematischen Grundlagen, die zum Verständis der Meth- ode notwendig sind, diskutiert, insoweit sie über den üblichen Umfang einer Einfürungsvorlesung in Logik und Komplexitätstheorie hinausgehen. Danach wird die Forcing Methode allgemein vorgestellt und anschließend an einem Beispiel vorgeführt. Desweiteren werden so genannte ‘pseudo proof systems’ behandelt, die ebenfalls von Jan Krajíček im selben Buch vorgestellt wurden. Hierbei handelt es sich um Funktionen, die sich, im Kontext der mit der Forcing Methode konstru- ierten Modelle, wie Beweissysteme verhalten, aber, im Allgemeinen, keine Beweissysteme sind. Diese ‘pseudo proof systems’ werden eingeführt und ein neues Ergebnis wird vorgestellt. Dazu werden ‘pseudo proof systems that err everywhere’ definiert. Hierbei handelt es sich um ‘pseudo proof systems’ die ausschließlich Sätze beweisen, die keine Tautologien sind. Anschließend wird bewiesen, dass solche Funktionen genau dann existieren, wenn gewisse harte Sequenzen, ‘invertible probably hard sequences’ existieren. Diese wer- den in dieser Arbeit neu eingeführt. Ihre Existens lässt sich unter bekannten komplxitätstheoritheschen Annahmen beweisen. Abschließend wird kurz die Möglichkeit diskutiert das Konzept eine ‘pseudo proof systems’ auch über den Kontext der Forcing Methode hinaus fruchtbar zu machen.
Keywords (eng)
Proof complexitybounded arithmeticpseudo proof systems
Keywords (deu)
ForcingKomplexitätstheorieLogikKrajicek
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1328051
rdau:P60550 (deu)
80 Seiten : Diagramme
Number of pages
80
Association (deu)
Members (1)
Title (eng)
Jan Krajíček's forcing construction and pseudo proof systems
Parallel title (deu)
Jan Krajicek's Forcingkonstruktion und Pseudobeweissysteme
Author
Jan Felix Maly
Abstract (deu)
Diese Arbeit behandelt eine Forcing Methode, die Jan Krajíček in dem Buch ‘Forcing with random variables and proof complexity’ 2010 vorgestellt hat und richtet sich an Leser mit grundlegenden Kentnissen in Logik und Komplexitätstheorie. Die Forcingmethode erlaubt es Modelle für verschiedene Theorien aus dem Bereich der ‘Bounded Arithemtic’ zu konstruieren. Es werden die mathematischen Grundlagen, die zum Verständis der Meth- ode notwendig sind, diskutiert, insoweit sie über den üblichen Umfang einer Einfürungsvorlesung in Logik und Komplexitätstheorie hinausgehen. Danach wird die Forcing Methode allgemein vorgestellt und anschließend an einem Beispiel vorgeführt. Desweiteren werden so genannte ‘pseudo proof systems’ behandelt, die ebenfalls von Jan Krajíček im selben Buch vorgestellt wurden. Hierbei handelt es sich um Funktionen, die sich, im Kontext der mit der Forcing Methode konstru- ierten Modelle, wie Beweissysteme verhalten, aber, im Allgemeinen, keine Beweissysteme sind. Diese ‘pseudo proof systems’ werden eingeführt und ein neues Ergebnis wird vorgestellt. Dazu werden ‘pseudo proof systems that err everywhere’ definiert. Hierbei handelt es sich um ‘pseudo proof systems’ die ausschließlich Sätze beweisen, die keine Tautologien sind. Anschließend wird bewiesen, dass solche Funktionen genau dann existieren, wenn gewisse harte Sequenzen, ‘invertible probably hard sequences’ existieren. Diese wer- den in dieser Arbeit neu eingeführt. Ihre Existens lässt sich unter bekannten komplxitätstheoritheschen Annahmen beweisen. Abschließend wird kurz die Möglichkeit diskutiert das Konzept eine ‘pseudo proof systems’ auch über den Kontext der Forcing Methode hinaus fruchtbar zu machen.
Keywords (eng)
Proof complexitybounded arithmeticpseudo proof systems
Keywords (deu)
ForcingKomplexitätstheorieLogikKrajicek
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1328052
Number of pages
80
Association (deu)