Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-22T16:06:44.830Z Has data issue: false hasContentIssue false
  • English
  • Français

ANALYTIC CUT AND INTERPOLATION FOR BI-INTUITIONISTIC LOGIC

Published online by Cambridge University Press:  06 December 2016

TOMASZ KOWALSKI  and
HIROAKIRA ONO
TOMASZ KOWALSKI*
Affiliation:
Department of Mathematics and Statistics, La Trobe University
HIROAKIRA ONO*
Affiliation:
Japan Advanced Institute of Science and Technology
*
*DEPARTMENT OF MATHEMATICS AND STATISTICS LA TROBE UNIVERSITY MELBOURNE, VICTORIA 3086 AUSTRALIA E-mail: [email protected]
†JAPAN ADVANCED INSTITUTE OF SCIENCE AND TECHNOLOGY 1-1 ASAHIDAI, NOMI, ISHIKAWA 923-1292 JAPAN E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that certain natural sequent systems for bi-intuitionistic logic have the analytic cut property. In the process we show that the (global) subformula property implies the (local) analytic cut property, thereby demonstrating their equivalence. Applying a version of Maehara technique modified in several ways, we prove that bi-intuitionistic logic enjoys the classical Craig interpolation property and Maximova variable separation property; its Halldén completeness follows.

Keywords

analytic cutsubformula propertyinterpolation03F0303B4703F52
Type
Research Article
Information
The Review of Symbolic Logic , Volume 10 , Issue 2 , June 2017 , pp. 259 - 283
Copyright
Copyright © Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Badia, G. (2015). Bi-intuitionistic logic has Maksimova’s variable separation property. Personal communication.Google Scholar
Badia, G. (2016) A remark on Maximova’s variable separation property in super-bi-intuitionistic logic. Australian Journal of Logic, to appear.Google Scholar
Buisman, L. & Goré, R. (2007). A cut-free sequent calculus for bi-intuitionistic logic. In Olivetti, N., editor. Automated Reasoning with Analytic Tableaux and Related Methods. Lecture Notes in Computer Science, Vol. 4548. Berlin: Springer, pp. 90–106.Google Scholar
Chagrov, A. & Zakharyaschev, M. (1997). Modal Logic. Oxford Logic Guides, Vol. 35. New York: The Clarendon Press, Oxford University Press, Oxford Science Publications.CrossRefGoogle Scholar
Galatos, N., Jipsen, P., Kowalski, T., & Ono, H. (2007). Residuated Lattices: An Algebraic Glimpse at Substructural Logics. Studies in Logic and the Foundations of Mathematics, Vol. 151. Amsterdam: Elsevier B. V.Google Scholar
Kihara, H. & Ono, H. (2010). Interpolation properties, Beth definability properties and amalgamation properties for substructural logics. Journal of Logic and Computation, 20(4), 823–875.Google Scholar
Kowalski, T. (1998). Varieties of tense algebras. Reports on Mathematical Logic, 32, 53–95.Google Scholar
Lahav, O. & Avron, A. (2013). A unified semantic framework for fully structural propositional sequent systems. ACM Transactions on Computational Logic, 14(4), Art. 27, 1–33.Google Scholar
Maehara, S. (1960). On the interpolation theorem of Craig (in Japanese). Sugaku, 12, 235–237.Google Scholar
Maksimova, L. (1976). The principle of separation of variables in propositional logics. Algebra and Logic, 15, 168–184 (in Russian).CrossRefGoogle Scholar
Naruse, H., Surarso, B., & Ono, H. (1998). A syntactic approach to Maksimova’s principle of variable separation for some substructural logics. Notre Dame Journal of Formal Logic, 39(1), 94–113.Google Scholar
Ono, H. (1998). Proof-theoretic methods in nonclassical logic—an introduction. In Takahashi, M., Okada, M. and Dezani-Ciancaglini, M., editors. Theories of Types and Proofs (Tokyo, 1997). MSJ Memoirs, Vol. 2. Tokyo: Mathematical Society of Japan, pp. 207–254.Google Scholar
Ono, H. (2015). Semantical approach to cut elimination and subformula property in modal logic. In Yang, S. C.-M., Deng, D.-M., and Lin, H., editors. Structural Analysis of Non-classical Logics. The Proceedings of the Second Taiwan Philosophical Logic Colloquium. Logic in Asia, Studia Logica Library, Vol. 2. Berlin, Heidelberg: Springer-Verlag, pp. 1–15.Google Scholar
Pinto, L. & Uustalu, T. (2009). Proof search and counter-model construction for bi-intuitionistic propositional logic with labelled sequents. In Automated Reasoning with Analytic Tableaux and Related Methods. Lecture Notes in Computer Science, Vol. 5607. Berlin: Springer, pp. 295–309.CrossRefGoogle Scholar
Rauszer, C. (1971). Representation theorem for semi-Boolean algebras. I, II. Bulletin L’Académie Polonaise des Science, Série des Sciences Mathématiques, Astronomiques et Physiques, 19, 881–887; ibid. 19 (1972), 889–892.Google Scholar
Rauszer, C. (1973/74). Semi-Boolean algebras and their applications to intuitionistic logic with dual operations. Fundamenta Mathematicae, 83(3), 219–249.Google Scholar
Rauszer, C. (1974). A formalization of the propositional calculus of H-B logic. Studia Logica, 33, 23–34.Google Scholar
Rauszer, C. (1977a). Applications of Kripke models to Heyting-Brouwer logic. Studia Logica, 36(1–2), 61–71.Google Scholar
Rauszer, C. (1977b). The Craig interpolation theorem for an extension of intuitionistic logic. Bulletin L’Académie Polonaise des Science, Série des Sciences Mathématiques, Astronomiques et Physiques, 25(4), 337–341.Google Scholar
Rauszer, C. (1977c). Model theory for an extension of intuitionistic logic. Studia Logica, 36(1–2), 73–87.Google Scholar
Sankappanavar, H. P. (1985). Heyting algebras with dual pseudocomplementation. Pacific Journal of Mathematics, 117(2), 405–415.Google Scholar
Takano, M. (1992). Subformula property as a substitute for cut-elimination in modal propositional logics. Mathematica Japonica, 37(6), 1129–1145.Google Scholar
Takano, M. (2001). A modified subformula property for K5 and K5D. Bulletin of the Section of Logic, 30(2), 115–122.Google Scholar
Taylor, C. J. (2016). Discriminator varieties of double-Heyting algebras. Reports on Mathematical Logic, to appear.Google Scholar
Wolter, F. (1998). On logics with coimplication. Journal of Philosophical Logic, 27(4), 353–387.CrossRefGoogle Scholar
Wroński, A. (1976). Remarks on Halldén completeness of modal and intermediate logics. Bulletin of the Section of Logic, 5(4), 126–128.Google Scholar