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.