Detailansicht
Jan Krajíček's forcing construction and pseudo proof systems
Jan Felix Maly
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Moritz Müller
DOI
10.25365/thesis.43173
URN
urn:nbn:at:at-ubw:1-12718.38957.782985-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
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.
Schlagwörter
Schlagwörter
(Englisch)
Proof complexity bounded arithmetic pseudo proof systems
Schlagwörter
(Deutsch)
Forcing Komplexitätstheorie Logik Krajicek
Autor*innen
Jan Felix Maly
Haupttitel (Englisch)
Jan Krajíček's forcing construction and pseudo proof systems
Paralleltitel (Deutsch)
Jan Krajicek's Forcingkonstruktion und Pseudobeweissysteme
Publikationsjahr
2016
Umfangsangabe
80 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Moritz Müller
Klassifikation
31 Mathematik > 31.10 Mathematische Logik, Mengenlehre
AC Nummer
AC13323869
Utheses ID
38212
Studienkennzahl
UA | 066 | 821 | |