Switch to: References

Add citations

You must login to add citations.
  1. On the complexity of the closed fragment of Japaridze’s provability logic.Fedor Pakhomov - 2014 - Archive for Mathematical Logic 53 (7-8):949-967.
    We consider the well-known provability logic GLP. We prove that the GLP-provability problem for polymodal formulas without variables is PSPACE-complete. For a number n, let L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} denote the class of all polymodal variable-free formulas without modalities ⟨n⟩,⟨n+1⟩,...\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle n \rangle,\langle n+1\rangle,...}$$\end{document}. We show that, for every number n, the GLP-provability problem for formulas from L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Turing–Taylor Expansions for Arithmetic Theories.Joost J. Joosten - 2016 - Studia Logica 104 (6):1225-1243.
    Turing progressions have been often used to measure the proof-theoretic strength of mathematical theories: iterate adding consistency of some weak base theory until you “hit” the target theory. Turing progressions based on n-consistency give rise to a \ proof-theoretic ordinal \ also denoted \. As such, to each theory U we can assign the sequence of corresponding \ ordinals \. We call this sequence a Turing-Taylor expansion or spectrum of a theory. In this paper, we relate Turing-Taylor expansions of sub-theories (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Münchhausen provability.Joost J. Joosten - 2021 - Journal of Symbolic Logic 86 (3):1006-1034.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The polytopologies of transfinite provability logic.David Fernández-Duque - 2014 - Archive for Mathematical Logic 53 (3-4):385-431.
    Provability logics are modal or polymodal systems designed for modeling the behavior of Gödel’s provability predicate and its natural extensions. If Λ is any ordinal, the Gödel-Löb calculus GLPΛ contains one modality [λ] for each λ < Λ, representing provability predicates of increasing strength. GLPω has no non-trivial Kripke frames, but it is sound and complete for its topological semantics, as was shown by Icard for the variable-free fragment and more recently by Beklemishev and Gabelaia for the full logic. In (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • The omega-rule interpretation of transfinite provability logic.David Fernández-Duque & Joost J. Joosten - 2018 - Annals of Pure and Applied Logic 169 (4):333-371.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Models of transfinite provability logic.David Fernández-Duque & Joost J. Joosten - 2013 - Journal of Symbolic Logic 78 (2):543-561.
    For any ordinal $\Lambda$, we can define a polymodal logic $\mathsf{GLP}_\Lambda$, with a modality $[\xi]$ for each $\xi < \Lambda$. These represent provability predicates of increasing strength. Although $\mathsf{GLP}_\Lambda$ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted $\mathsf{GLP}^0_\omega$. Later, Icard defined a topological model for $\mathsf{GLP}^0_\omega$ which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary $\Lambda$. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Predicativity through transfinite reflection.Andrés Cordón-Franco, David Fernández-Duque, Joost J. Joosten & Francisco Félix Lara-martín - 2017 - Journal of Symbolic Logic 82 (3):787-808.
    Let T be a second-order arithmetical theory, Λ a well-order, λ < Λ and X ⊆ ℕ. We use $[\lambda |X]_T^{\rm{\Lambda }}\varphi$ as a formalization of “φ is provable from T and an oracle for the set X, using ω-rules of nesting depth at most λ”.For a set of formulas Γ, define predicative oracle reflection for T over Γ ) to be the schema that asserts that, if X ⊆ ℕ, Λ is a well-order and φ ∈ Γ, then$$\forall \,\lambda (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • A many-sorted variant of Japaridze’s polymodal provability logic.Gerald Berger, Lev D. Beklemishev & Hans Tompits - 2018 - Logic Journal of the IGPL 26 (5):505-538.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Reflection algebras and conservation results for theories of iterated truth.Lev D. Beklemishev & Fedor N. Pakhomov - 2022 - Annals of Pure and Applied Logic 173 (5):103093.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Provability logic.Rineke Verbrugge - 2008 - Stanford Encyclopedia of Philosophy.
    -/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical point of view, provability logic is interesting because (...)
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations