Finitary Proof Systems for Kozen's μ

Abstract

We present three finitary cut-free sequent calculi for the modal $μ$-calculus. Two of these derive annotated sequents in the style of Stirling’s ‘tableau proof system with names’ (2014) and feature special inferences that discharge open assumptions. The third system is a variant of Kozen’s axiomatisation in which cut is replaced by a strengthening of the $ν$-induction inference rule. Soundness and completeness for the three systems is proved by establishing a sequence of embeddings between the calculi, starting at Stirling’s tableau-proofs and ending at the original axiomatisation of the $μ$-calculus due to Kozen. As a corollary we obtain a completeness proof for Kozen’s axiomatisation which avoids the usual detour through automata or games.