Algebraic models and complete proof calculi for classical BI
File(s)DTR08-7.pdf (239.26 KB)
Published version
Author(s)
Brotherston, James
Calcagno, Cristiano
Type
Report
Abstract
We consider the classical (propositional) version, CBI, of
O’Hearn and Pym’s logic of bunched implications (BI) from a model-
and proof-theoretic perspective. We make two main contributions in this
paper. Firstly, we present a class of algebraic models for CBI which per-
mit the full range of classical multiplicative connectives to be modelled.
Our models can be seen as generalisations of Abelian groups, and in-
clude several computationally interesting models as concrete instances.
Secondly, we give a display calculus proof system for CBI that is an
instance of Belnap’s general display logic — hence cut-eliminating —
and demonstrate this system to be sound and complete with respect to
validity in our models. To achieve the latter, we first define a simple
extension of the usual sequent calculus for BI by axioms that directly
capture properties of our models, and show this extension to be sound
and complete (though not cut-eliminating). Soundness and completeness
of our display calculus then follows by establishing faithful translations
between the display calculus and this sequent calculus.
O’Hearn and Pym’s logic of bunched implications (BI) from a model-
and proof-theoretic perspective. We make two main contributions in this
paper. Firstly, we present a class of algebraic models for CBI which per-
mit the full range of classical multiplicative connectives to be modelled.
Our models can be seen as generalisations of Abelian groups, and in-
clude several computationally interesting models as concrete instances.
Secondly, we give a display calculus proof system for CBI that is an
instance of Belnap’s general display logic — hence cut-eliminating —
and demonstrate this system to be sound and complete with respect to
validity in our models. To achieve the latter, we first define a simple
extension of the usual sequent calculus for BI by axioms that directly
capture properties of our models, and show this extension to be sound
and complete (though not cut-eliminating). Soundness and completeness
of our display calculus then follows by establishing faithful translations
between the display calculus and this sequent calculus.
Date Issued
2008-01-01
Citation
Departmental Technical Report: 08/7, 2008, pp.1-28
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
28
Journal / Book Title
Departmental Technical Report: 08/7
Copyright Statement
© 2008 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Publication Status
Published
Article Number
08/7