The Constructive μ \mu -calculus: Game Semantics and Non-Wellfounded Proof Systems
Leonardo Pacheco · 2026
Read The Constructive μ \mu -calculus: Game Semantics and Non-Wellfounded Proof Systems by Leonardo Pacheco (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23273.txt.
Introduction
Pacheco studies a constructive variant of the modal mu-calculus built on the constructive modal logic CK. He defines game semantics for this calculus and proves it equivalent to birelational Kripke semantics. From the game semantics, he proves soundness and completeness of a fully labelled non-wellfounded proof system. He closes by sketching how the game semantics and proof system carry over to the mu-calculus over other non-classical modal logics.
Catalog record
| CREATOR | Leonardo Pacheco |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68429 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23273
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Constructive μ \mu -calculus: Game Semantics and Non-Wellfounded Proof Systems Leonardo Pacheco Abstract We study a variant of the modal μ \mu -calculus based on the constructive modal logic 𝖢𝖪 \mathsf{CK} . We define game semantics for the constructive μ \mu -calculus and prove its equivalence to the birelational Kripke semantics. We then use the game semantics to prove the soundness and completeness of a fully-labeled non-wellfounded proof system for it. At last, we briefly describe how to adapt the game semantics and proof system to the μ \mu -calculus over other non-classical modal logics. 1 Introduction We define a constructive variant of the modal \mu -calculus by adding least and greatest fixed-point operators to the constructive modal logic \mathsf{CK} . We then define birelational and Kripke game semantics for the constructive \mu -calculus and prove their equivalence. We combine fully-labeled sequents and non-wellfounded proof systems to define \mathsf{lab}\mu\mathsf{CK}_{\omega} . We prove that \mathsf{lab}\mu\mathsf{CK}_{\omega} is sound and weakly complete with respect to \mathsf{CK} -models using our game semantics. To illustrate the flexibility of our methods, we describe how to adapt \mathsf{lab}\mu\mathsf{CK}_{\omega} to proof systems \mathsf{lab}\mu\mathsf{IK}_{\omega} and \mathsf{lab}\mu\mathsf{GK}_{\omega} sound and weakly complete with respect to the non-classical modal logics \mathsf{IK} and \mathsf{GL} , respectively. The modal \mu -calculus was defined by Kozen [ 24 ] by adding least and greatest fixed-point operators to \mathsf{K} . The \mu -formulas are famously hard to understand as they allow for entangled least and greatest fixed-point operators. Game semantics for the \mu -calculus they give a more intuitive interpretation of the \mu -formulas; they are also a powerful tool to work with. See [ 10 , 22 , 26 ] for more information on the classical \mu -calculus. Kozen also defined a Hilbert-style proof system \mathsf{\mu K} for the classical \mu -calculus, whose completeness was first proved by Walukiewicz [ 36 ] . This result was obtained by an analysis of a non-wellfounded proof system first studied by Niwiński and Walukiewicz [ 30 ] . Other infinitary proof systems for the \mu -calculus have also been studied [ 3 , 35 ] . In constructive modal logic, the duality of the modalities \Box and \Diamond is lost. These logics have been studied for a long time: some of the first texts on the topic are Fitch [ 18 ] and Prawitz [ 33 ] . In this paper, we use Mendler and de Paiva’s birelational \mathsf{CK} -models [ 28 ] . These models have two relations: one to interpret the intuitionistic part of the language and one to interpret the modal part of the language. These models are based on those of Wijesekera [ 37 ] , but allow worlds where the false proposition \bot holds. In addition to \mathsf{CK} , there are other non-classical variants of modal logic such as intuitionistic modal logic [ 34 , 17 ] and Gödel–Dummett modal logic [ 12 , 11 ] . These are closely related to constructive modal logic On the axiomatic side, these logics are obtained by adding axioms to constructive modal logic. On the semantics side, they are obtained by adding further restrictions on \mathsf{CK} -models. It is also common to consider non-classical modal logics containing only one of \Box and \Diamond following [ 9 , 31 ] . See [ 13 , 14 , 34 ] for more information on the relation between constructive and intuitionistic modal logics. Note that other non-classical fixed-point logics other than have also appeared in the literature [ 1 , 2 , 6 , 8 , 16 , 23 , 29 ] . More recently, Afshari et al. [ 3 ] proved the completeness of a constructive fragment of the classical \mu -calculus. Fully-labeled sequents were first used by Marin et al. [ 27 ] to study the intuitionistic modal logic \mathsf{IK} . They consist of labeled formulas x:\varphi along statements x\preceq y and xRy between variables representing worlds. They were later used to prove the decidability of \mathsf{IS4} [ 20 ] and \mathsf{IK} [ 21 ] . As we will see, they are a flexible tool which can be easily adapted to many non-classical modal logics. Our contribution We first define evaluation games for the constructive \mu -calculus. In both classical and constructive games, two players discuss whether a formula is true at a given world of a Kripke model. In the classical games, it is usual to refer to the players as Verifier and Refuter. In the constructive games, we will still have two players; but now Verifier and Refuter denote two roles and may switch roles depending on their moves. This change is necessary because, over constructive semantics, not every formula can be put in negative normal form; and formulas in negative normal form are what allows us to simplify the classical evaluation games. Furthermore, we also need to consider the semantics of constructive diamonds, which mix universal and existential quantifiers. Therefore we will need a more delicate argument to prove the equivalence of the semantics in the constructive case. We then define a fully-labeled non-wellfounded proof system \mathsf{lab}\mu\mathsf{CK}_{\omega} . This is obtained by adding fixed-points to a proof system based on the fully-labeled proof systems of Marin et al. [ 27 ] and binested proof system of Gao and Olivetti [ 19 ] . We prove its soundness by showing that any contermodel for a formula \varphi witnesses that \varphi has no proof. We then prove its completeness by extracting a countermodel \varphi from a failed proof search. We also sketch how to adapt our results to obtain proof systems for the intuitionistic modal logic \mathsf{IK} [ 34 ] the Gödel–Dummett modal logic \mathsf{GK} [ 12 ] , and other related modal logics. We close the paper with some remarks on future work. 2 Constructive \mu -calculus 2.1 Syntax The language of the \mu -calculus is obtained by adding least and greatest fixed-point operators \mu and \nu to the language of modal logic. When defining the fixed-point formulas \mu X.\varphi and \nu X.\varphi , we need a syntactical requirement in order to have well-defined semantics. Definition 1 . Fix pairwise disjoint sets \mathrm{Prop} and \mathrm{Var} of propositions and propositional variables, respectively. The \mu -formulas are defined by the following grammar: \varphi:=P\mid X\mid\bot\mid\varphi\land\varphi\mid\varphi\lor\varphi\mid\varphi\to\varphi\mid\Box\varphi\mid\Diamond\varphi\mid\mu X.\varphi\mid\nu X.\varphi, where P is a proposition, X is a propositional variable occurring only positively in \varphi . We abbreviate \varphi\to\bot by \neg\varphi and \bot\to\bot by \top . We also call \mu -formulas by formulas. The fixed-point formulas \mu X.\varphi and \nu X.\varphi are defined iff X is positive in \varphi . We classify an occurrence of X as positive or negative in a given formula by structural induction: • X is positive and negative in P and in \bot ; • X is positive in X ; • if Y\neq X , X is positive and negative in Y ; • if X is positive (negative) in \varphi and \psi , then X is positive (negative) in \varphi\land\psi , \varphi\lor\psi , \Box\varphi , and \Diamond\varphi ; • if X is negative (positive) in \varphi and positive (negative) in \psi , then X is positive (negative) in \varphi\to\psi ; • X is positive and negative in \mu X.\varphi and \nu X.\varphi .