5 found
Order:
  1.  16
    On a Question of Krajewski's.Fedor Pakhomov & Albert Visser - 2019 - Journal of Symbolic Logic 84 (1):343-358.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  12
    Truth, Disjunction, and Induction.Ali Enayat & Fedor Pakhomov - 2019 - Archive for Mathematical Logic 58 (5-6):753-766.
    By a well-known result of Kotlarski et al., first-order Peano arithmetic \ can be conservatively extended to the theory \ of a truth predicate satisfying compositional axioms, i.e., axioms stating that the truth predicate is correct on atomic formulae and commutes with all the propositional connectives and quantifiers. This result motivates the general question of determining natural axioms concerning the truth predicate that can be added to \ while maintaining conservativity over \. Our main result shows that conservativity fails even (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  6
    Short Proofs for Slow Consistency.Anton Freund & Fedor Pakhomov - 2020 - Notre Dame Journal of Formal Logic 61 (1):31-49.
    Let Con↾x denote the finite consistency statement “there are no proofs of contradiction in T with ≤x symbols.” For a large class of natural theories T, Pudlák has shown that the lengths of the shortest proofs of Con↾n in the theory T itself are bounded by a polynomial in n. At the same time he conjectures that T does not have polynomial proofs of the finite consistency statements Con)↾n. In contrast, we show that Peano arithmetic has polynomial proofs of Con)↾n, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  13
    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   2 citations  
  5.  7
    Complexity of the Interpretability Logic IL.Luka Mikec, Fedor Pakhomov & Mladen Vuković - forthcoming - Logic Journal of the IGPL.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark