Two Remarks about Game Semantics of Classical Logic
Thierry Coquand · 2026
Read Two Remarks about Game Semantics of Classical Logic by Thierry Coquand (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-04012.txt.
Introduction
Thierry Coquand presents two remarks of Stefano Berardi on game semantics that had not been published. The remarks concern classical logic viewed through game semantics, a setting where logical interaction is modeled as play. Coquand explains each remark, making Berardi's ideas accessible to readers. The paper thus preserves and clarifies part of Berardi's thinking on games and classical logic.
Catalog record
| CREATOR | Thierry Coquand |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16697 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.04012
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Two Remarks about Game Semantics of Classical Logic Thierry Coquand Abstract We present and explain two unpublished remarks of Stefano Berardi connected to game semantics. 1 Introduction Around 30 years ago, I had several discussions with Stefano Berardi on the topic of game semantics for classical logic, in particular connected to our work [ 3 ] . Stefano had several insightful remarks, unfortunately most of them unpublished, and the goal of this note is to report and comment on two of these remarks: 1. The first remark suggests a natural extension of the notion of views and debates [ 5 , 6 ] to transfinite interaction sequences 2. The second remark shows that the game motivation of realization semantics [ 3 ] also validates false formulae, a remark which connects to recent work [ 11 ] We first recall the main notions for the game semantics used in [ 3 ] and then present these remarks. 2 Game semantics of classical logic The semantics is defined for an infinitary propositional calculus. The formulas of this calculus are defined inductively as: (i) 0 and 1 are (atomic) formulas, and (ii) if a_{i} (i\in I) are formulas, where I is a countable set, then both \wedge_{i}a_{i} and \vee_{i}a_{i} are formulas. Note that each arithmetical formula can be represented as a formula of this infinitary propositional calculus in a natural way. Here, we regard atomic formulas as both universal and existential. We define \neg a by induction on a , using de Morgan rules. We can define intuitionistic validity, specifying the set \mathcal{V} of intuitionistically valid formulas inductively: (i) 1\in\mathcal{V} , (ii) \wedge_{i}a_{i}\in\mathcal{V} if a_{i}\in\mathcal{V} for all i and (iii) \vee_{i}a_{i}\in\mathcal{V} if a_{i}\in\mathcal{V} for some i . We can consider the formula as specifying a perfect information game and then intuitionistic validity corresponds to a winning strategy for this game. Note that we have a winning strategy for a\vee\neg a for any a , by induction on a , by a “copy-cat” strategy. We then introduce the notion of classical validity by specifying the set \mathcal{C} of classically valid formulas. \mathcal{C} is defined inductively: (i) 1\in\mathcal{C} , (ii) \wedge_{i}a_{i}\in\mathcal{C} if a_{i}\in\mathcal{C} for all i , and (iii) \vee_{i}a_{i}\in\mathcal{C} if there exists an i_{0} such that either a_{i_{0}} is 1, or a_{i_{0}} is of the form \wedge_{j}a_{i_{0}j} with a_{i_{0}j}\lor\vee_{i}a_{i}\in\mathcal{C} for all j\in J . Game theoretical semantics for this calculus is also given as a perfect information game over a formula between two players: \exists loise, who plays for existential formulas, and \forall belard, who plays for universal formulas. But the difference is now that \exists loise can backtrack. The game for a formula a is played as follows: If \exists loise (resp. \forall belard) has to play and a is atomic, then \exists loise (resp. \forall belard) wins if a is 1 (resp. 0). If a is universal of the form \wedge_{i}a_{i} , then \forall belard has to choose an i\in I and \exists loise starts the game for a_{i} . If a is existential of the form \vee_{i}a_{i} , then \exists loise chooses an i\in I and wins if a_{i} is 1, loses if a_{i} is 0. When a_{i} is universal of the form \wedge_{j}a_{ij} , \exists loise can start the game not for a_{ij} but for a_{ij}\lor\vee_{i}a_{i} after \forall belard returns a j\in J . It is only \exists loise who is allowed to change her mind and backtracks in her choice. The intuition is that \exists loise learns from the environment \forall belard, by playing in this way. For instance, if f is a function given as an oracle, the formula \vee_{x}\wedge_{y}f(x)\leqslant f(y) , stating that f takes a minimum value, is not intuitionistically valid. However \exists loise has a winning strategy for the classical game. She chooses first an arbitrary value x=0 . If \forall belard answers with a value y=x_{1} such that f(0)\leqslant f(x_{1}) , then \exists loise wins. Otherwise f(x_{1})<f(0) and \exists loise backtracks by choosing x=x_{1} . If \forall belard answers with a value y=x_{2} such that f(x_{1})\leqslant f(x_{2}) , then \exists loise wins. Otherwise f(x_{2})<f(x_{1}) and \exists loise backtracks by choosing x=x_{2} , and so on. The game has to finish eventually since we have f(x_{n})<f(x_{n-1}) . Note that \exists loise may win without having found the actual minimum for f . One main difference with Lorenzen’s approach is that we limit ourselves to \wedge\vee formulae 1 1 1 In this way, the intuitionistic strategies have a direct perfect information game interpretation. . The strategies with backtracking correspond then to cut-free proofs, and the contribution w.r.t. Lorenzen’s work is to analyse what corresponds to the process of cut-elimination . In general, we represent a formula as a \wedge\vee tree, possibly infinitely branching, with leaves being 0 or 1 . For instance: (\exists_{n}\forall_{m}\,f(n)\leqslant f(m))\rightarrow\exists_{u}\,f(u)\leqslant f(u+1) will be represented as a \wedge\vee tree: (\wedge_{n}\vee_{m}\,f(n)>f(m))\vee\vee_{u}\,f(u)\leqslant f(u+1). The strategy for \exists loise is the following, winning with at most two moves • \exists loise asks for n . • \forall belard answers n=a . • If f(a)\leqslant f(a+1) , then \exists loise takes u=a . • If f(a)>f(a+1) , then \exists loise takes m=a+1 . The strategies considered so far correspond to cut-free proofs , which describe how a proof behaves in an environment that does not change its mind. The cut-rule is interpreted as ”cooperation” between proofs. For example: the strategy A for \vee_{n}\wedge_{m}\,f(n)\leqslant f(m) interacts with the strategy B for (\wedge_{n}\vee_{m}\,f(n)>f(m))\vee\vee_{u}\,f(u)\leqslant f(u+1) to produce a proof of \vee_{u}\,f(u)\leqslant f(u+1). The cut-formula is \vee_{n}\wedge_{m}\,f(n)\leqslant f(m) . For a simple example, consider the function: f(0)=10,~f(1)=8,~f(2)=3,~f(3)=27,\ldots The interaction proceeds as follows 2 2 2 The map \varphi indicates to what moves we answer, with 0 as the start move. 1. B asks for n , with \varphi(1)=0 2. A answers n=0 , with \varphi(2)=1 3. B responds with m=1 , since f(0)>f(0+1) , with \varphi(3)=2 4. A backtracks and answers by playing n=1 , with \varphi(4)=1 5. B responds with m=2 , since f(1)>f(1+1) , with \varphi(5)=4 6. A backtracks and answers by playing n=2 , with \varphi(6)=1 7. B concludes by playing u=2 , since f(2)\leqslant f(2+1) The cut-formula, viewed as a tree, serves as the “topic of the debate.” The debate consists of: • Arguments and counter-arguments. • Two opponents who can both change their minds. • At any point, they can resume the debate from a previous point. In this example, A and B debate, learning both from this interaction, until B can produce a value for u . We can think of A as acting as the proof while B acts as a counter-proof. Note that, in this example, if e.g. f(4)=0 , it happens that the interaction stops before A finding the actual minimum of f . Gentzen’s cut-elimination corresponds to the fact that such a debate has to end eventually. In [ 5 ] , reproduced in [ 7 ] and [ 4 ] (which also gives an alternative proof of termination), we gave an argument for termination, which we believe to be essentially different from the one of Gentzen 3 3 3 For instance, F. Aschieri, a former student of Stefano Berardi, showed [ 2 ] that one could use this analysis to