Constructive and Mechanised Meta-Theory of IEL and Similar Modal Logics

Saarland University Computer Science

Christian Hagemeier, Dominik Kirst

Artemov and Protopopescu proposed intuitionistic epistemic logic (IEL) to capture an intuitionistic conception of knowledge. By establishing completeness, they provided the base for a meta-theoretic investigation of IEL, which was continued by Krupski with a proof of cut-elimination, and Su and Sano establishing semantic cut-elimination and the finite model property. However, no analysis of these results in a constructive meta-logic has been conducted, arguably impeding the intuitionistic justification of IEL.

We aim to close this gap and investigate IEL in the constructive type theory of the Coq proof assistant. Concretely, we present a constructive and mechanised completeness proof for IEL, employing a syntactic decidability proof based on cut-elimination to constructivise the ideas from the literature. Following Su and Sano, we then also give constructive versions of semantic cut-elimination and the finite model property. Given our constructive and mechanised setting, all these results now bear executable algorithms.

Our particular strategy to establish constructive completeness exploiting syntactic decidability can be used for similar modal logics, which we illustrate with the examples of the classical modal logics K, D, and T. For modal logics including the 4 axiom, however, the method seems not to apply immediately.


Coq Mechanisation (Coq version 8.13.2)