💻 computer science

Two Remarks about Game Semantics of Classical Logic

This paper presents and elucidates two unpublished remarks by Stefano Berardi concerning the game semantics of classical logic.

Original authors: Thierry Coquand

Published 2026-03-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thierry Coquand

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: Logic as a Game

Imagine that doing math isn't just about writing numbers on a page, but about playing a game between two people:

Player A (The Prover/Existential): Wants to prove a statement is true. They get to make choices.
Player B (The Skeptic/Universal): Wants to prove the statement is false. They get to challenge Player A's choices.

In Intuitionistic Logic (the standard "safe" math), once you make a move, you can't take it back. If you pick a door, you have to walk through it.
In Classical Logic (the "bold" math), Player A is allowed to backtrack. If they pick a door and realize it leads to a dead end, they can say, "Wait, I changed my mind!" and go back to the start to pick a different door.

This paper discusses two fascinating insights from the late mathematician Stefano Berardi about how this "backtracking" works.

Remark 1: The Infinite Debate and the "Time Travel" View

The Concept:
In the game, Player A can keep changing their mind to find the right answer. Usually, the game ends when someone wins. But what if the game goes on forever?

The Analogy: The Endless Chess Match
Imagine a chess match that never ends. Player A keeps moving a piece, Player B counters, Player A moves it back, Player B counters again. It goes on infinitely.

The Question: Who is responsible for this infinite loop? Is it Player A's fault for never settling, or Player B's fault for never letting them win?
Berardi's Insight: Even in an infinite game, there is a hidden pattern. If you look at the "history" of the game, you can find a specific sequence of moves that repeats forever.
The "View": Think of this as a camera recording the game. If the game goes on forever, the camera zooms out to show the "infinite view." Berardi proved that in this infinite view, you can pinpoint exactly which player is "stuck" in a loop. It's like realizing that in an endless argument, one person is the only one who keeps bringing up the same old point over and over. This helps us understand who is "blamed" for the game never ending.

Why it matters: It helps mathematicians extend these games into "transfinite" time (time beyond infinity) to understand the structure of logical proofs that never seem to finish.

Remark 2: The Trap of "Continuous" Opponents

The Concept:
This is the more surprising part. Berardi found a way to win a game even when the statement you are trying to prove is actually false.

The Analogy: The Magic Trick vs. The Slow Detective
Imagine Player A is a magician trying to prove a trick works. Player B is a detective trying to catch them.

The Rule: The detective (Player B) is "continuous." This means they can only look at a finite amount of information at a time. They can't see the whole future; they can only check a few steps ahead.
The Trap: Player A has a strategy to keep changing their mind (backtracking) so fast that the detective always sees a "valid" move, even though Player A is actually lying.
The False Formula: The paper gives an example of a statement that is mathematically false (like saying "There is a function that is always 1, but also sometimes 0").
- Player A's Strategy: They start by saying the function is always 1. The detective checks a number (say, 0). Player A says, "Oops, I changed my mind, at 0 it's actually 0!"
- The detective checks the next number (say, 1). Player A says, "Wait, at 1 it's 0 too!"
- Because the detective can only check one number at a time, Player A can always update their story just before the detective checks that specific number. The detective never catches the lie because they can't see the whole infinite list of changes at once.

The Twist:
If the detective plays "fairly" (using infinite resources or checking everything at once), they would win immediately. But because the detective is limited to checking things step-by-step (continuity), Player A can trick them into thinking a lie is true.

The Lesson:
This shows that continuity alone isn't enough to define what is "real" in math. Just because you can win a game against a slow, step-by-step opponent doesn't mean your statement is actually true. It means you are just better at playing the game of "changing your mind" than the opponent is at catching you.

Summary: What Did We Learn?

Infinite Games: Even if a logical debate goes on forever, we can mathematically determine who is "responsible" for the infinite loop by looking at the pattern of their moves.
The Illusion of Truth: You can construct a winning strategy for a false statement if your opponent is limited to checking things one by one. This teaches us that "winning a game" against a limited opponent doesn't always mean you found the truth; it might just mean you found a loophole in how they play.

The Human Element:
The paper is a tribute to Stefano Berardi. It's like a student writing a letter to a beloved teacher, saying: "You saw these deep patterns in the game of logic that we hadn't noticed yet. Here is what you taught us, and here is why it still matters today." It reminds us that in math, sometimes the most interesting things happen when we look at the "infinite" or the "impossible."

Technical Summary: Two Remarks about Game Semantics of Classical Logic

Author: Thierry Coquand
Context: A tribute to Stefano Berardi, analyzing two of his unpublished remarks regarding game semantics for classical logic.

1. Problem Statement

The paper addresses the theoretical foundations of game semantics for classical logic, specifically within the context of modified realizability and cut-elimination. While game semantics (where logical formulas are games between two players, $\exists$ loise and $\forall$ belard) successfully models intuitionistic logic via winning strategies, extending this to classical logic requires allowing backtracking (changing one's mind).

The core problems investigated are:

How to formally characterize infinite interaction sequences in classical game semantics and determine which player is responsible for an infinite debate (non-termination).
Whether the "continuity" argument (where an opponent uses only finite information) is sufficient to characterize realizability semantics for classical logic. Specifically, does the existence of a winning strategy against all continuous opponents guarantee the validity of a formula?

2. Methodology

Coquand employs game-theoretic semantics on an infinitary propositional calculus.

The Game Model: A perfect information game between $\exists$ loise (existential) and $\forall$ belard (universal). Unlike intuitionistic games, $\exists$ loise is permitted to backtrack (retract a previous choice and play a new one) based on information revealed by $\forall$ belard.
Interaction Sequences: The paper utilizes a formal structure called an interaction sequence, defined by a pair $(V, \phi)$ , where $\phi(n)$ indicates which previous move the current move $n$ responds to. This structure captures the "view" of the game at any stage.
Strategy Analysis: The author analyzes specific strategies for $\exists$ loise involving the updating of functions (e.g., in countable choice) and compares them against strategies for $\forall$ belard.
Counter-Examples: The methodology involves constructing specific "false" formulas that admit winning strategies against continuous opponents to test the limits of realizability interpretations.

3. Key Contributions and Results

Remark 1: Transfinite Interaction Sequences and Infinite Debates

Context: Previous work established that infinite interaction sequences imply a specific structural property (a "nest" of definite segments).
Berardi's Insight: Coquand refines this using a classical argument to prove Theorem 1: In any infinite interaction sequence, there exists a unique infinite sequence of indices $n_k$ such that $n_k + 1 = \phi(n_{k+1})$ and the segments $S(n_k)$ partition the interval $[0, \omega[$ .
Significance:
- This uniqueness identifies exactly one player responsible for the infinite debate.
- It allows the definition of a "view at stage $\omega$ " ( $V(\omega)$ ), enabling the extension of interaction sequences transfinitely.
- This provides a rigorous geometric analysis of non-termination, distinguishing it from Gentzen's cut-elimination bounds by focusing on the level of backtracking.

Remark 2: The Insufficiency of Continuity for Realizability

Context: In modified realizability for classical logic (specifically $HA^\omega$ with countable choice), a strategy for $\exists$ loise is considered valid if it wins against any "continuous" opponent (one who uses only finite information about the function).
The Counter-Example: Berardi pointed out a false formula in $HA^\omega$ $H A^{ω}$ :
$\bigvee_f \bigwedge_x \bigvee_y (f(x) = 0 \land f(y) \neq 0)$
- Strategy A1 ( $\exists$ loise): $\exists$ loise plays a function $f$ that is initially all 1s. If $\forall$ belard picks an $x$ , $\exists$ loise backtracks and updates $f(x)$ to 0. If $\forall$ belard picks a new $x$ , $\exists$ loise updates again.
- Outcome: If $\forall$ belard plays continuously, they must eventually pick an $x < n$ (where $n$ is the current step), allowing $\exists$ loise to win. Thus, $\exists$ loise has a winning strategy against all continuous opponents.
- The Paradox: The formula is logically false. Furthermore, there exists a strategy B1 for the negation of the formula. When A1 and B1 interact, they generate an infinite debate (an infinite sequence of function updates) without termination.
Result: The existence of a winning strategy against continuous opponents is insufficient to characterize realizability semantics. A formula can be "realizable" in the sense of beating continuous opponents yet be false and lack a cut-elimination (termination) proof.

Comparison with Soloviev's Work:
Coquand draws a parallel to S. Soloviev's work involving the Ackermann function. There, a stronger player (with more computational resources) can force a weaker player (restricted to primitive recursive strategies) to "believe" a false statement. This reinforces the idea that asymmetry in resources can lead to the validation of false formulas in game semantics.

4. Significance

Refinement of Termination Proofs: The first remark provides a deeper structural understanding of infinite debates, offering a precise mechanism to assign responsibility for non-termination and extend game semantics into the transfinite.
Limits of Continuity Arguments: The second remark is a critical negative result. It demonstrates that continuity arguments alone cannot characterize the computational content of classical logic. A strategy beating all continuous opponents does not guarantee the formula is true or that a cut-free proof exists.
Implications for Proof Theory: This clarifies the relationship between game semantics and cut-elimination. While cut-elimination corresponds to the termination of debates, the existence of a winning strategy against a specific class of opponents (continuous ones) does not automatically imply termination if the opponent is allowed to be "stronger" or if the formula is fundamentally false.
Legacy of Berardi: The paper highlights Stefano Berardi's ability to identify subtle flaws and extensions in game semantics that bridge the gap between constructive interpretations and classical logic, influencing modern research in type theory and realizability.

In conclusion, Coquand uses Berardi's insights to demonstrate that while game semantics is a powerful tool for classical logic, the criteria for "validity" (winning strategies) must be carefully distinguished from "truth" and "termination," particularly when dealing with infinite interactions and resource asymmetries.