💻 computer science

Uniform Interpolation of Basic Tense Logic

This paper establishes the uniform interpolation theorem for basic tense logic by extending Albert Visser's semantic argument based on layered bisimulation, which was originally formulated for basic modal logic K.

Original authors: Katsuhiko Sano (Hokkaido University)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Katsuhiko Sano (Hokkaido University)

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: Time Traveling Logic

Imagine you are writing a story about time. In this story, you have two special tools:

The "Future Goggles" (□): When you look through these, you see everything that will happen.
The "Past Goggles" (■): When you look through these, you see everything that has happened.

This paper is about a specific type of logic called Basic Tense Logic (or "two-way modal logic"). It's the rulebook for how these two tools work together. The author, Katsuhiko Sano, wants to prove that this rulebook has a very special superpower called Uniform Interpolation.

What is "Uniform Interpolation"? (The "Secret Ingredient" Analogy)

To understand the superpower, let's play a game of "Guess the Secret."

Imagine you have a complex sentence (a formula) that says: "If it rains tomorrow, then the picnic will be cancelled."

Part A (The Cause): "It rains tomorrow."
Part B (The Effect): "The picnic is cancelled."

Now, imagine you want to explain the connection between A and B to a friend, but you are forbidden from mentioning "rain" (a specific variable). You need a "middle sentence" (an interpolant) that connects the two ideas without using the forbidden word.

Standard Interpolation: You might say, "If the weather is bad, the picnic is cancelled." This works, but the "middle sentence" changes depending on exactly how you phrase the original sentence.
Uniform Interpolation: This is the "superpower." It says: "No matter what sentence you start with, I can generate a single, perfect middle sentence that works for any conclusion you might draw, as long as you don't use the forbidden word."

It's like having a magic machine. You feed it a sentence and a word you want to hide (like "rain"). The machine instantly spits out a "universal summary" that captures everything important about the sentence except the hidden word. This summary is so good that if your original sentence implies a conclusion, this summary implies it too.

The Paper's Main Achievement

For a long time, logicians knew this "magic machine" existed for simple logic (just looking forward into the future). But they didn't know if it worked for Tense Logic (looking both forward and backward).

Sano's paper proves: Yes, the magic machine works for time-traveling logic too!

He shows that for any statement involving past and future, you can always strip out a specific detail (like a specific time or event) and get a "universal summary" that still holds true for everything else.

How Did He Prove It? (The "Bridge Builder" Analogy)

Sano didn't just guess; he built a bridge using a concept called Layered Bisimulation.

Imagine two different worlds (or timelines) that look slightly different but behave the same way regarding the rules of logic.

World A has a specific event (like "rain").
World B is a version of World A where that event is erased or changed.

To prove the "magic machine" works, Sano had to show that if you have two worlds that agree on everything except the hidden detail, you can always build a third, "Bridge World" that connects them.

This Bridge World looks like World A regarding the things you kept.
It looks like World B regarding the things you changed.

If you can always build this bridge, it proves that the "hidden detail" wasn't actually necessary to make the logic work. Therefore, a "universal summary" (the uniform interpolant) exists.

The Twist: When the Magic Fails

The paper also explores what happens when you add stricter rules to the logic. Specifically, it looks at S4, a logic where time is "reflexive" (you can stay in the same moment) and "transitive" (if A leads to B, and B leads to C, then A leads to C).

Sano proves that if you try to use this "magic machine" on this stricter version of time logic, it breaks.

The Analogy: Imagine a maze where you can loop back on yourself. If you try to summarize the maze without mentioning a specific loop, you might get stuck. The paper shows that for this specific type of time logic, you cannot always create a perfect summary that ignores a specific detail. The "Bridge" cannot always be built.

Summary of Results

The Good News: The basic logic of time (looking forward and backward) does have the "Uniform Interpolation" superpower. You can always create a summary that ignores specific details while keeping the logic valid.
The Method: The author used a visual, map-like method (layered bisimulation) to prove this, rather than just using algebraic equations. This helps us understand why the logic works by looking at how different "worlds" connect.
The Bad News: If you make the rules of time too strict (like in the logic S4), this superpower disappears. You can't always summarize the logic without mentioning the specific details you wanted to hide.

Why Does This Matter?

The paper doesn't talk about building robots or curing diseases. Instead, it's about mathematical truth. It confirms that our fundamental rules for reasoning about time are robust and flexible. It tells us exactly where the "magic" of summarizing logic works and where it hits a wall, helping logicians understand the deep structure of time and possibility.

Technical Summary: Uniform Interpolation of Basic Tense Logic

Problem Statement
The paper addresses the open problem of establishing the uniform interpolation property for basic tense logic (also known as two-way modal logic or modal logic with converse), denoted as $K_t$ . While the Craig interpolation property for $K_t$ is well-established through both proof-theoretic and semantic methods, the uniform interpolation property—which requires the existence of a "uniform interpolant" $\exists p.\phi$ for any formula $\phi$ and variable $p$ such that $\exists p.\phi$ is independent of $p$ and preserves provability relations with all $p$ -free formulas—had not been fully demonstrated for this logic. The author notes that while Visser (1996) provided a semantic argument for the uniform interpolation of basic modal logic $K$ using layered bisimulations, this result had not been extended to the tense expansion involving converse modalities.

Methodology
The paper employs a semantic approach, extending Visser's model-theoretic argument based on layered (or bounded) bisimulations to the context of tense logic. The methodology proceeds through the following steps:

Definitions and Framework: The author defines basic tense logic syntax and semantics, introducing the standard Hilbert system $H(K_t)$ and Kripke semantics with forward ( $\square$ ) and backward ( $\blacksquare$ ) modalities. The concept of layered bisimulation is adapted for tense logic, incorporating conditions for both forward ($Forth$, $Back$) and backward ( $Forth^{-1}$ , $Back^{-1}$ ) transitions, indexed by modal depth $n$ .
Bisimulation Expansion Property: A sufficient condition for a normal tense logic $\Lambda_{\mathcal{F}}$ (associated with a frame class $\mathcal{F}$ ) to possess the uniform interpolation property is formulated. This condition, termed the bisimulation expansion property, requires that for any two pointed models $(M_1, w_1)$ and $(M_2, w_2)$ in $\mathcal{F}$ that are bisimilar up to depth $n$ over a shared set of variables, there exists an intermediate model $(N, x)$ in $\mathcal{F}$ that bridges them via bisimulations over the respective variable sets.
Construction of the Intermediate Model: The core technical contribution involves proving that the class of all frames ( $\mathcal{F}_{all}$ ) possesses the bisimulation expansion property. The author constructs an intermediate model $N$ by taking the disjoint union of the two input models and adding a new "universal" state $T$ connected to all states. The relation in $N$ is defined over a product space involving the states of the original models and a "layer" index, effectively simulating the bisimulation steps required to satisfy the expansion property.
Transfer Results: The paper investigates the preservation of the uniform interpolation property under various extensions:
- Mirror Images: If a logic $\Lambda$ is invariant under the mirror image operation (swapping $\square$ and $\blacksquare$ ), the property transfers to extensions by mirror-image axioms.
- Constant Axioms: The property is preserved when adding constant formulas (formulas with no propositional variables).
- Boxdot Translation: The property is shown to transfer to the reflexive counterpart of a logic via the boxdot translation.
Counter-Example Construction: To demonstrate the limits of the property, the paper analyzes the tense expansion of the modal logic $S4$ (denoted $S4_t$ ). Using a specific model construction (an infinite path with alternating truth values for a proposition $r$ ) and a layered bisimulation argument, the author proves that $S4_t$ lacks the uniform interpolation property.

Key Contributions and Results

Main Theorem: The paper establishes that the minimal basic tense logic $K_t$ possesses the uniform interpolation property. This is achieved by proving that the class of all frames satisfies the bisimulation expansion property.
Semantic Characterization: It is demonstrated that the uniform interpolant in $K_t$ coincides with a bisimulation quantifier. Specifically, a formula $\exists p.\phi$ holds at a state if and only if there exists a bisimilar model (where $p$ is interpreted differently) in which $\phi$ holds.
Extension to Sub-logics: The uniform interpolation property is shown to hold for various extensions of $K_t$ , including those defined by constant axioms (e.g., existence of first/last moments) and mirror-image invariant extensions.
Failure in $S4_t$ : The paper proves that the tense expansion of $S4$ ( $S4_t$ ) does not have the uniform interpolation property. This result extends Ghilardi and Zawadowski's earlier findings on $S4$ to the tense setting, showing that the addition of reflexivity and transitivity axioms breaks the uniform interpolation property.
Transfer Mechanisms: The paper provides formal proofs for the transfer of the uniform interpolation property via mirror images, constant extensions, and the boxdot translation, allowing the derivation of results for logics like $K_t \oplus T_\square$ and $K_t \oplus 4_\square$ (under specific conditions).

Significance
The paper claims to resolve a significant gap in the literature regarding the meta-logical properties of basic tense logic. By extending Visser's semantic argument to the two-way modal setting, the author confirms that $K_t$ enjoys the uniform interpolation property, a result that was previously unknown despite the logic's widespread use in philosophy, computer science, and formal semantics. The work clarifies the boundary between logics that possess this strong interpolation property (like $K_t$ ) and those that do not (like $S4_t$ ), providing a robust semantic framework (layered bisimulations) for analyzing interpolation in tense logics. Furthermore, the paper suggests that the uniform interpolant in $K_t$ can be understood semantically as a temporal version of a bisimulation quantifier, offering a deeper conceptual understanding of the logic's expressive power. The results also lay the groundwork for future investigations into uniform Lyndon interpolation and the application of these techniques to multimodal and hybrid tense logics.