🔢 mathematics

Intuitionistic Monotone Modal Logic: Proof Theory and Semantics

This paper provides a semantic characterization and a structured proof calculus for the intuitionistic monotone modal logic IM and its extensions, establishing their decidability and highlighting a significant analogy between constructive variants of monotone and normal modal logics.

Original authors: Tiziano Dalmonte, Jim de Groot

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tiziano Dalmonte, Jim de Groot

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Building a New Rulebook for "Maybe"

Imagine you are trying to write a rulebook for a game where players make statements about what might happen or what must happen. In the standard version of this game (called Classical Logic), the rules are very strict: if something isn't proven false, it's considered true, and the concepts of "must" (necessity) and "might" (possibility) are locked together like two sides of the same coin.

However, in the world of Intuitionistic Logic (which is like a more cautious, "prove it to me" version of the game), things work differently. You can't just assume something is true because you can't prove it's false. Also, in this cautious world, "must" and "might" are no longer locked together; they are like two separate tools that don't necessarily depend on each other.

This paper focuses on a specific, recently discovered tool in this cautious world called IM (Intuitionistic Monotone Modal Logic). The authors, Tiziano Dalmonte and Jim de Groot, wanted to answer three big questions:

What does this tool actually mean? (Semantics)
How do we prove things using it without making mistakes? (Proof Theory)
Can we always tell if a statement is provable or not? (Decidability)

1. The Map: Constructive Neighborhoods (Semantics)

To understand what "IM" means, the authors built a map called a Constructive Neighborhood Model.

The Analogy:
Imagine you are standing in a city (a "world"). In front of you, there are several "neighborhoods" (groups of other places you can visit).

The "Must" (2): You can say "It must be sunny in the next neighborhood" only if you can find at least one neighborhood nearby where every single house is sunny.
The "Might" (3): You can say "It might be sunny in the next neighborhood" only if, no matter which neighborhood you look at, you can find at least one house inside it that is sunny.

The authors showed that this map perfectly matches the rules of their new logic. They also proved that if you follow these rules, you can never get stuck in a contradiction.

2. The Toolkit: A Special Calculator (Proof Theory)

The second part of the paper is about building a machine (a calculus) that can automatically check if a statement is true according to the rules of IM.

The Analogy:
Think of a standard logic proof like a stack of papers. The authors created a special stack called CIM.

Input vs. Output: They marked some papers as "Input" (things we assume are true) and others as "Output" (things we are trying to prove).
The Magic Blocks: They introduced special folders called Blocks. Imagine a block is a small box you can put papers in. These boxes represent the "neighborhoods" from the map above.
The Pruning Trick: The most clever part of their machine is a rule called Output Pruning. Imagine you are writing a proof, and you reach a point where you need to move to a "future" version of the proof. The machine has a special scissors that cuts off the "Output" papers (the things you are trying to prove) but leaves the "Input" papers and the "Blocks" intact.

Why is this cool?
This "pruning" action is the secret sauce that makes the logic work for IM. If you change the scissors to be even more aggressive—cutting off the entire block, not just the papers inside it—you get a different machine that solves a slightly different logic called WM. This shows a deep connection between the two logics, like two siblings who look different but share the same family DNA.

3. The Guarantee: The Machine Always Stops (Decidability)

One of the biggest fears in logic is that you might keep trying to prove something forever without ever finishing. The authors proved that their machine CIM is decidable.

The Analogy:
Imagine you are trying to solve a maze. Some mazes have infinite loops where you could walk forever. The authors proved that their maze (the logic IM) has a "loop detector." If the machine starts to repeat a step it has already taken, it stops and says, "Okay, we can't prove this." Because the machine always stops, we know for sure that we can determine if any statement in this logic is true or false.

4. Expanding the Game (Extensions)

Finally, the authors showed how to add new rules to this game.

If you want to say "The empty neighborhood is valid," you add a specific rule.
If you want to say "If something is true, it must be possible," you add another rule.

They proved that their machine can handle these new rules easily, just by adding a few extra instructions to the manual. They also showed how to handle a very complex rule (called K) that requires the "folders" (blocks) to hold multiple papers at once, rather than just one.

Summary of the Main Takeaways

New Meaning: They defined exactly what the logic IM means using a "neighborhood" map where you check groups of places.
New Tool: They built a proof-checking machine (CIM) that uses "blocks" and a special "pruning" cut to verify statements.
Connection: They showed that IM and a related logic (WM) are very similar; the only difference is how aggressively the machine cuts off parts of the proof.
Reliability: They proved the machine always finishes its job, so we can always decide if a statement is true or false.
Flexibility: The machine can be easily upgraded to handle more complex rules without breaking.

In short, the authors took a new, tricky logic system and gave it a solid foundation, a reliable calculator, and a clear set of instructions, proving that it is a robust and useful tool for reasoning about "must" and "might" in a cautious, constructive world.

Technical Summary: Intuitionistic Monotone Modal Logic: Proof Theory and Semantics

Problem Statement
The paper addresses a gap in the study of intuitionistic monotone modal logic, specifically the logic IM recently introduced in [27]. While classical monotone modal logic ( $M$ ) is well-studied and underpins systems like game logic and coalition logic, its intuitionistic counterparts remain underdeveloped compared to intuitionistic analogues of normal modal logics (like $K$ and $S4$ ). Existing work on intuitionistic monotone logics includes CM (completely independent modalities), WM (Wijesekera-style, allowing zero or one conclusion), and IM (derived via translation to intuitionistic first-order logic). However, IM lacked a dedicated proof-theoretic treatment, a systematic study of its extensions, and basic decidability results. Furthermore, the relationship between constructive variants (like $WM$) and intuitionistic variants (like $IM$) of monotone logic required clarification.

Methodology
The authors employ a dual approach combining semantic characterization and proof-theoretic analysis:

Semantic Characterization: The authors define constructive neighbourhood frames (derived from [11]) to provide a semantics for IM and its extensions. Unlike the intuitionistic neighbourhood models in [27], these frames utilize a preorder and a neighbourhood function mapping worlds to sets of sets of worlds. They introduce the concept of continual frames to capture the specific properties of IM. A canonical model construction using segments (pairs of prime theories and collections of sets of theories) is utilized to prove completeness.
Proof-Theoretic Analysis: The authors develop a cut-free sequent calculus, $C_{IM}$ , for IM. This calculus is adapted from the structured calculus $HM$ for classical monotone logic [14]. Key structural features include:
- Marked Formulas: Formulas are marked with input ( $\bullet$ ) or output ( $\circ$ ) polarity.
- Blocks: Structural connectives $\{ \Delta \}$ representing neighbourhood sets.
- Output Pruning ( $\downarrow$ ): A distinctive operation in the implication rule ( $\to^\bullet$ ) that removes output formulas (and empties output blocks) when moving from premises to conclusions. This operation is crucial for capturing the axiom $I3$ ( $(2\top \to 3\phi) \to 3\phi$ ).
- Extensions: The calculus is extended modularly to handle axioms $N, P, T, D,$ and $K$ by adding specific structural rules (e.g., $n, p, d, t, k$ ) while keeping logical rules unchanged, adhering to Dösen's principle.

Key Contributions

Semantic Completeness: The paper provides a sound and complete semantics for IM and its extensions with respect to classes of continual constructive neighbourhood frames. This differs from the first-order translation approach of [27] by offering a direct modal semantics that aids in understanding the sequent calculus.
Cut-Free Calculus ( $C_{IM}$ ): The authors present a terminating, cut-free sequent calculus for IM. The calculus successfully simulates the axioms of IM, particularly the interaction between the modalities via the $I3$ axiom, through the mechanism of output pruning.
Decidability: By establishing the subformula property and a loop-checking condition for the backward proof search in $C_{IM}$ , the authors prove that IM is decidable.
Relation to $WM$: The paper demonstrates a close relationship between IM and WM. By modifying the output pruning operation in $C_{IM}$ to output thinning (which removes entire output blocks rather than just emptying them), the authors derive a calculus $C_{WM}$ for WM. This allows for a re-proof that IM and WM have different 2-free fragments, while sharing the same 3-free fragment.
Extensions: The framework is extended to cover axiomatic extensions of IM (including $N, P, T, D, K$ ). For the axiom $K$ , the calculus is generalized to allow blocks containing multisets of formulas, introducing a new rule $k$ to split blocks.

Results

Completeness: Theorem 2.14 establishes that $\vdash_{IM \oplus Ax} \phi$ if and only if $\Vdash_{IM \oplus Ax} \phi$ for any subset of axioms $Ax \subseteq \{N, P, T, D, K\}$ .
Cut Elimination: Theorem 3.12 proves the admissibility of cut (and substitution rules) in $C_{IM}$ , ensuring the calculus is analytic.
Decidability: Theorem 3.14 confirms that the derivability problem for IM is decidable.
Fragment Distinction: The paper re-confirms that IM and WM differ in their 2-free fragments (specifically regarding the derivability of $((3\bot \to \bot) \to \bot) \to 3\bot$ ), while sharing the same 3-free fragment.
Soundness and Completeness for Extensions: Theorems 4.4 and 4.14 extend the soundness and completeness results to all considered axiomatic extensions, including those with the $K$ axiom.

Significance
The paper claims to fill the gap in the proof-theoretic and semantic study of IM. By providing a cut-free calculus, it establishes IM as a well-behaved logic with a decidable derivability problem. A central finding is the revelation of an analogy between constructive/intuitionistic variants of monotone logic ( $M$ ) and normal logic ( $K$ ):

Constructive variants (like $WM$) correspond to single-succedent restrictions of standard Gentzen calculi.
Intuitionistic variants (like $IM$) correspond to single-succedent restrictions of structured sequent calculi (involving blocks and specific pruning operations).

This structural insight justifies IM as a faithful intuitionistic variant of classical monotone logic. The authors note that their work opens questions regarding the generalizability of this pattern to other modal logics and the potential for extracting countermodels from failed derivations, which they identify as directions for future research.