Münchhausen provability

Journal of Symbolic Logic 86 (3):1006-1034 (2021)
  Copy   BIBTEX

Abstract

By Solovay’s celebrated completeness result [31] on formal provability we know that the provability logic ${\textbf {GL}}$ describes exactly all provable structural properties for any sound and strong enough arithmetical theory with a decidable axiomatisation. Japaridze generalised this result in [22] by considering a polymodal version ${\mathsf {GLP}}$ of ${\textbf {GL}}$ with modalities $[n]$ for each natural number n referring to ever increasing notions of provability. Modern treatments of ${\mathsf {GLP}}$ tend to interpret the $[n]$ provability notion as “provable in a base theory T together with all true $\Pi ^0_n$ formulas as oracles.” In this paper we generalise this interpretation into the transfinite. In order to do so, a main difficulty to overcome is to generalise the syntactical characterisations of the oracle formulas of complexity $\Pi ^0_n$ to the hyper-arithmetical hierarchy. The paper exploits the fact that provability is $\Sigma ^0_1$ complete and that similar results hold for stronger provability notions. As such, the oracle sentences to define provability at level $\alpha $ will recursively be taken to be consistency statements at lower levels: provability through provability whence the name of the paper. The paper proves soundness and completeness for the proposed interpretation for a wide class of theories, namely for any theory that can formalise the recursion described above and that has some further very natural properties. Some remarks are provided on how the recursion can be formalised into second order arithmetic and on lowering the proof-theoretical strength of these systems of second order arithmetic.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,442

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Provability logic.Rineke Verbrugge - 2008 - Stanford Encyclopedia of Philosophy.
Provability logics with quantifiers on proofs.Rostislav E. Yavorsky - 2001 - Annals of Pure and Applied Logic 113 (1-3):373-387.
The polytopologies of transfinite provability logic.David Fernández-Duque - 2014 - Archive for Mathematical Logic 53 (3-4):385-431.
On the provability logic of bounded arithmetic.Rineke Verbrugge & Alessandro Berarducci - 1991 - Annals of Pure and Applied Logic 61 (1-2):75-93.
The analytical completeness of Dzhaparidze's polymodal logics.George Boolos - 1993 - Annals of Pure and Applied Logic 61 (1-2):95-111.
A modal provability logic of explicit and implicit proofs.Evan Goris - 2010 - Annals of Pure and Applied Logic 161 (3):388-403.
Rosser Provability and Normal Modal Logics.Taishi Kurahashi - 2020 - Studia Logica 108 (3):597-617.

Analytics

Added to PP
2021-12-06

Downloads
6 (#1,105,852)

6 months
1 (#454,876)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Joost Joosten
Universitat de Barcelona

Citations of this work

No citations found.

Add more citations

References found in this work

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems.G. Kreisel & A. Lévy - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):97-142.
Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems.Georg Kreisel & Azriel Lévy - 1968 - Zeitschrift für Mathematische Logic Und Grundlagen der Mathematik 14 (1):97--142.
Proof-theoretic analysis by iterated reflection.Lev D. Beklemishev - 2003 - Archive for Mathematical Logic 42 (6):515-552.
Provability algebras and proof-theoretic ordinals, I.Lev D. Beklemishev - 2004 - Annals of Pure and Applied Logic 128 (1-3):103-123.

View all 15 references / Add more references