🔢 mathematics

Intuitionistic Common Knowledge

This paper investigates the intuitionistic common knowledge logic (ICK), providing sound and complete axiomatizations and cyclic sequent calculi for various modal extensions, while establishing their finite model property, decidability, and exponential time complexity for proof-search and validity.

Original authors: Lukas Zenger

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lukas Zenger

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 figure out what a group of people knows, not just right now, but what they know about what everyone else knows, and what they know about that, forever. In the world of logic, this is called Common Knowledge.

Usually, logicians study this using "classical" logic, which assumes facts are either absolutely true or absolutely false. But this paper introduces a new way of looking at it using Intuitionistic Logic.

Here is the simple breakdown of what the paper does, using some everyday analogies:

1. The Setting: A Growing Library

Think of Intuitionistic Logic as a library that is constantly being built.

The Classical View: A book is either on the shelf (True) or it isn't (False).
The Intuitionistic View: A book might not be on the shelf yet. It's not "False" that it's there; it's just that we haven't found the proof to put it there yet. As time goes on and we gather more information, the library grows. A statement that wasn't proven yesterday might be proven today.

The author, Lukas Zenger, asks: What happens if we try to figure out "Common Knowledge" in this growing library?

2. The Characters: Mathematicians with Evolving Beliefs

The paper imagines a group of mathematicians (the "agents").

The Library (The World): Represents the total state of mathematical truth at a specific moment.
The Growth (The Order): As time passes, the library gets bigger. New theorems are added.
The Knowledge (The Agent's View): Each mathematician only knows a subset of the library. They might not know about a new theorem that just got added to the main section.
The "Triangle" Rule: The paper introduces a rule called "triangle confluence." Imagine a mathematician looking at a map of possible worlds. If the library grows (a new book is added), the mathematician's map of "what is possible" must update smoothly so they don't suddenly think a book they knew existed has vanished. It ensures their knowledge grows with the library, not against it.

3. The Problem: How to Prove Things Without Getting Stuck

In classical logic, proving "Common Knowledge" is like proving a loop: "I know X, I know you know X, I know you know I know X..." This goes on forever.

The Old Way: Previous systems used "induction" (like a ladder with a specific rule for climbing higher). This is hard to automate and can get messy.
The New Way (This Paper): The author builds a new set of rules called Cyclic Proofs.
- The Analogy: Imagine a maze. Instead of trying to draw a path that never ends, you draw a path that loops back on itself. If you can prove that the loop is "safe" (it doesn't trap you in a lie), then the whole infinite path is valid.
- The paper creates a "cyclic sequent calculus." It's like a flowchart where arrows can point back to earlier steps, creating a cycle. If the cycle follows the rules, the proof is valid.

4. The Tools: Games and Algorithms

The paper doesn't just say "this works"; it shows how to find these proofs automatically.

The Game: Imagine a game between two players: Prover (who wants to prove a statement is true) and Refuter (who wants to find a counter-example).
The Parity Game: They play a game on a board made of the logic rules. The paper shows that if Prover has a winning strategy in this game, the statement is true.
The Result: Because we know how to solve these specific types of games efficiently with computers, the paper proves that we can automate the process of finding these proofs.

5. The Big Findings

The paper achieves four main things:

New Rules: It creates a complete set of rules (axioms) for this new "Intuitionistic Common Knowledge" logic for different types of scenarios (some where agents are perfect, some where they might make mistakes).
The Looping Proof System: It introduces the cyclic proof system mentioned above, which is "analytic" (meaning it only uses pieces of the original problem, not random guesses).
Automation: It proves that a computer can search for these proofs and decide if a statement is true or false.
Speed: It calculates how long this takes. It turns out the computer can solve these problems in "Exponential Time." This is fast enough to be practical for many complex problems, though not instant.

6. The "Translation" Trick

For the most complex version of this logic (where agents are perfect and know everything they know), the author found a clever trick. They showed that you can translate a problem from the "Classical" world into this "Intuitionistic" world.

The Metaphor: It's like translating a sentence from English to French. If you can translate the sentence perfectly, and you know the French version is true, then the English version must be true too. This proves that the new Intuitionistic system is just as powerful as the old Classical one for these specific cases.

Summary

In short, this paper builds a new, more flexible way to reason about what groups of people know when their information is constantly changing. It replaces messy, infinite loops with neat, looping diagrams (cyclic proofs) and proves that computers can efficiently solve these puzzles. It bridges the gap between "what we know now" and "what we will know later" in a mathematically rigorous way.

1. Problem Statement

The paper addresses the gap in the proof theory and computational complexity of Intuitionistic Common Knowledge Logic (ICK). While classical Common Knowledge (CK) logic is well-understood, its intuitionistic counterpart—introduced by Jäger and Marti—lacks fully analytic proof systems and direct methods for automated reasoning.

Context: ICK extends Intuitionistic Propositional Logic (IPL) with knowledge modalities ( $K_a$ ) for multiple agents and a common knowledge operator ( $C$ ) defined as a greatest fixed point.
Limitations of Existing Work: Previous systems relied on non-analytic sequent calculi with explicit induction rules or unrestricted cut, making automated proof search difficult. Furthermore, extensions to standard epistemic frame conditions (S4 and S5) had not been systematically developed, and the complexity of validity checking remained largely unexplored (except for the general case, recently shown to be ExpTime-complete).
Goal: To provide sound and complete axiomatizations, analytic cyclic sequent calculi, and complexity analysis for ICK over classes of frames satisfying reflexivity, S4, and S5 conditions.

2. Methodology

The author employs a multi-faceted approach combining proof theory, model theory, and game theory:

Semantics: The logic is interpreted over birelational Kripke models consisting of an intuitionistic partial order ( $\leq$ ) representing information growth and modal accessibility relations ( $R_a$ ) for agents. A key constraint is triangle confluence ( $w \leq v \land v R_a u \implies w R_a u$ ), ensuring the persistence of truth (monotonicity) under information growth.
Axiomatization: The paper constructs Hilbert-style systems for ICK, ICKT (reflexive), ICKS4, and ICKS5. These systems are modular, extending a base system with axioms for reflexivity ( $T_a$ ), positive introspection ( $S4_a$ ), and negative introspection/classicality ( $S5_a$ , $K^c_a$ ).
Cyclic Proof Systems: To achieve analyticity (where all formulas in a proof are subformulas of the root), the author introduces cyclic sequent calculi.
- These calculi allow non-wellfounded proofs (infinite trees) which are then pruned into finite cyclic proofs containing back-edges.
- Correctness is ensured by a global correctness criterion (for non-wellfounded proofs) or a local correctness criterion (for cyclic proofs), requiring that infinite branches pass through the unfolding of common knowledge ( $C$ ) infinitely often.
- For the S5 case, which behaves classically regarding knowledge, the system requires analytic cuts (cuts restricted to the negation closure of the root formula) to maintain completeness.
Automated Reasoning via Parity Games: The proof-search problem is reduced to solving parity games.
- A two-player game is defined between a Prover (seeking a proof) and a Refuter (seeking a countermodel).
- Winning strategies for the Prover correspond to cyclic proofs.
- The game is memoryless determined, allowing the use of efficient algorithms for parity games to decide validity.
Translation: A modal variant of Kuroda's translation is developed to embed classical Common Knowledge logic over S5 ($CKS5$) into $ICKS5$, establishing a polynomial-time reduction.

3. Key Contributions

Extension to S4 and S5 Frames: The paper systematically extends ICK to reflexive, S4, and S5 frame classes, providing sound and complete Hilbert-style axiomatizations for each.
Analytic Cyclic Calculi: It introduces the first analytic cyclic sequent calculi for intuitionistic common knowledge. Unlike previous systems, these eliminate the need for explicit induction rules and unrestricted cut, ensuring that proofs are analytic.
Proof-Search Automation: The paper demonstrates that proof search in these calculi can be automated by reducing the problem to solving parity games. This provides a direct algorithmic method for constructing proofs or finding countermodels.
Complexity Bounds:
- Establishes that the validity problem for all considered logics (ICK, ICKT, ICKS4, ICKS5) is solvable in Exponential Time (ExpTime).
- Proves that the validity problem for ICKS5 is ExpTime-complete by providing a polynomial-time reduction from classical $CKS5$.
Finite Model Property: Through the construction of finite canonical models (using prime theories and negation closures), the paper proves that all considered logics possess the finite model property, implying decidability.

4. Key Results

Soundness and Completeness: The paper proves that the axiomatizations and cyclic calculi are sound and complete with respect to their respective frame classes.
- Completeness for non-wellfounded calculi is shown via a proof-search game argument (determinacy of Gale-Stewart games).
- Completeness for cyclic calculi is derived by translating non-wellfounded proofs into cyclic proofs.
- For S5, completeness is established directly via a canonical model construction with analytic cuts.
Disjunction Property: The Semantic Disjunction Property holds for ICK, ICKT, and ICKS4 (if $\phi \lor \psi$ is valid, then $\phi$ or $\psi$ is valid). However, this property fails for ICKS5, as knowledge in S5 models behaves classically (e.g., $K_a \phi \lor \neg K_a \phi$ is valid).
Interpretation: The author offers an interpretation of ICK as a logic for reasoning about knowledge over evolving information states.
- Worlds represent stages of information growth.
- Reflexivity corresponds to infallible agents (only correct proofs).
- S5 corresponds to "hyper-skeptical" agents who only trust the most basic truths (logical tautologies) and distrust any new information that might contradict their current state, leading to classical behavior.
Translation: The translation $tr(\phi)$ (prefixing formulas with $\neg\neg$ and after every modality) successfully embeds classical $CKS5$ into $ICKS5$, clarifying the relationship between classical and intuitionistic approaches.

5. Significance

Theoretical Advancement: This work fills a critical gap in the literature by providing the first fully analytic proof systems for intuitionistic common knowledge, enabling a deeper understanding of the logic's proof-theoretic structure.
Computational Feasibility: By reducing proof search to parity games, the paper provides a concrete path for implementing automated reasoning tools for intuitionistic epistemic logic, a field previously hindered by non-analytic systems.
Complexity Classification: Establishing ExpTime-completeness for ICKS5 places the logic in the same complexity class as its classical counterpart, suggesting that the constructive nature of the logic does not inherently increase computational difficulty for the S5 case.
Future Directions: The framework opens avenues for studying extensions with co-implication (bi-intuitionistic logic) to model information loss, and for extracting interpolants, which are crucial for knowledge representation and reasoning (KRR) applications.

In summary, Zenger's paper provides a comprehensive foundation for Intuitionistic Common Knowledge, bridging the gap between constructive semantics and automated reasoning through the innovative use of cyclic proofs and parity games.