Generic Methods for Formalising Sequent Calculi Applied to Provability Logic

Jeremy Dawson (ANU)

COMPUTER SCIENCE SEMINAR Logic and Computation

DATE: 2010-09-21
TIME: 15:30:00 - 16:30:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
We describe generic methods for reasoning about multiset-based sequent calculi which allow us to combine shallow and deep embeddings as desired. Our methods are modular, permit explicit structural rules, and are widely applicable to many sequent systems, even to other styles of calculi like natural deduction and term rewriting systems. We describe new axiomatic type classes which enable simplification of multiset or sequent expressions using existing algebraic manipulation facilities. We demonstrate the benefits of our combined approach by formalising in Isabelle/HOL a variant of a recent, non-trivial, pen-and-paper proof of cut-admissibility for the provability logic GL, where we express a large part of the proof in a way which is immediately applicable to other logics. Our work also provides a machine-checked proof to settle the controversy surrounding the proof of cut-admissibility for GL.