On structural proof theory of the modal logic K+ extended with infinitary derivations

被引:0
作者
Shamkanov, Daniyar [1 ]
机构
[1] Russian Acad Sci, Steklov Math Inst, 8 Gubkina St, Moscow 119991, Russia
关键词
transitive closure; infinitary derivations; non-well-founded proofs; continuous cut elimination; SEMANTICS;
D O I
10.1093/jigpal/jzae121
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We consider an extension of the modal logic of transitive closure K+ with certain infinitary derivations and present a sequent calculus for this extension, which allows non-well-founded proofs. We establish continuous cut-elimination for the given calculus using fixed-point theorems for contractive mappings. The infinitary derivations mentioned above are well founded and countably branching, while the non-well-founded proofs of the sequent calculus can only be finitely branching. The ordinary derivations in K+, as we show additionally, correspond to the non-well-founded proofs of the calculus that are regular and cut-free. Therefore, in this article, we explore the relationship between deductive systems for K+ with well-founded infinitely branching derivations and (regular) non-well-founded finitely branching proofs.
引用
收藏
页数:46
相关论文
共 30 条
  • [1] Acclavio M, 2024, Arxiv, DOI arXiv:2308.07789
  • [2] Baelde D., 2016, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), p42:1
  • [3] Baelde D., LICS22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Aug 2022, Haifa, Israel, 10.1145/3531130.3533375
  • [4] DENOTATIONAL SEMANTICS IN THE CPO AND METRIC APPROACH
    BAIER, C
    MAJSTERCEDERBAUM, ME
    [J]. THEORETICAL COMPUTER SCIENCE, 1994, 135 (02) : 171 - 220
  • [5] Two Ways to Common Knowledge
    Bucheli, Samuel
    Kuznets, Roman
    Studer, Thomas
    [J]. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2010, 262 : 83 - 98
  • [6] Das A., 2018, The 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), volume 119 of Leibniz International Proceedings in Informatics (LIPIcs), p19:1
  • [7] ON THE LOGICAL COMPLEXITY OF CYCLIC ARITHMETIC
    Das, Anupam
    [J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2020, 16 (01) : 1:1 - 1:39
  • [8] Di Gianantonio P., 2003, Types for Proofs and Programs. International Workshop, TYPES 2002. Selected Papers (Lecture Notes in Computer Science Vol.2646), P148
  • [9] Doczkal Christian, 2012, Certified Programs and Proofs. Second International Conference (CPP 2012). Proceedings, P224, DOI 10.1007/978-3-642-35308-6_18
  • [10] Escard MH., 1998, A metric model of PCF