TU Darmstadt / ULB / TUbiblio

Proof interpretations: theoretical and practical aspects

Gaspar, Jaime (2011)
Proof interpretations: theoretical and practical aspects.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

We study theoretical and practical aspects of proof theoretic tools called proof interpretations. (1) Theoretical contributions. (1.1) Completeness and omega-rule. Using a proof interpretation, we prove that Peano arithmetic with the omega-rule is a complete theory. (1.2) Proof interpretations with truth. Proof interpretations without truth give information about the interpreted formula, not the original formula. We give three heuristics on hardwiring truth and apply them to several proof interpretations. (1.3) Copies of classical logic in intuitionistic logic. The usual proof interpretations embedding classical logic in intuitionistic logic give the same copy of classical logic, suggesting uniqueness. We present three different copies. (2) Practical contributions. (2.1) "Finitary" infinite pigeonhole principles. Terence Tao studied finitisations of statements in analysis. We take a logic view at Tao's finitisations through the lenses of proof interpretations and reverse mathematics. (2.2) Proof mining Hillam's theorem. Hillam's theorem characterises the convergence of fixed point iterations. We proof mine it, getting a "finitary rate of convergence" of the fixed point iteration.

Typ des Eintrags: Dissertation
Erschienen: 2011
Autor(en): Gaspar, Jaime
Art des Eintrags: Erstveröffentlichung
Titel: Proof interpretations: theoretical and practical aspects
Sprache: Englisch
Referenten: Kohlenbach, Prof. Dr. Ulrich ; Oliva, Reader Dr. Paulo ; Streicher, Prof. Dr. Thomas
Publikationsjahr: 21 Dezember 2011
Datum der mündlichen Prüfung: 6 Dezember 2011
URL / URN: urn:nbn:de:tuda-tuprints-28518
Kurzbeschreibung (Abstract):

We study theoretical and practical aspects of proof theoretic tools called proof interpretations. (1) Theoretical contributions. (1.1) Completeness and omega-rule. Using a proof interpretation, we prove that Peano arithmetic with the omega-rule is a complete theory. (1.2) Proof interpretations with truth. Proof interpretations without truth give information about the interpreted formula, not the original formula. We give three heuristics on hardwiring truth and apply them to several proof interpretations. (1.3) Copies of classical logic in intuitionistic logic. The usual proof interpretations embedding classical logic in intuitionistic logic give the same copy of classical logic, suggesting uniqueness. We present three different copies. (2) Practical contributions. (2.1) "Finitary" infinite pigeonhole principles. Terence Tao studied finitisations of statements in analysis. We take a logic view at Tao's finitisations through the lenses of proof interpretations and reverse mathematics. (2.2) Proof mining Hillam's theorem. Hillam's theorem characterises the convergence of fixed point iterations. We proof mine it, getting a "finitary rate of convergence" of the fixed point iteration.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Wir untersuchen theoretische und praktische Aspekte von Beweisinterpretationen. (1) Theoretische Ergebnisse. (1.1) Vollständigkeit und Omega-Regel. Mit Hilfe einer Beweisinterpretation zeigen wir, dass die Peano-Arithmetik mit der Omega-Regel eine vollständige Theorie ist. (1.2) Beweisinterpretationen mit Wahrheitsprädikat. Beweisinterpretationen ohne Wahrheitsprädikat geben Informationen über die interpretierte Formel und nicht mehr über die ursprüngliche Formel. Wir präsentieren drei Heuristiken, um Wahrheitsprädikate zu Beweisinterpretationen hinzuzufügen, und geben einige Beispiele. (1.3) Kopien von klassischer Logik in intuitionistischer Logik. Die üblichen Einbettungen von klassischer Logik in intuitionistische Logik mit Hilfe von Beweisinterpretationen erzeugen alle die gleiche Kopie der klassischen Logik. Dies deutet darauf hin, dass diese Kopie eindeutig sein könnte. Wir zeigen, dass dies nicht der Fall ist und präsentieren drei verschiedene Kopien. (2) Angewandte Ergebnisse. (2.1) "Finitisierungen" des unendlichen Schubfachprinzips. Terence Tao untersucht Finitisierungen von Sätzen der Analysis. Wir betrachten Taos Ergebnisse aus dem Blickwinkel der Beweisinterpretationen und reverse mathematics. (2.2) Proof mining des Satzes von Hillam. Der Satz von Hillam charakterisiert die Konvergenz von Fixpunktiterationen. Wir extrahieren mit Hilfe von proof mining eine Rate der Konvergenz für die Fixpunktiteration.

Deutsch
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 04 Fachbereich Mathematik > Logik
04 Fachbereich Mathematik
Hinterlegungsdatum: 11 Jan 2012 11:35
Letzte Änderung: 05 Mär 2013 09:57
PPN:
Referenten: Kohlenbach, Prof. Dr. Ulrich ; Oliva, Reader Dr. Paulo ; Streicher, Prof. Dr. Thomas
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 6 Dezember 2011
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen