💻 computer science

On Modal Logics of Full Products of Neighborhood Frames

This paper defines and axiomatizes the tri-modal logics of full products of neighborhood frames validating T or D by introducing three natural neighborhood functions and demonstrating that these logics are equivalent to the fusion of three copies of the base logic augmented by a specific interaction principle called (mix).

Original authors: Rajab Aghamov (Dresden University of Technology, Dresden, Germany), Andrey Kudinov (Higher School of Modern Mathematics, MIPT, Moscow, Russia, HSE University, Moscow, Russia), Maik Thanh Nguyen (Dresd

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rajab Aghamov (Dresden University of Technology, Dresden, Germany), Andrey Kudinov (Higher School of Modern Mathematics, MIPT, Moscow, Russia, HSE University, Moscow, Russia), Maik Thanh Nguyen (Dresden University of Technology, Dresden, Germany), Jakob Piribauer (Dresden University of Technology, Dresden, Germany)

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 map out a complex city, but instead of streets and buildings, you are mapping out "possibilities" and "knowledge." In the world of logic, this is often done using Kripke frames, which are like simple maps where you can only move from one point to another if there is a direct road (a relationship) connecting them.

However, some situations are too messy for simple roads. Sometimes, a "neighborhood" isn't just a single road; it's a whole area of possibilities. This is where Neighborhood Frames come in. Instead of just saying "you can go from A to B," a neighborhood frame says, "from point A, you can consider any group of points that includes this specific area." It's a more flexible, fuzzy way of looking at logic, useful for systems that don't follow the strict rules of standard logic.

The Big Idea: Building a 3D City from 2D Maps

The authors of this paper are interested in what happens when you take two of these flexible "neighborhood maps" and combine them to make a bigger, two-dimensional grid (like a city map with North-South and East-West directions).

Usually, when you combine two maps, you get two ways to move:

Horizontal: Moving East or West (keeping your North-South position fixed).
Vertical: Moving North or South (keeping your East-West position fixed).

But the authors wanted to build a "Full Product." This is like adding a third way to move: Diagonal. You can move North and East at the same time.

So, in their new 3D logic city, every point has three types of "neighborhoods" (areas of influence):

Horizontal Neighborhoods: Areas you can reach by moving only sideways.
Vertical Neighborhoods: Areas you can reach by moving only up/down.
Product Neighborhoods: Areas you can reach by moving diagonally (sideways AND up/down).

The Rules of the Game

The paper focuses on two specific types of logic rules, which they call T and D.

Logic T (The "Reflexive" Rule): Imagine a rule that says, "If you are in a neighborhood, you must be standing inside it." You can't be looking at a neighborhood from the outside; you have to be part of it.
Logic D (The "Serial" Rule): Imagine a rule that says, "Every neighborhood must have something in it." You can't have an empty neighborhood; there must be at least one possibility.

The authors asked a big question: If we build a full 3D city using these T or D rules, what are the exact laws that govern how these three types of movement (Horizontal, Vertical, and Diagonal) interact?

The Discovery: The "Mix" Principle

In simpler logic systems (like the famous S4, which is used for topological spaces), there is a rule called (sub). It basically says: "If you can reach a destination diagonally, you can definitely reach it by going sideways first, and you can definitely reach it by going up/down first." It's a very strong rule that forces the diagonal path to be a combination of the other two.

However, the authors found that in their more flexible Neighborhood systems (specifically for rules T and D), this strong rule (sub) doesn't always hold. You can have a diagonal move that doesn't perfectly break down into a simple sideways-then-up move.

Instead, they discovered a new, slightly weaker rule they call (mix).

(mix) says: "If you can reach a destination diagonally, then you can reach it by going sideways and then up, OR by going up and then sideways."

Think of it like this:

Rule (sub): "If I can fly diagonally to the park, I can definitely walk there, and I can definitely drive there." (This is too strong for their system).
Rule (mix): "If I can fly diagonally to the park, I can definitely get there by walking then driving, OR by driving then walking." (This is the rule that actually works).

The Main Result

The paper proves two major things:

For Logic T: The complete set of rules for this 3D neighborhood city is exactly the combination of the basic rules for T, plus the new (mix) rule. They call this T ⊗ T ⊗ T + (mix).
For Logic D: Similarly, the rules for the D-based city are the basic D rules plus the (mix) rule. They call this D ⊗ D ⊗ D + (mix).

Why This Matters (In Simple Terms)

Before this paper, we knew how these rules worked for very strict, rigid systems (like S4). But the real world is often messier and less rigid. This paper fills in the gap by showing exactly how these "messier" systems behave when you combine dimensions.

They also proved that these new logical systems are decidable. In plain English, this means there is a guaranteed algorithm (a step-by-step recipe) that can tell you, for any statement in this system, whether it is true or false. You won't get stuck in an infinite loop trying to figure it out.

Summary Analogy

Imagine you have two sets of instructions for navigating a maze:

Set T: "You are always in the room you are looking at."
Set D: "Every room you look at has at least one exit."

The authors took these instructions, combined them to create a 3D maze with horizontal, vertical, and diagonal moves, and discovered that the only new rule needed to make sense of the diagonal moves is the "Mix" rule: "Diagonal moves are just combinations of horizontal-then-vertical or vertical-then-horizontal moves."

They proved that this is the only rule needed, and that you can always solve any puzzle in this new 3D maze.

Technical Summary: On Modal Logics of Full Products of Neighborhood Frames

Problem Statement
The paper addresses the characterization of the modal logics associated with "full products" of neighborhood frames. While the logic of products for Kripke frames and topological spaces (specifically for systems like $S4$ and $D4$ ) is well-understood, the behavior of full products in the context of weaker, non-normal modal logics remains less explored.

In standard Kripke semantics, the full product of two frames introduces a third accessibility relation (the synchronous relation) alongside the horizontal and vertical ones. This structure typically validates strong interaction principles such as commutation ( $\square_1 \square_2 p \leftrightarrow \square_2 \square_1 p$ ) and convergence. In contrast, neighborhood semantics, which generalizes Kripke semantics and includes topological semantics as a special case, allows for the construction of products where these interaction principles do not necessarily hold.

The specific problem tackled is determining the precise axiomatization of the full neighborhood product for the logics $T$ (reflexive) and $D$ (serial). The authors investigate the tri-modal logic generated by the class of full products of neighborhood frames validating $T$ or $D$ , equipped with three neighborhood functions: horizontal ( $\square_1$ ), vertical ( $\square_2$ ), and the product ( $\square$ ).

Methodology
The authors employ a combination of semantic analysis and completeness proofs via bounded morphisms.

Definitions and Lower Bounds:
The paper defines the full neighborhood product $X \times^+_n Y$ of two neighborhood frames $X$ and $Y$ . This structure includes horizontal and vertical neighborhood functions (derived from the component frames) and a product neighborhood function (generated by products of neighborhoods from the components).
The authors establish lower bounds for the logics $T \times^+_n T$ and $D \times^+_n D$ by identifying valid axioms. They introduce the interaction axiom $(mix) = \square p \to \square_1 \square_2 p \land \square_2 \square_1 p$ . They demonstrate that the logics $T_3^m = T \otimes T \otimes T + (mix)$ and $D_3^m = D \otimes D \otimes D + (mix)$ are contained within the logics of the respective full products.
Completeness via Infinite Trees:
To prove the upper bounds (i.e., that the product logics are contained within $T_3^m$ and $D_3^m$ ), the authors construct specific infinite Kripke frames:
- $T^{r,m}_{\omega,\omega,\omega}$ : A reflexive, infinitely branching tree with relations $R, R_1, R_2$ satisfying $R_1 \circ R_2, R_2 \circ R_1 \subseteq R$ .
- $T^{i,m}_{\omega,\omega,\omega}$ : An irreflexive counterpart.
  They prove that $T_3^m$ is sound and complete with respect to $T^{r,m}_{\omega,\omega,\omega}$ and $D_3^m$ with respect to $T^{i,m}_{\omega,\omega,\omega}$ . This relies on the Finite Model Property (FMP) of these logics, established via filtration techniques that preserve the interaction condition $R_1 \circ R_2 \cup R_2 \circ R_1 \subseteq R$ .
Neighborhood Frame Construction and Bounded Morphisms:
A critical technical hurdle is that the neighborhood frames required to falsify interaction axioms like commutation cannot be derived directly from Kripke frames (as Kripke-induced neighborhood frames preserve commutation). To overcome this, the authors construct specific neighborhood frames $N^r_\omega$ and $N^i_\omega$ based on "pseudo-infinite sequences" (sequences of natural numbers eventually becoming a special symbol $\star$ ). These frames possess neighborhoods that form infinite strictly decreasing chains, ensuring no state has a smallest neighborhood, which is necessary to break Kripke-like properties.
Finally, the authors define a surjective bounded morphism from the full product of these neighborhood frames ( $N^r_\omega \times^+_n N^r_\omega$ ) to the neighborhood frame induced by the tree $T^{r,m}_{\omega,\omega,\omega}$ . This morphism proves that any formula valid on the tree is valid on the product, establishing the upper bound.

Key Contributions and Results
The primary contribution of the paper is the exact axiomatization of the full neighborhood products for the logics $T$ and $D$ :

Theorem 1.4:
- $T \times^+_n T = T \otimes T \otimes T + (mix)$
- $D \times^+_n D = D \otimes D \otimes D + (mix)$
Here, $\otimes$ denotes the fusion of logics, and $(mix)$ is the interaction axiom $\square p \to \square_1 \square_2 p \land \square_2 \square_1 p$ .
Distinction from Topological Semantics:
The paper highlights a crucial divergence between topological semantics and general neighborhood semantics. In topological semantics (which corresponds to reflexive frames), the axiom $(sub) = \square p \to \square_1 p \land \square_2 p$ is valid on full products. The authors show that over $S4 \otimes S4 \otimes S4$ , $(sub)$ and $(mix)$ are equivalent. However, for the weaker serial logic $D$ , $(sub)$ is not valid on full neighborhood products. The paper provides a counterexample (adapting a Kripke frame example to neighborhood semantics) showing that $(sub) \notin D \times^+_n D$ , whereas $(mix)$ remains valid.
Decidability:
By establishing the Finite Model Property for the resulting logics $T_3^m$ and $D_3^m$ , the authors conclude that these logics are decidable.

Significance
The paper extends known product results for $S4$ and $D4$ to weaker systems ( $T$ and $D$ ) within the neighborhood semantics framework. It clarifies the structural differences between full products in topological settings versus general neighborhood settings, specifically demonstrating that the reflexivity of the underlying frames is a necessary condition for the validity of the $(sub)$ axiom in full products. The work provides a complete characterization of the tri-modal logics arising from these products, filling a gap in the literature regarding the interaction of modalities in non-normal, product-based neighborhood structures. The authors note that extending these results to non-serial logics like $K$ or $K4$ remains an open direction, as the techniques used (relying on seriality) do not directly apply.