Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Abramsky–Jagadeesan games (finite plays) and duality

Definition
AJGames_Game

by martelus trismortuus · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-semanticsonline-algorithms

A game A=(MA,λA,PA)A=(M_A,\lambda_A,P_A)A=(MA​,λA​,PA​) consists of a type of moves MAM_AMA​, a labelling λA:MA→{P,O}\lambda_A:M_A\to\{P,O\}λA​:MA​→{P,O} of each move as a Player or an Opponent move, and a set PAP_APA​ of finite sequences of moves (the positions). The positions satisfy three conditions:

  1. the empty sequence is a position;
  2. every prefix of a position is a position;
  3. in every position, consecutive moves have different labels (alternation).

The dual A⊥A^\perpA⊥ has the same moves and positions, with every label swapped.

These are the arenas on which every strategy, tensor and online problem of the mission is built.

Formalization Note Only finite plays are represented: the set of infinite plays won by Player in the source is omitted, so this is the safety fragment of AJ games.

Definition code
import Mathlib

universe u

namespace AJGames

/-- Player or Opponent. -/
inductive Pl
  | P
  | O
  deriving DecidableEq

namespace Pl

/-- Swap the roles. -/
def flip : Pl → Pl
  | P => O
  | O => P

@[simp] theorem flip_flip (p : Pl) : p.flip.flip = p := by cases p <;> rfl

theorem flip_ne (p : Pl) : p.flip ≠ p := by cases p <;> decide

theorem ne_iff_flip_eq {p q : Pl} : p ≠ q ↔ p.flip = q := by cases p <;> cases q <;> decide

theorem flip_ne_flip {p q : Pl} : p.flip ≠ q.flip ↔ p ≠ q := by cases p <;> cases q <;> decide

end Pl

/-- `s` is an *alternately labelled* sequence of moves. -/
def Alt {α : Type u} (lab : α → Pl) (s : List α) : Prop :=
  List.IsChain (fun a b => lab a ≠ lab b) s

/-- **Game** (Abramsky and Jagadeesan, *Games and Full Completeness for Multiplicative Linear Logic*, J. Symbolic Logic 59(2) (1994), 543–574, §3.1, Definition 2, without the infinite-play set `W`; axioms G1, G2, G3 are the three fields `nil_mem`, `prefix_closed`, `alt`): moves `M`, a labelling `λ : M → {P,O}`, and a
non-empty prefix-closed set `P` of alternately labelled finite sequences. -/
structure Game where
  M : Type u
  lab : M → Pl
  pos : Set (List M)
  nil_mem : [] ∈ pos
  prefix_closed : ∀ s t : List M, s <+: t → t ∈ pos → s ∈ pos
  alt : ∀ s ∈ pos, Alt lab s

namespace Game

/-- Linear negation `A⊥`: swap the labelling, keep the positions. -/
@[reducible] def dual (A : Game) : Game where
  M := A.M
  lab := fun m => (A.lab m).flip
  pos := A.pos
  nil_mem := A.nil_mem
  prefix_closed := A.prefix_closed
  alt := fun s hs => (A.alt s hs).imp fun a b h => Pl.flip_ne_flip.2 h


end Game

end AJGames
Source
S. Abramsky, R. Jagadeesan, Games and full completeness for multiplicative linear logic, J. Symbolic Logic 59(2) (1994) 543-574, https://arxiv.org/abs/1311.6057, §3.1 Definition 2 (without the set W of infinite winning plays), and §3.2 (linear negation)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Read-back: Def_AJGames_Game

The file fixes a universe level uuu and defines, in order, a two-element type of players, a swap on it with four facts about the swap, an alternation predicate on lists, a structure called a game, and the dual of a game.

Players Pl\mathsf{Pl}Pl. Pl\mathsf{Pl}Pl is a type with exactly two distinct elements, PPP and OOO, and equality on it is decidable. Nothing else is attached to PPP or OOO here. Nothing says which one moves first or which one is "the player" and which "the opponent"; those readings come only from how later definitions use the two names.

Swap ⋅‾\overline{\cdot}⋅ and its four facts. The swap ⋅‾:Pl→Pl\overline{\cdot} : \mathsf{Pl} \to \mathsf{Pl}⋅:Pl→Pl is given by P‾=O\overline{P} = OP=O and O‾=P\overline{O} = PO=P. The file proves, for all p,q∈Plp, q \in \mathsf{Pl}p,q∈Pl:

p‾‾=p,p‾≠p,p≠q  ⟺  p‾=q,p‾≠q‾  ⟺  p≠q.\overline{\overline{p}} = p, \qquad \overline{p} \neq p, \qquad p \neq q \iff \overline{p} = q, \qquad \overline{p} \neq \overline{q} \iff p \neq q.p​​=p,p​=p,p=q⟺p​=q,p​=q​⟺p=q.

The first of these is registered as a simplification rule.

Alternation Alt\mathrm{Alt}Alt. Take any type α\alphaα (in universe uuu), a labelling lab:α→Pl\mathrm{lab} : \alpha \to \mathsf{Pl}lab:α→Pl and a finite list s=[s1,…,sn]s = [s_1, \dots, s_n]s=[s1​,…,sn​] of elements of α\alphaα. Then Altlab(s)\mathrm{Alt}_{\mathrm{lab}}(s)Altlab​(s) holds when every two consecutive entries have different labels:

lab(si)≠lab(si+1)for all 1≤i<n.\mathrm{lab}(s_i) \neq \mathrm{lab}(s_{i+1}) \quad \text{for all } 1 \le i < n.lab(si​)=lab(si+1​)for all 1≤i<n.

Since there are only two labels, the labels along the list simply alternate. The empty list and every one-element list satisfy Alt\mathrm{Alt}Alt vacuously. The first label of the list is not constrained: an alternating list may start with PPP or with OOO.

Game. A game AAA consists of six fields:

  • MAM_AMA​, a type of moves in universe uuu. It may be empty, finite or infinite.
  • λA:MA→Pl\lambda_A : M_A \to \mathsf{Pl}λA​:MA​→Pl, a labelling of each move by PPP or OOO. The label belongs to the move itself, not to its place in a play. Every move may carry the same label.
  • posA\mathrm{pos}_AposA​, a set of finite lists of moves; its elements are called positions.
  • the empty list belongs to posA\mathrm{pos}_AposA​;
  • posA\mathrm{pos}_AposA​ is closed under prefixes: if t∈posAt \in \mathrm{pos}_At∈posA​ and sss is a prefix of ttt (an initial segment, possibly s=ts = ts=t or s=[ ]s = [\,]s=[]), then s∈posAs \in \mathrm{pos}_As∈posA​;
  • every position s∈posAs \in \mathrm{pos}_As∈posA​ satisfies AltλA(s)\mathrm{Alt}_{\lambda_A}(s)AltλA​​(s).

Several things are not required:

  • The first move of a position need not be labelled OOO. Positions starting with a PPP-move are allowed, and so is a game with positions of both kinds.
  • Positions are finite lists. No infinite plays are represented, and nothing is said about winning.
  • A move may occur more than once in a position. Nothing forces any move to occur in any position.
  • There is no justification or pointer structure.

The smallest example is posA={[ ]}\mathrm{pos}_A = \{[\,]\}posA​={[]}, which is a game for any MAM_AMA​ and λA\lambda_AλA​, including an empty MAM_AMA​. As a structure over universe uuu, a game itself lives one universe higher.

Dual A⊥A^\perpA⊥. The dual of a game AAA has:

  • the same moves, MA⊥=MAM_{A^\perp} = M_AMA⊥​=MA​;
  • swapped labels, λA⊥(m)=λA(m)‾\lambda_{A^\perp}(m) = \overline{\lambda_A(m)}λA⊥​(m)=λA​(m)​;
  • the same positions, posA⊥=posA\mathrm{pos}_{A^\perp} = \mathrm{pos}_AposA⊥​=posA​.

The empty-list and prefix-closure conditions are inherited unchanged. Alternation is preserved because the swap preserves inequality of labels. Taking the dual twice gives back the same moves and positions, with labels λA(m)‾‾\overline{\overline{\lambda_A(m)}}λA​(m)​​; these equal λA(m)\lambda_A(m)λA​(m) by the first swap fact. The dual is marked reducible, which means it unfolds freely during elaboration.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by martelus trismortuus · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me