Cut Elimination in Coalgebraic Logics (bibtex)
by Dirk Pattinson, Lutz Schröder
Abstract:
We give two generic proofs for cut elimination in propositional modal logics, interpreted over coalgebras. We first investigate semantic coherence conditions between the axiomatisation of a particular logic and its coalgebraic semantics that guarantee that the cut-rule is admissible in the ensuing sequent calculus. We then independently isolate a purely syntactic property of the set of modal rules that guarantees cut elimination. Apart from the fact that cut elimination holds, our main result is that the syntactic and semantic assumptions are equivalent in case the logic is amenable to coalgebraic semantics. As applications we present a new proof of the (already known) interpolation property for coalition logic and newly establish the interpolation property for the conditional logics CK and CK+ID.
Reference:
Cut Elimination in Coalgebraic Logics (Dirk Pattinson, Lutz Schröder), In Information and Computation, vol. 208, pp. 1447–1468, 2010. [preprint]
Bibtex Entry:
@Article{PattinsonSchroder10,
  author = {Dirk Pattinson and Lutz Schr{\"o}der},
  title = {Cut Elimination in Coalgebraic Logics},
  year = {2010},
  journal = {Information and Computation},
  volume = {208},
  pages = {1447-1468},
  keywords = {Coalgebra modal logic cut elimination interpolation coalition logic conditiona logic},
  url = {http://dx.doi.org/10.1016/j.ic.2009.11.008},
  comment = { <a href = "http://www8.informatik.uni-erlangen.de/~schroeder/papers/cut-ext.pdf"> [preprint] </a>},
  abstract = {We give two generic proofs for cut elimination in
  propositional modal logics, interpreted over coalgebras. We first
  investigate semantic coherence conditions between the axiomatisation
  of a particular logic and its coalgebraic semantics that guarantee
  that the cut-rule is admissible in the ensuing sequent calculus. We
  then independently isolate a purely syntactic property of the set of
  modal rules that guarantees cut elimination.  Apart from the fact
  that cut elimination holds, our main result is that the syntactic
  and semantic assumptions are equivalent in case the logic is
  amenable to coalgebraic semantics.  As applications we present a new
  proof of the (already known) interpolation property for coalition
  logic and newly establish the interpolation property for the conditional
  logics CK and CK+ID.},
}
Powered by bibtexbrowser