🔢 mathematics

The proof theory and semantics of second-order (intuitionistic) tense logic

This paper establishes the equivalence of axiomatic, proof-theoretic, and model-theoretic definitions for second-order intuitionistic tense logic, demonstrating that the diamond modality can be derived from boxes via second-order quantification and proving the completeness and cut-admissibility of a labelled sequent calculus for both intuitionistic and classical variants.

Original authors: Justus Becker, Anupam Das, Sonia Marin, Paaras Padhiar

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Justus Becker, Anupam Das, Sonia Marin, Paaras Padhiar

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

Imagine you are trying to build a perfect, unbreakable set of rules for a game of logic. Usually, in these games, you have two types of pieces: "positive" pieces (like "maybe" or "possibly") and "negative" pieces (like "must" or "necessarily"). In standard logic, you need to write down special rules for both types of pieces to make the game work.

This paper is about a new, upgraded version of this game called Second-Order Intuitionistic Tense Logic. The authors, Justus Becker and colleagues, did something clever: they showed that you don't actually need special rules for the "positive" pieces at all. You can build them entirely out of the "negative" pieces, provided you have a specific kind of game board.

Here is a breakdown of their journey using simple analogies:

1. The Magic Trick: Building "Maybe" out of "Must"

In most logic games, if you want to say "It is possible that A," you need a special symbol (let's call it a Diamond). If you want to say "It is necessary that A," you use a different symbol (a Box).

The authors discovered a magic trick. If you have a system that allows you to talk about all possible rules (this is the "Second-Order" part) and you have a way to look both forward and backward in time (the "Tense" part), you can define the Diamond using only the Box.

The Analogy: Imagine you are in a maze. Usually, you need a special map to find the "possible exits" (Diamonds). But the authors showed that if you have a map of "all possible paths" and you can look both forward and backward, you can figure out where the exits are just by looking at the "must-pass" paths (Boxes). You don't need a separate map for the exits; you can construct it from the walls.

2. The Three Ways to Describe the Game

To prove their magic trick works, the team described the game in three different languages, like describing a building as a blueprint, a 3D model, and a physical structure:

The Rulebook (Axiomatic): A list of written laws and instructions on how to move pieces.
The Map (Semantics): A visual description of the worlds and paths where the rules apply.
The Construction Kit (Proof Theory): A set of mechanical steps to build a proof, like stacking blocks to reach a goal.

The paper's biggest achievement is proving that all three descriptions are exactly the same. If a statement is true in the Rulebook, it is true on the Map, and you can build it with the Construction Kit. This is called "coincidence," and it means the system is robust and consistent.

3. The "Grand Tour" and the Safety Net

The authors used a method called Proof Search to prove their system works. Imagine you are trying to solve a maze.

The Strategy: Instead of guessing, you try to build a path from the start to the finish.
The Safety Net (Cut-Admissibility): In logic, a "Cut" is like taking a shortcut by assuming a fact is true just because you proved it earlier. The authors proved that you never need these shortcuts. You can always build the path from scratch using only the basic rules. This is a huge deal because it means the system is "clean" and reliable.

They visualized this as a "Grand Tour" (a loop in their diagrams) where they started with the Rulebook, went to the Map, built the Construction Kit, and came back to the Rulebook, proving everything matched up perfectly.

4. Two Versions of the Game

They didn't just do this for one type of logic; they did it for two:

The Intuitionistic Version: This is a stricter game where you can't assume things are true just because they aren't false. You need positive proof.
The Classical Version: This is the standard game where "not false" means "true."

They showed that their method works for both, and even explained how to translate the strict version into the standard version using a "negative translation" (a way of rewriting the rules so they fit).

5. Why This Matters (According to the Paper)

The paper doesn't claim this will fix your computer or cure a disease. Instead, it solves a deep theoretical puzzle:

It shows that complexity can be reduced. You don't need to invent new rules for "possibility" if you already have "necessity" and a way to talk about "all possibilities."
It provides a solid foundation for future logicians who want to use these rules in computer science or artificial intelligence. By proving the system is consistent and complete, they give others a safe playground to build upon.

In summary: The authors built a new, super-logical engine. They proved that you can generate all the "maybe" parts of the engine using only the "must" parts, as long as you have a time-traveling perspective. They then spent the rest of the paper proving that this engine runs perfectly, has no broken gears, and works exactly the same way whether you look at it as a list of rules, a map, or a construction project.

Technical Summary: The Proof Theory and Semantics of Second-Order (Intuitionistic) Tense Logic

Problem and Motivation
The paper addresses the foundational development of second-order tense logic over both classical and intuitionistic bases. While second-order logic is a standard tool in mathematical and computational logic, its metalogical foundations, particularly regarding proof theory and semantics, have posed significant challenges. A specific difficulty in intuitionistic modal logic is the lack of consensus on the appropriate axiomatization of the diamond modality ( $\Diamond$ ), which cannot be defined in terms of the box ( $\Box$ ) as it is in classical logic. Various proposals exist (e.g., CK, IK), but they often involve arbitrary choices of axioms.

The authors propose a unified approach using second-order quantification. A key observation is that in second-order intuitionistic logic, positive connectives can be defined from the negative fragment. Specifically, the paper demonstrates that the diamond modality (and its associated theory) can be recovered using only boxes ( $\Box$ ) and backward boxes ( $\blacksquare$ ), provided both forward and backward modalities (tense logic) are included. This allows for a definition of $\Diamond A$ as $\forall X(\Box(A \to \blacksquare X) \to X)$ , avoiding arbitrary axiomatizations.

Methodology
The authors develop three parallel definitions for second-order tense logic:

Axiomatic: Systems $Kt2$ (classical) and $IKt2$ (intuitionistic) are defined. These extend second-order propositional logic with normal modalities and adjunction axioms for tense pairs. Crucially, they include a full comprehension axiom, allowing impredicative definitions.
Semantic: The paper introduces (bi)relational semantics for the intuitionistic case and relational semantics for the classical case. These structures include a partial order (for intuitionism) and an accessibility relation. A central feature is the requirement of "comprehensivity," where the domain of sets includes the extensions of all formulas, effectively modeling the comprehension axiom. The authors also define "predicate structures" (where worlds are classical modal models) and show their equivalence to birelational structures.
Proof-Theoretic: Labelled sequent calculi ( $\ell Kt2$ and $\ell IKt2$ ) are proposed. These systems use world labels and relational atoms to internalize the semantics. For the intuitionistic case, an intermediate multi-succedent calculus ( $m\ell IKt2$ ) is introduced to facilitate proof search arguments, which is shown to be conservative over the single-succedent version.

The core technical strategy involves proving that these three definitions coincide. This is visualized as "grand tours" connecting axiomatic provability, semantic validity, and proof-theoretic derivability. The completeness proofs rely on a proof-search argument adapted from Schütte's notion of semi-valuations and Prawitz's concept of possible values, overcoming the hurdles of impredicativity.

Key Contributions and Results

Definition of Diamonds via Second-Order Quantification: The paper establishes that in the presence of tense modalities, the diamond modality is definable in second-order intuitionistic logic as $\Diamond A \iff \forall X(\Box(A \to \blacksquare X) \to X)$ . This recovers the theory of Fischer Servi and Simpson's $IK$ and Ewald's $IKt$ without arbitrary axiom choices.
Soundness and Completeness:
- Intuitionistic: The system $IKt2$ is proven sound and complete with respect to comprehensive birelational semantics (Main Theorem 3.3).
- Classical: The system $Kt2$ is proven sound and complete with respect to comprehensive relational semantics (Main Theorem 3.14).
Cut-Admissibility: The paper establishes cut-admissibility for the labelled sequent calculi $\ell Kt2$ $ℓ K t 2$ and $\ell IKt2$ $ℓ I K t 2$ (Main Theorem 4.2). This is achieved via a proof-search argument that constructs countermodels from failed proof searches.
- For the classical case, the argument adapts Schütte's semi-valuations and Prawitz's possible values to extract a relational countermodel.
- For the intuitionistic case, the argument is more complex, requiring the construction of a proof search tree (rather than a branch) to handle the partial order of Kripke models, ultimately yielding a predicate model countermodel.
Axiomatic Soundness of Labelled Proofs: The paper provides a translation from labelled proofs to axiomatic proofs (Theorem 7.1), completing the cycle of equivalences. This involves interpreting labelled polytree sequents as tense formulas and showing that each inference rule corresponds to an admissible rule in the axiomatic system.
Classical-Intuitionistic Relationship: The paper establishes that classical second-order tense logic ($Kt2$) can be embedded into the intuitionistic system ($IKt2$) via a negative translation (Theorem 8.2), similar to the Gödel-Gentzen translation.

Significance
The paper claims to provide a robust, unified foundation for second-order tense logic. By demonstrating that axiomatic, semantic, and proof-theoretic definitions coincide, it validates the chosen minimal axiomatization. The work addresses the specific challenge of defining positive modalities in an intuitionistic setting without arbitrary axioms, leveraging the expressive power of second-order quantification.

The methodology is presented as applicable to both classical and intuitionistic settings, with the intuitionistic case requiring novel technical adaptations to handle impredicativity and the structure of Kripke models. The results are significant for the metalogical study of modal logics, offering a complete proof-theoretic account (including cut-elimination) for second-order tense logic, a domain where such results were previously lacking or restricted to full semantics (which are not recursively enumerable). The paper positions itself as a contribution to the theoretical tools needed for adopting second-order modal logic in areas like knowledge representation and artificial intelligence, as noted in related works.

1. The Magic Trick: Building "Maybe" out of "Must"

2. The Three Ways to Describe the Game

3. The "Grand Tour" and the Safety Net

4. Two Versions of the Game

5. Why This Matters (According to the Paper)

More like this