On the Axiomatisation of Boolean Categories with and without Medial

Lutz Strassburger (1, 2)

1 PARSIFAL - Proof search and reasoning with logic specifications
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

In its most general meaning, a Boolean category is to categories what a Boolean algebra is to posets. In a more specific meaning a Boolean category should provide the abstract algebraic structure underlying the proofs in Boolean Logic, in the same sense as a Cartesian closed category captures the proofs in intuitionistic logic and a *-autonomous category captures the proofs in linear logic. However, recent work has shown that there is no canonical axiomatisation of a Boolean category. In this work, we will see a series (with increasing strength) of possible such axiomatisations, all based on the notion of *-autonomous category. We will particularly focus on the medial map, which has its origin in an inference rule in KS, a cut-free deductive system for Boolean logic in the calculus of structures. Finally, we will present a category proof nets as a particularly well-behaved example of a Boolean category.

Domaines: Logique en informatique [cs.LO]; Catégories et ensembles [math.CT]; Logique [math.LO]

Lutz Strassburger. On the Axiomatisation of Boolean Categories with and without Medial. 2006. ⟨inria-00130508⟩