Abramsky–Jagadeesan games (finite plays) and duality
DefinitionAJGames_GameA game consists of a type of moves , a labelling of each move as a Player or an Opponent move, and a set of finite sequences of moves (the positions). The positions satisfy three conditions:
- the empty sequence is a position;
- every prefix of a position is a position;
- in every position, consecutive moves have different labels (alternation).
The dual 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.
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
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 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 . is a type with exactly two distinct elements, and , and equality on it is decidable. Nothing else is attached to or 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 and its four facts. The swap is given by and . The file proves, for all :
The first of these is registered as a simplification rule.
Alternation . Take any type (in universe ), a labelling and a finite list of elements of . Then holds when every two consecutive entries have different labels:
Since there are only two labels, the labels along the list simply alternate. The empty list and every one-element list satisfy vacuously. The first label of the list is not constrained: an alternating list may start with or with .
Game. A game consists of six fields:
- , a type of moves in universe . It may be empty, finite or infinite.
- , a labelling of each move by or . The label belongs to the move itself, not to its place in a play. Every move may carry the same label.
- , a set of finite lists of moves; its elements are called positions.
- the empty list belongs to ;
- is closed under prefixes: if and is a prefix of (an initial segment, possibly or ), then ;
- every position satisfies .
Several things are not required:
- The first move of a position need not be labelled . Positions starting with a -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 , which is a game for any and , including an empty . As a structure over universe , a game itself lives one universe higher.
Dual . The dual of a game has:
- the same moves, ;
- swapped labels, ;
- the same positions, .
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 ; these equal by the first swap fact. The dual is marked reducible, which means it unfolds freely during elaboration.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.