Hypersequent Calculi for S5: The Methods of Cut Elimination
DOI:
https://doi.org/10.12775/LLP.2015.018Keywords
cut elimination, modal logic, hypersequent calculi, proof theoryAbstract
S5 is one of the most important modal logic with nice syntactic, semantic and algebraic properties. In spite of that, a successful (i.e. cut-free) formalization of S5 on the ground of standard sequent calculus (SC) was problematic and led to the invention of numerous nonstandard, generalized forms of SC. One of the most interesting framework which was very often used for this aim is that of hypersequent calculi (HC). The paper is a survey of HC for S5 proposed by Pottinger, Avron, Restall, Poggiolesi, Lahav and Kurokawa. We are particularly interested in examining different methods which were used for proving the eliminability/admissibility of cut in these systems and present our own variant of a system which admits relatively simple proof of cut elimination.References
Avron, A., “A constructive analysis of RM”, Journal of Symbolic Logic, 52, 4 (1987): 939–951. DOI: 10.2307/2273828
Avron, A., “Hypersequents, logical consequence and intermediate logics for concurrency”, Annals of Mathematics and Artificial Intelligence, 4, 3–4 (1991): 225–248. DOI: 10.1007/BF01531058
Avron, A., “The method of hypersequents in the proof theory of propositional non-classical logic”, pages 1–32 in Logic: from Foundations to Applications, 1996.
Avron, A., “A simple proof of completeness and cut-elimination for propositional Gödel logic”, Journal of Logic and Computation, 21 (2011): 813–821.
Belnap, N.D., “Display logic”, Journal of Philosophical Logic, 11, 4 (1982): 375–417. DOI: 10.1007/BF00284976
Braüner, T., “A cut-free Gentzen formulation of the modal logic S5”, Logic Journal of the IGPL, 8, 5 (2000): 629–643. DOI: 10.1093/jigpal/8.5.629
Baaz, M., and A. Ciabattoni, “A Schütte-Tait style cut-elimination proof for first-order Gödel logic”, pages 24–38 in Automated Reasoning with Tableaux and Related Methods (Tableaux’02), vol. 2381 of LNAI, 2002.
Baaz, M., A. Ciabattoni, and C.G. Fermüller, “Hypersequent calculi for Gödel logics – a survey”, Journal of Logic and Computation, 13 (2003): 1–27.
Ciabattoni, A., G. Metcalfe, and F. Montagna, “Algebraic and prooftheoretic characterizations of truth stressers for MTL and its extensions”, Fuzzy Sets and Systems, 161 , 3 (2010): 369–389. DOI: 10.1016/j.fss.2009.09.001
Ciabattoni, A., R. Ramanayake, and H. Wansing, “Hypersequent and display calculi – a unified perspective”, Studia Logica, 102, 6 (2014): 1245–1294. DOI: 10.1007/s11225-014-9566-z
Curry, H.B., Foundations of Mathematical Logic, McGraw-Hill: New York, 1963.
Fitting, M., Proof Methods for Modal and Intuitionistic Logics, Reidel: Dordrecht, 1983.
Girard, J. Y., Proof Theory and Logical Complexity, Bibliopolis: Napoli, 1987.
Indrzejczak, A., “Cut-free double sequent calculus for S5”, Logic Journal of the IGPL, 6, 3 (1998): 505–516. DOI: 10.1093/jigpal/6.3.505
Indrzejczak, A., “Cut-free hypersequent calculus for S4.3”, Bulletin of the Section of Logic, 41, 1/2 (2012): 89–104.
Indrzejczak, A., “Eliminability of cut in hypersequent calculi for some modal logics of linear frames”, Information Processing Letters, 115, 2 (2015): 75–81. DOI: 10.1016/j.ipl.2014.07.002
Kanger, S., “Provability in logic”, Stockholm Studies in Philosophy, 47 pp., series “Acta Universitatis Stockholmiensis”, Almqvist and Wiskell: Stockholm, 1957.
Kurokawa, H., “Hypersequent calculi for modal logics extending S4”, pages 51–68 in New Frontiers in Artificial Intelligence, series “Lecture Notes in Computer Science”, 2013. DOI: 10.1007/978-3-319-10061-6_4
Lahav, O., “From frame properties to hypersequent rules in modal logics”, pages 408–417 in 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013. DOI: 10.1109/LICS.2013.47
Metcalfe, G., N. Olivetti, and D. Gabbay, Proof Theory for Fuzzy Logics, Springer, 2008.
Mints, G., “Cut-free calculi of the S5 type”, pages 79–82 in Studies in Constructive Mathematics and Mathematical Logic, part 2, 1970. DOI: http://dx.doi.org/10.1007/978-1-4899-5327-8_16
Negri, S., “Proof analysis in modal logic”, Journal of Philosophical Logic, 34, 5–6 (2005): 507–544. DOI: 10.1007/s10992-005-2267-3
Negri, S., and J. von Plato, Proof Analysis a Contribution to Hilbert’s Last Problem, Cambridge, 2011.
Ohnishi, M., and K. Matsumoto, “Gentzen method in modal calculi I”, Osaka Mathematical Journal, 9 (1957): 113–130.
Ohnishi, M., and K. Matsumoto, ‘Gentzen method in modal calculi II”, Osaka Mathematical Journal, 11 (1959): 115–120.
Poggiolesi, F., “A cut-free simple sequent calculus for modal logic S5”, Review of Symbolic Logic, 1, 1 (2008): 3–15. DOI: 10.1017/S1755020308080040
Poggiolesi, F., Gentzen Calculi for Modal Propositional Logic, Springer, 2011. DOI: 10.1007/978-90-481-9670-8
Pottinger, G., “Uniform cut-free formulations of T, S4 and S5 (abstract)”, Journal of Symbolic Logic, 48 (1983): 900. DOI: 10.2307/2273495
Restall, G., “Proofnets for S5: Sequents and circuits for modal logic”, pages 151–172 in Logic Colloquium 2005, series “Lecture Notes in Logic”, no. 28, Cambridge University Press, 2007. DOI: 10.1017/CBO9780511546464.012
Sato, M., “A study of Kripke-type models for some modal logics by Gentzen’s sequential method”, Publications of the Research Institute for Mathematical Sciences, Kyoto University, 13 (1977): 381–468.
Stouppa, P., “The design of modal proof theories: the case of S5”, Master Thesis, Dresden, 2004.
Stouppa, P., “A deep inference system for the modal logic S5”, Studia Logica, 85, 2 (2007): 199–214. DOI: 10.1007/s11225-007-9028-y
Takano, M., “Subformula property as a substitute for cut-elimination in modal propositional logics”, Mathematica Japonica, 37, 6 (1992): 1129–1145.
Wansing, H., Displaying Modal Logics, Kluwer Academic Publishers: Dordrecht, 1999. DOI: 10.1007/978-94-017-1280-4
Zeman, J. J., Modal Logic, Oxford University Press, Oxford, 1973.
Downloads
Published
How to Cite
Issue
Section
Stats
Number of views and downloads: 739
Number of citations: 11
