×

Semantical analysis of the logic of bunched implications. (English) Zbl 07725402

Summary: We give a novel approach to proving soundness and completeness for a logic (henceforth: the object-logic) that bypasses truth-in-a-model to work directly with validity. Instead of working with specific worlds in specific models, we reason with eigenworlds (i.e., generic representatives of worlds) in an arbitrary model. This reasoning is captured by a sequent calculus for a meta-logic (in this case, first-order classical logic) expressive enough to capture the semantics of the object-logic. Essentially, one has a calculus of validity for the object-logic. The method proceeds through the perspective of reductive logic (as opposed to the more traditional paradigm of deductive logic), using the space of reductions as a medium for showing the behavioural equivalence of reduction in the sequent calculus for the object-logic and in the validity calculus. Rather than study the technique in general, we illustrate it for the logic of Bunched Implications (BI), thus IPL and MILL (without negation) are also treated. Intuitively, BI is the free combination of intuitionistic propositional logic and multiplicative intuitionistic linear logic, which renders its meta-theory is quite complex. The literature on BI contains many similar, but ultimately different, algebraic structures and satisfaction relations that either capture only fragments of the logic (albeit large ones) or have complex clauses for certain connectives (e.g., Beth’s clause for disjunction instead of Kripke’s). It is this complexity that motivates us to use BI as a case-study for this approach to semantics.

MSC:

03-XX Mathematical logic and foundations

Software:

CoALP

References:

[1] Beth, W.E., Semantic Constructions of Intuitionistic Logic, Mededelingen Der Koninklijke Nederlandse Akademie Vanwetenschappen, Afd. Letterkunde 19(11):357-388, 1956. · Zbl 0073.24903
[2] Brotherston, J., Bunched Logics Displayed, Studia Logica 100(6):1223-1254, 2012. · Zbl 1282.03011
[3] Bundy, A., The Computer Modelling of Mathematical Reasoning, Academic Press Professional Inc., 1985. · Zbl 0541.68067
[4] Cao, Q., S. Cuellar, and A. W. Appel, Bringing Order to the Separation Logic Jungle, in Bor-Yuh Evan Chang, (ed.), Asian Symposium on Programming Languages and Systems - APLAS 15, vol. 10695 of Lecture Notes in Computer Science, Springer, 2017, pp. 190-211. · Zbl 1503.03034
[5] Docherty, S., Bunched Logics: A Uniform Approach, Ph.D. thesis, University College London, 2019.
[6] Docherty, S., and D. Pym, Intuitionistic Layered Graph Logic, in N. Olivetti, and A. Tiwari, (eds.), International Joint Conference on Automated Reasoning - IJCAR 16, Springer, 2016, pp. 469-486. · Zbl 1476.03024
[7] Docherty, S., and D. Pym, Modular Tableaux Calculi for Separation Theories, in Ch. Baier, and U. Dal Lago, (eds.), Foundations of Software Science and Computation Structures - FOSSACS 21, Springer International Publishing, 2018, pp. 441-458. · Zbl 1506.03073
[8] Docherty, S., and D. J. Pym, A Stone-type Duality Theorem for Separation Logic via its Underlying Bunched Logics, Electronic Notes in Theoretical Computer Science 336:101-118, 2018. · Zbl 1525.03094
[9] Docherty, S., and D. J. Pym, Intuitionistic Layered Graph Logic: Semantics and Proof Theory, Logical Methods in Computer Science 14:1-36, 2018. · Zbl 1454.03030
[10] Docherty, S., and D. J. Pym, Stone-Type Dualities for Separation Logics, Logical Methods in Computer Science 15:1-40, 2019. · Zbl 1432.03046
[11] Dummett, M. A. E., Elements of Intuitionism, vol. 39 of Oxford Logic Guides, Clarendon Press, 2000. · Zbl 0985.03508
[12] Gabbay, D.M., Fibring Logics, vol. 38 of Oxford Logic Guides, Clarendon Press, 1998.
[13] Galmiche, D., M. Marti, and D. Mery, Relating Labelled and Label-Free Bunched Calculi in BI Logic, in S. Cerrito, and A. Popescu, (eds.), Automated Reasoning with Analytic Tableaux and Related Methods - Tableaux 28, Springer International Publishing, 2019, pp. 130-146 · Zbl 1468.03024
[14] Galmiche, D., D. Mery, and D. Pym, The Semantics of BI and Resource Tableaux, Mathematical Structures in Computer Science 15(6):1033-1088, 2005. · Zbl 1145.03308
[15] Gheorghiu, A.V., S. Docherty, and D.J. Pym, Reductive Logic, Coalgebra, and Proof-search: A Perspective from Resource Semantics, in A. Palmigiano, and M. Sadrzadeh, (eds.), Samson Abramsky on Logic and Structure in Computer Science and Beyond, vol. 25 of Outstanding Contributions to Logic, Springer, 2023, to appear.
[16] Gheorghiu, A.V., and S. Marin, Focused Proof-search in the Logic of Bunched Implications, in S. Kiefer, and Ch. Tasson, (eds.), Foundations of Software Science and Computation Structures - FOSSACS 24, vol. 12650 of Lecture Notes in Computer Science, Springer, 2021, pp. 247-267. · Zbl 07410428
[17] Komendantskaya, E., G. McCusker, and J. Power, Coalgebraic Semantics for Parallel Derivation Strategies in Logic Programming, in M. Johnson, and D. Pavlovic, (eds.), International Conference on Algebraic Methodology and Software Technology - AMAST 13, vol. 6486 of Lecture Notes in Computer Science, Springer, 2011, pp. 111-127. · Zbl 1308.68029
[18] Kowalski, R., Logic for Problem Solving, vol. 7 of Artificial Intelligence Series, Elsevier North Holland, 1979. · Zbl 0426.68002
[19] Kowalski, R., and D. Kuehner, Linear Resolution with Selection Function, Artificial Intelligence 2(3):227-260, 1971. · Zbl 0234.68037
[20] Kreisel, G., Elementary Completeness Properties of Intuitionistic Logic with a Note on Negations of Prenex Formulae, The Journal of Symbolic Logic, 23, 3, 317-330 (1958) · Zbl 0086.24601 · doi:10.2307/2964291
[21] Kripke, S. A., Semantical Analysis of Intuitionistic Logic I, in J. N. Crossley, and M. A. E. Dummett, (eds.), Formal Systems and Recursive Functions, vol. 40 of Studies in Logic and the Foundations of Mathematics, Elsevier, 1965, pp. 92-130. · Zbl 0137.00702
[22] Milner, R., The Use of Machines to Assist in Rigorous Proof, Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences 312(1522):411-422, 1984. · Zbl 0572.68078
[23] Negri, S., Proof Analysis in Modal Logic, Journal of Philosophical Logic 34(5):507-544, 2005. · Zbl 1086.03045
[24] O’Hearn, P. W., and D. J. Pym, The Logic of Bunched Implications, The Bulletin of Symbolic Logic 5(2):215-244, 1999. · Zbl 0930.03095
[25] Pym, D. J., The Semantics and Proof Theory of the Logic of Bunched Implications, vol. 26 of Applied Logic Series, Springer, 2002. · Zbl 1068.03001
[26] Pym, D. J., P. W. O’Hearn, and H. Yang, Possible Worlds and Resources: The Semantics of BI, Theoretical Computer Science 315(1):257-305, 2004. · Zbl 1055.03021
[27] Pym, D. J., and E. Ritter, Reductive Logic and Proof-search: Proof theory, Semantics, and Control, vol. 45 of Oxford Logic Guides, Clarendon Press, 2004. · Zbl 1062.03003
[28] Read, S., Relevant Logic, Basil Blackwell, 1988.
[29] Routley, R., and R. Meyer, The Semantics of Entailment, in H. Leblanc, (ed.), Truth, Syntax, and Modality, vol. 68 of Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1973, pp. 199-243. · Zbl 0317.02017
[30] Schroeder-Heister, P., Proof-Theoretic Semantics, in E. N. Zalta, (ed.), The Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford University, Spring 2018. · Zbl 1528.03232
[31] Szabo, M. E., (ed.), The Collected Papers of Gerhard Gentzen, North-Holland Publishing Company, 1969. · Zbl 0209.30001
[32] Troelstra, A. S., and H. Schwichtenberg, Basic Proof Theory, vol. 43 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2000. · Zbl 0957.03053
[33] Urquhart, A., Semantics for Relevant Logics, The Journal of Symbolic Logic 37(1):159-169, 1972. · Zbl 0245.02028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.