🔢 mathematics

Intuitionistic K is a Bisimulation-Invariant Fragment of Intuitionistic First-Order Logic

This paper establishes that the intuitionistic modal logic IK is precisely the bisimulation-invariant fragment of intuitionistic first-order logic by defining IK-bisimulation, proving a Hennessy-Milner-style characterization, and developing corresponding model-theoretic tools such as intuitionistic analogues of Łoś's Theorem and countable saturation.

Original authors: Jim de Groot, João Marcos, Rodrigo Stefanes

Published 2026-07-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jim de Groot, João Marcos, Rodrigo Stefanes

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: Finding the "Essence" of a Logic

Imagine you have two different languages for describing the world:

The Simple Language (Modal Logic IK): This is like a set of flashcards. Each card has a simple rule, like "If you are here, you can see that," or "It is possible that." It's great for quick, local observations but can't describe complex, detailed relationships between many things at once.
The Complex Language (Intuitionistic First-Order Logic): This is like a massive, detailed encyclopedia. It can describe specific people, their relationships, and how those relationships change over time. It is incredibly powerful but can be overwhelming.

The Main Question: The authors ask: Is there a specific part of the "Encyclopedia" that is exactly the same as the "Flashcards"?

They prove that Yes, there is. The logic they call IK (Intuitionistic K) is exactly the part of the complex encyclopedia that cares only about the "shape" of the world, not the specific details. If two worlds look the same in terms of their structure (even if they have different names for things), the Flashcards (IK) can't tell them apart.

The Key Concept: "Bisimulation" (The Twin Test)

To understand the paper, you need to understand Bisimulation.

Imagine you are a detective trying to tell if two different cities are "structurally identical."

City A has a park, a library, and a coffee shop.
City B has a garden, a bookshop, and a cafe.

If you can walk through City A and, for every street you take, find a matching street in City B that leads to a similar-looking place, and vice versa, then the two cities are bisimilar. They are twins in terms of their layout.

In the world of logic, if two "worlds" (or states) are bisimilar, they are indistinguishable to the "Flashcard" logic (IK). The paper proves that IK is the only logic that respects this Twin Test. If a sentence in the complex encyclopedia changes its meaning just because you swapped the names of the cities (but kept the layout the same), then that sentence cannot be written in the Flashcard language.

The Journey: How They Proved It

The authors didn't just guess this; they built a bridge between the two languages using some heavy mathematical machinery. Here is how they did it, step-by-step:

1. Building the Bridge (The Translation)

First, they showed how to translate every "Flashcard" sentence into the "Encyclopedia" language.

Example: The Flashcard says "It is possible to go to a place where it is raining."
Translation: The Encyclopedia says "There exists a person $y$ such that $x$ can go to $y$ , and at $y$ , it is raining."

2. The "Twin Test" for Logic (Hennessy-Milner Theorem)

They defined a specific set of rules for what counts as a "Twin" (an IK-bisimulation) in this specific type of logic. They proved that if two worlds are twins according to these rules, they will always agree on every Flashcard sentence.

The Catch: In standard logic, "twins" are usually defined very strictly. The authors had to invent a slightly looser definition of twins specifically for this Intuitionistic logic. If they used the strict standard definition, the logic would break. It's like realizing that for these specific cities, you don't need the coffee shops to be in the exact same spot, just that they are reachable in a similar way.

3. The "Magic Mirror" (Model Theory Tools)

To prove the reverse (that only the Flashcard sentences respect the Twin Test), they had to use some advanced tools from the "Encyclopedia" side. They treated the logic like a science experiment:

The Ultrafilter Product (The "Super-Model"): Imagine you take thousands of different versions of a city, mix them together, and create one "Super-City" that contains the average features of all of them. The authors proved that this Super-City behaves exactly like the original cities regarding the Flashcard rules. This is their version of Łoś's Theorem, a famous rule in logic that says "What is true in most parts is true in the whole."
Saturation (The "Perfect City"): They created a "Perfect City" (an $\omega$ -saturated model) that is so detailed and complete that it can represent every possible scenario. They showed that if two Perfect Cities are twins, they are indistinguishable.

4. The Final Conclusion

By combining these tools, they showed:

If a sentence is in the Flashcard language (IK), it cannot tell the difference between two Twin cities.
If a sentence in the Encyclopedia cannot tell the difference between two Twin cities, it must be a Flashcard sentence (or equivalent to one).

Why This Matters (According to the Paper)

The paper doesn't talk about building apps or fixing computers. Instead, it solves a theoretical puzzle in mathematics and computer science logic.

It defines the limits: It tells us exactly what Intuitionistic Modal Logic (IK) is capable of. It is the "structural" part of the logic.
It connects two worlds: It proves that the simple, structural way of thinking about the world (Modal Logic) is mathematically identical to the part of the complex, detailed way of thinking (First-Order Logic) that ignores specific names and focuses only on connections.

Summary Analogy

Think of Intuitionistic First-Order Logic as a high-resolution 3D map of a forest. You can see every tree, every rock, and every path.
Think of Intuitionistic Modal Logic (IK) as a simple sketch of the forest's trails.

The paper proves that IK is the "Trail Sketch" that is perfectly preserved even if you swap the names of the trees. If you take the high-res map, rename every tree, and the paths still look the same, the sketch (IK) will look exactly the same. But if you try to write a sentence about the color of a specific tree (which isn't about the path structure), the sketch can't capture it.

The authors built the mathematical tools to prove that the "Trail Sketch" is the only thing that survives the "Name-Swapping" test.

Technical Summary: Intuitionistic K is a Bisimulation-Invariant Fragment of Intuitionistic First-Order Logic

Problem Statement
The paper addresses the characterization of the intuitionistic modal logic IK (introduced by Fischer Servi and studied by Plotkin, Stirling, Ewald, and Simpson) within the framework of model theory. While Van Benthem's celebrated theorem establishes that classical normal modal logic corresponds precisely to the bisimulation-invariant fragment of classical first-order logic, a similar intrinsic characterization for intuitionistic modal logics has remained an open challenge. Existing analogues for non-classical logics (such as bi-intuitionistic logic) often rely on classical first-order logic as the meta-language. The authors aim to prove that IK arises specifically as the bisimulation-invariant fragment of intuitionistic first-order logic (IFOL), thereby establishing a relative characterization theorem where both the object logic and the meta-logic are intuitionistic.

Methodology
The authors follow a standard path for Van Benthem-style characterizations, requiring the development of specific model-theoretic machinery adapted to the intuitionistic setting:

Semantics and Translation: The paper utilizes birelational models for IK, which consist of a poset of worlds, a valuation, and a binary relation satisfying specific frame conditions. It establishes a standard translation from IK formulas to IFOL formulas, interpreting IK as the set of modal formulas whose translations are provable in IFOL.
IK-Bisimulation: A new notion of IK-bisimulation is defined between birelational models. Unlike standard Kripke bisimulations, this definition is slightly weaker to accommodate the specific structural constraints of intuitionistic logic (specifically the interaction between the partial order $\leq$ and the modal relation $R$ ). The authors prove that IK-bisimilarity implies modal equivalence.
Model-Theoretic Extensions: To prove the converse (that bisimulation-invariant formulas are expressible in IK), the authors develop intuitionistic analogues of classical model theory tools:
- Filter Products: They define filter products (and ultraproducts) for intuitionistic first-order structures, extending the construction to handle constant symbols.
- Łoś's Theorem: An intuitionistic analogue of Łoś's Theorem is proven for these filter products, establishing that a formula holds in the product structure if and only if it holds in "almost all" component structures (relative to the ultrafilter).
- Compactness and Embeddings: Using Łoś's Theorem, they prove a compactness theorem for IFOL and demonstrate that every IFOL structure can be elementarily embedded into an ultrapower.
- Saturation: The authors introduce $\omega$ -saturation for IFOL structures and prove that every structure for a countable signature can be elementarily embedded into an $\omega$ -saturated structure. They further show that $\omega$ -saturated IFOL structures induce modally saturated birelational models.
Hennessy–Milner Property: A Hennessy–Milner-style theorem is established for modally saturated birelational models, proving that on such models, modal equivalence coincides with IK-bisimilarity.

Key Contributions and Results
The central result is Theorem 7.2, which states:

A formula $\alpha(x)$ in intuitionistic first-order logic (with one free variable) is equivalent to the standard translation of a formula in the modal language of IK if and only if it is invariant under IK-bisimulations.

The proof proceeds by:

Showing that any translation of an IK formula is bisimulation-invariant (using the Hennessy–Milner property on saturated models).
Showing that any bisimulation-invariant IFOL formula is equivalent to a translation of an IK formula. This is achieved by assuming a formula $\alpha$ is invariant, constructing a set of modal consequences (MOC), and using compactness and elementary embeddings into $\omega$ -saturated structures to show that $\alpha$ is logically equivalent to a finite conjunction of these modal translations.

Additionally, the paper provides:

A rigorous definition of IK-bisimulation that correctly captures the structural equivalence of birelational models, distinguishing it from stronger Kripke-style bisimulations.
A comprehensive development of intuitionistic model theory, including the handling of constants in filter products and the definition of elementary embeddings in the intuitionistic context.

Significance
The paper claims to provide the first intrinsic characterization of IK as a fragment of intuitionistic first-order logic, mirroring Van Benthem's theorem for classical logic. By developing the necessary intuitionistic model-theoretic tools (ultraproducts, saturation, elementary embeddings), the authors demonstrate that the correspondence between modal logic and first-order logic can be maintained entirely within an intuitionistic framework.

The authors note that this work opens avenues for further research, including:

Generalizing the results to signatures containing function symbols.
Weakening restrictions on term interpretations.
Expanding the theory of saturated models beyond the countable case.
Investigating whether the IK-bisimulation notion is robust across other intuitionistic modal logics (e.g., CK, WK, FS) or if distinct bisimulation notions are required for each variant.
Exploring the relationship between IK-bisimulations and Kripke bisimulations regarding invariance.

The work is presented as a foundational step in understanding the structural properties of intuitionistic modal logics through the lens of model theory.