Cyclic Involutive Distributive Full Lambek Calculus is Decidable
We prove the decidability of the extension CyInDFL of DFL (Distributive Full Lambek Calculus), in which the involutive law is derivable under the assumption of cyclicity. So far, the decidability of this logic has been an open problem (Galatos et al., 2007, Residuated Lattices: An Algebraic Glimpse at Substructural Logics, Elsevier). We present a Gentzen-style consecution calculus which is complete with respect to the class of cyclic involutive distributive full Lambek algebras (CyInDFL). It is an extension of the system DFL introduced by the author (2009, Stud. Log., 91, 201-216). We prove the cut elimination theorem for this system, and give a procedure of building a finite proof-search tree for any consecution.
cyclicity involution full lambek calculus decidability residuated lattice cut elimination distributive lattice