On the Correspondence between Nested Calculi and Semantic Systems for Intuitionistic Logics

Journal of Logic and Computation 31 (1):213-265 (2021)
  Copy   BIBTEX

Abstract

This paper studies the relationship between labelled and nested calculi for propositional intuitionistic logic, first-order intuitionistic logic with non-constant domains and first-order intuitionistic logic with constant domains. It is shown that Fitting’s nested calculi naturally arise from their corresponding labelled calculi—for each of the aforementioned logics—via the elimination of structural rules in labelled derivations. The translational correspondence between the two types of systems is leveraged to show that the nested calculi inherit proof-theoretic properties from their associated labelled calculi, such as completeness, invertibility of rules and cut admissibility. Since labelled calculi are easily obtained via a logic’s semantics, the method presented in this paper can be seen as one whereby refined versions of labelled calculi (containing nested calculi as fragments) with favourable properties are derived directly from a logic’s semantics.

Links

PhilArchive

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

Cut-elimination and proof-search for bi-intuitionistic logic using nested sequents.Rajeev Goré, Linda Postniece & Alwen Tiu - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 43-66.
Cut-free Calculi and Relational Semantics for Temporal STIT Logics.Tim Lyon & Kees van Berkel - 2019 - In Francesco Calimeri, Nicola Leone & Marco Manna (eds.), Logics in Artificial Intelligence. Springer. pp. 803 - 819.
Proof theory for quantified monotone modal logics.Sara Negri & Eugenio Orlandelli - 2019 - Logic Journal of the IGPL 27 (4):478-506.
Semantics for a class of intuitionistic modal calculi.Gisele Servi - 1978 - Bulletin of the Section of Logic 7 (1):26-29.
Gentzen sequent calculi for some intuitionistic modal logics.Zhe Lin & Minghui Ma - 2019 - Logic Journal of the IGPL 27 (4):596-623.
Analytic Calculi for Product Logics.George Metcalfe, Nicola Olivetti & Dov Gabbay - 2004 - Archive for Mathematical Logic 43 (7):859-889.
Maehara-style modal nested calculi.Roman Kuznets & Lutz Straßburger - 2019 - Archive for Mathematical Logic 58 (3-4):359-385.
The Basics of Display Calculi.Tim Lyon, Christian Ittner, Timo Eckhardt & Norbert Gratzl - 2017 - Kriterion - Journal of Philosophy 31 (2):55-100.

Analytics

Added to PP
2021-04-07

Downloads
180 (#104,917)

6 months
57 (#73,285)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Tim Lyon
Technische Universität Dresden