🤖 AI

Common Knowledge Always, Forever

This paper introduces a polytopological PDL capable of expressing common knowledge and demonstrates that while it possesses the finite model property over closure spaces, it fails to do so over Cantor derivative spaces due to an embedding of linear temporal logic with 'past'.

Original authors: Martín Diéguez, David Fernández-Duque

Published 2026-02-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Martín Diéguez, David Fernández-Duque

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: Mapping the Mind with Geometry

Imagine you are trying to understand how people know things, how they share information, and how they reach a point where "everyone knows that everyone knows." This is the realm of Epistemic Logic (the logic of knowledge).

Usually, researchers use "maps" made of dots and arrows (called Kripke frames) to model this. But the authors of this paper, Martín Diéguez and David Fernández-Duque, decided to try a different kind of map: Topology.

Think of topology not as a math class, but as stretchy rubber sheet geometry. Instead of dots and arrows, imagine a landscape of "neighborhoods."

Standard Logic: "I know X" means there is a direct arrow from my current state to a state where X is true.
Topological Logic: "I know X" means I am standing in a "neighborhood" (a safe zone) where every single point inside that neighborhood is a place where X is true. If you can wiggle around a little bit without leaving the safe zone, you are safe.

The authors are building a new, super-powered logic system that combines these "rubber sheet" maps with Dynamic Logic (logic about actions and changes). They want to see if this new system can handle Common Knowledge (the idea that a group of people all know something, and they all know that the others know it, forever).

The Two Types of "Maps"

The paper explores two different ways to draw these rubber sheet maps, which act like two different lenses for looking at knowledge:

The "Closure" Lens (The Safe Zone):
Imagine a fuzzy cloud. If you are inside the cloud, you are safe. If you are on the edge, you are technically "inside" the cloud too. This is like Topological Closure. It's a very friendly, inclusive way of looking at knowledge.
- Result: When the authors use this lens, their logic behaves nicely. It has the Finite Model Property.
- Analogy: Think of this like a video game with a limited number of levels. No matter how complex the story gets, you can always find a solution within a finite number of steps. The computer can check every possibility and say, "Yes, this is possible" or "No, it's impossible."
The "Derivative" Lens (The Limit Point):
This is a stricter, more mathematical lens called the Cantor Derivative. Instead of asking "Is X true everywhere in this neighborhood?", it asks "Is X true right next to me, but not necessarily at me?" It looks at the edges and the limits.
- Result: This is where things get tricky. When the authors use this lens with multiple agents (people), the logic loses the Finite Model Property.
- Analogy: Imagine trying to describe a pattern that goes on forever, like a fractal. You can't draw the whole thing on a piece of paper because it never ends. In this logic, to prove something is true, you might need an infinite number of steps. A computer trying to check this would get stuck in an endless loop.

The "Alice and Bob" Experiment

To prove that the "Derivative" lens causes infinite problems, the authors set up a clever experiment with two agents, Alice and Bob.

They created a special rule (a formula) that forces Alice and Bob to live in a very specific, repeating pattern.

Imagine Alice and Bob are standing on a number line.
Alice can only see the number to her right.
Bob can only see the number to his left.
They are forced to bounce back and forth in a perfect, endless loop: $0 \to 1 \to 2 \to 3 \dots$

The authors then showed that this setup is mathematically identical to Linear Temporal Logic (LTL) with "Past".

LTL with Past is a logic used to describe time (e.g., "It will happen in the future" and "It happened in the past").
It is a known fact in computer science that LTL with "Past" cannot be solved with a finite map. It requires an infinite timeline to be accurate.

By translating this infinite time problem into their "Alice and Bob" topological logic, they proved: If you want to model common knowledge using this specific "Derivative" lens, you cannot do it with a finite map. You need an infinite universe.

Why Does This Matter?

You might ask, "So what? Who cares if a map is infinite?"

It's a Warning Sign: It tells computer scientists and AI researchers that if they try to build an AI that reasons about "common knowledge" using this specific mathematical framework, they might run into a wall. They can't just write a simple program to check if the AI's reasoning is correct, because the problem might be too big to fit in memory.
It's Not a Dead End: Even though the map is infinite, the logic is likely still decidable (meaning we can still figure out the answer, it just takes a different, more complex method). It's like knowing a maze is infinite, but having a magic compass that still lets you find the exit.
Honoring a Mentor: The paper is written as a tribute to Andreas Herzig, a giant in the field of logic. The authors are saying, "We took your favorite topics (Common Knowledge and Dynamic Logic), mixed them with our new topological ideas, and found a fascinating, slightly scary, but beautiful result."

The Takeaway

The paper is a journey into the geometry of knowledge.

Good News: If you look at knowledge as "safe zones" (Closure), everything is manageable and finite.
Bad News: If you look at knowledge as "limit points" (Derivative) with multiple people involved, the logic explodes into infinity. You can't capture the whole picture on a finite piece of paper.

The authors successfully built a bridge between the world of "rubber sheet geometry" and "computer logic," showing us exactly where the bridge holds strong and where it leads into the infinite unknown.

1. Problem Statement

The paper addresses the intersection of epistemic logic, topological semantics, and dynamic logic. Specifically, the authors aim to:

Develop a polytopological Propositional Dynamic Logic (PDL) capable of modeling multi-agent systems where knowledge is defined via topological operators (closure and Cantor derivative).
Investigate the Finite Model Property (FMP) for this logic. While many modal logics (like S4 and K4) possess the FMP, the authors seek to determine if this property holds when combining multiple agents with Cantor derivative semantics (which corresponds to weakly transitive frames) and common knowledge operators.
Resolve whether the validity problem for this logic remains decidable in general topological settings.

2. Methodology

The authors employ a combination of topological semantics, algebraic logic, and embedding techniques:

Derivative Spaces: They generalize topological spaces into derivative spaces $(X, d)$ , where $d$ is an operator satisfying normality ( $d(\emptyset)=\emptyset, d(A \cup B) = d(A) \cup d(B)$ ) and weak idempotence ( $d(d(A)) \subseteq A \cup d(A)$ ). This unifies topological closure spaces (S4) and Cantor derivative spaces (wK4).
Polytopological PDL ( $L^*$ ): They introduce a multi-agent logic where each agent $a$ $a$ is associated with a derivative operator $d_a$ $d_{a}$ . The language includes standard PDL constructs: atomic programs (agents), composition ( $;$ $;$ ), union ( $\cup$ $\cup$ ), and iteration ( $*$ $*$ ).
- Common Knowledge: Defined as $C_{a_1...a_n}\varphi = [(a_1 \cup ... \cup a_n)^*]\varphi$ .
- Semantics: The iteration operator $\langle \alpha^* \rangle$ is interpreted as the least fixed point (or least superset) satisfying the condition, which corresponds to the topological closure in closure spaces but behaves differently in derivative spaces.
Embedding Linear Temporal Logic (LTL): To prove the lack of the FMP, the authors construct an embedding of LTL with past (PLTL) into their polytopological PDL. They utilize a specific bitopological construction involving two agents ( $a$ and $b$ ) to simulate a bijective transition relation (the "next" and "previous" functions of LTL).

3. Key Contributions

A. Formalization of Polytopological PDL

The paper defines a rigorous framework for multi-agent epistemic logic over topological spaces. It distinguishes between:

Closure Spaces: Where $d_a$ is the topological closure (modeling S4 logic).
Derivative Spaces: Where $d_a$ is the Cantor derivative (modeling wK4 logic).

B. Decidability Results

The authors establish decidability for specific subclasses of derivative spaces:

Closure Spaces: The logic has the Effective Finite Model Property (FMP). The validity problem is decidable. This is proven by embedding the logic into standard PDL via a translation that replaces atomic programs $a$ with $a^*$ , leveraging the fact that closure operators are idempotent ( $c(c(A)) = c(A)$ ).
TD Topological Derivative Spaces: For spaces validating the logic K4 (where $33p \to 3p$ ), the validity problem is also decidable. The proof involves transforming models into irreflexive, transitive frames via tree unwinding, though the FMP does not hold in the strict topological sense for these spaces.

C. Negative Result: Lack of Finite Model Property

The central negative result is that Polytopological PDL does not have the Finite Model Property (FMP) over the class of general Cantor derivative spaces (even when restricted to monadic spaces, which relate to S5).

Proof Strategy: They define a formula $\text{Two}$ that forces the existence of a specific bitopological structure where two agents' derivative operators interact to create a bijective function $S = S_b \circ S_a$ .
Embedding: They translate LTL with past ( $\text{PLTL}$ ) into their logic. Since $\text{PLTL}$ over bijective frames lacks the FMP (e.g., the formula $Fq \land \neg Pq$ is satisfiable only in infinite models), the embedded formula in their PDL also lacks the FMP.

D. Complexity Implications

The embedding implies a PSPACE lower bound for the validity problem of the logic, as $\text{PLTL}$ is PSPACE-complete. The authors note that while the lack of FMP is significant, it does not imply undecidability (as $\text{PLTL}$ itself is decidable).

4. Results Summary

Feature	Closure Spaces (S4-like)	Derivative Spaces (wK4-like)
Logic Type	Standard Topological PDL	Cantor Derivative PDL
Finite Model Property	Yes (Effective)	No (in general)
Decidability	Decidable	Decidable (for TD spaces)
Key Mechanism	Embedding into standard PDL	Tree unwinding / Bisimulation
Complexity	PSPACE (implied)	PSPACE lower bound

5. Significance and Future Directions

Theoretical Impact: The paper demonstrates that adding common knowledge (via iteration) to Cantor derivative semantics breaks the Finite Model Property. This is a crucial distinction from standard epistemic logic (S5) or single-agent topological logic, where FMP often holds.
Modeling Implications: The results suggest that modeling "common knowledge" in dynamic topological settings (where agents update beliefs based on limit points rather than just closure) requires infinite models to capture certain validities.
Future Work:
- The authors conjecture that the logic remains decidable despite the lack of FMP.
- They propose exploring weakly transitive closure ( $\alpha^\sharp$ ) instead of standard iteration ( $\alpha^*$ ) to better model "Cantor derivative" versions of common knowledge.
- They suggest investigating distributed knowledge via the join of topologies and how these extensions affect decidability and model properties.

In conclusion, the paper successfully extends dynamic logic to a multi-agent topological setting, proving that while decidability is preserved for specific topological classes, the powerful combination of multiple agents and Cantor derivatives fundamentally alters the model-theoretic landscape by destroying the Finite Model Property.