Tensor , implication and par of AJ games
DefinitionAJGames_TensorThe tensor has moves with the inherited labels. A sequence is a position of when three conditions hold:
- its restriction is a position of , and is a position of ;
- consecutive moves have different labels;
- whenever two consecutive moves lie in different components, the second is an Opponent move (only Opponent switches component).
Linear implication is , and par is .
The switching rule (3) is what distinguishes the AJ tensor from Conway's sum of games.
import Mathlib
import Definitions.Def_AJGames_Game
namespace AJGames
section Tensor
universe u
variable {α β : Type u}
/-- **Tensor transition relation** (Abramsky and Jagadeesan, *Games and Full Completeness for Multiplicative Linear Logic*, J. Symbolic Logic 59(2) (1994), 543–574, §3.2, tensor product; axioms T1 (alternation) and T2 (only Opponent switches component)). Consecutive moves `m, m'` of the tensor: alternately labelled, and *if they lie in different components,
`m'` is an Opponent move* (only Opponent may switch component). -/
def TR (la : α → Pl) (lb : β → Pl) (m m' : α ⊕ β) : Prop :=
Sum.elim la lb m ≠ Sum.elim la lb m' ∧ (m.isLeft = m'.isLeft ∨ Sum.elim la lb m' = Pl.O)
/-- The restriction to the left component. -/
def projL (s : List (α ⊕ β)) : List α := s.filterMap Sum.getLeft?
/-- The restriction to the right component. -/
def projR (s : List (α ⊕ β)) : List β := s.filterMap Sum.getRight?
end Tensor
namespace Game
/-- **Tensor product** `A ⊗ B` (Abramsky and Jagadeesan, *Games and Full Completeness for Multiplicative Linear Logic*, J. Symbolic Logic 59(2) (1994), 543–574, §3.2). disjoint union of moves; positions are alternately labelled interleavings whose
restrictions are positions of `A` and `B`, in which **only Opponent may switch component**. -/
@[reducible] def tensor (A B : Game) : Game where
M := A.M ⊕ B.M
lab := Sum.elim A.lab B.lab
pos := {s | List.IsChain (TR A.lab B.lab) s ∧ projL s ∈ A.pos ∧ projR s ∈ B.pos}
nil_mem := ⟨List.isChain_nil, A.nil_mem, B.nil_mem⟩
prefix_closed := by
rintro s t hst ⟨h1, h2, h3⟩
refine ⟨h1.infix hst.isInfix, A.prefix_closed _ _ ?_ h2, B.prefix_closed _ _ ?_ h3⟩
· exact hst.filterMap Sum.getLeft?
· exact hst.filterMap Sum.getRight?
alt := fun s hs => hs.1.imp fun a b h => h.1
/-- Linear implication `A ⊸ B := (A ⊗ B⊥)⊥`. -/
@[reducible] def imp (A B : Game) : Game := (tensor A B.dual).dual
/-- Par `A ⅋ B := (A⊥ ⊗ B⊥)⊥`. -/
@[reducible] def par (A B : Game) : Game := (tensor A.dual B.dual).dual
end Game
end AJGames
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: Def_AJGames_Tensor
This file builds on the games, labels and swap of the Game file: , the swap and , and a game with moves , labelling and a prefix-closed set of alternating finite lists that contains . Throughout, and are two types in the same universe . The disjoint sum has left elements and right elements . Given labellings and , write for the combined labelling of : on left elements and on right elements.
Transition relation . For moves , the relation holds exactly when both of the following hold:
Here "same side" means both are left elements or both are right elements. In words: the labels of and differ, and a step from one side to the other is allowed only when the move arrived at, , is labelled . A step that stays on the same side only needs the labels to differ.
Projections. For a list over :
- is the list of -elements obtained by keeping the left entries of , in order, and deleting the right entries;
- does the same for the right entries.
Both projections are empty when is empty, or when has no entries on that side.
Tensor . For games and over the same universe:
- the moves are ;
- the labelling is , so each move keeps its label from its own game;
- a list is a position exactly when three conditions hold together:
- consecutive entries satisfy , that is, for every consecutive pair;
- ;
- .
The empty list is a position. Prefix closure holds because each of the three conditions passes to prefixes. Alternation of follows from the first half of .
Several things are not imposed:
- The first move of a tensor position is not required to be . If or has positions starting with a -move, the tensor can start with that move.
- The switching rule constrains only consecutive moves. It says nothing about which side the very first move is on.
- The rule allows a switch into an -move. Combined with alternation, the move before a switch is then labelled .
- If , the positions of are exactly the left-injected positions of . In those, consecutive moves only need differing labels, which 's positions already have.
The tensor is marked reducible.
Linear implication . This is defined as . Unfolded:
- the moves are ;
- a left move has label ;
- a right move has label , which equals by the involution fact;
- a list is a position exactly when:
- consecutive entries satisfy ;
- ;
- .
The first condition is stated with the inner labels: on the left and on the right. Under it, two consecutive moves must have different inner labels, which is the same as having different labels in . A step from one side to the other is allowed only when the move arrived at has inner label . For a left move this means ; for a right move it means . In both cases the move's label in is . So in , a switch of side is allowed only into a move labelled there. Again the first move is unconstrained.
Par . This is defined as . Unfolded:
- the moves are ;
- the labels are and , which equal and ;
- a list is a position exactly when consecutive entries satisfy , and .
Here a switch of side is allowed only into a move whose own label is . Both implication and par are marked reducible.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.