Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tensor A⊗BA\otimes BA⊗B, implication and par of AJ games

Definition
AJGames_Tensor

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

game-semanticsonline-algorithms

The tensor A⊗BA\otimes BA⊗B has moves MA⊔MBM_A\sqcup M_BMA​⊔MB​ with the inherited labels. A sequence sss is a position of A⊗BA\otimes BA⊗B when three conditions hold:

  1. its restriction s↾As{\restriction}As↾A is a position of AAA, and s↾Bs{\restriction}Bs↾B is a position of BBB;
  2. consecutive moves have different labels;
  3. whenever two consecutive moves lie in different components, the second is an Opponent move (only Opponent switches component).

Linear implication is A⊸B=(A⊗B⊥)⊥A\multimap B=(A\otimes B^\perp)^\perpA⊸B=(A⊗B⊥)⊥, and par is A⅋B=(A⊥⊗B⊥)⊥A\mathbin{⅋}B=(A^\perp\otimes B^\perp)^\perpA⅋B=(A⊥⊗B⊥)⊥.

The switching rule (3) is what distinguishes the AJ tensor from Conway's sum of games.

Definition code
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
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.2 (tensor product, linear implication, par)
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: Pl={P,O}\mathsf{Pl} = \{P, O\}Pl={P,O}, the swap P‾=O\overline{P} = OP=O and O‾=P\overline{O} = PO=P, and a game AAA with moves MAM_AMA​, labelling λA\lambda_AλA​ and a prefix-closed set posA\mathrm{pos}_AposA​ of alternating finite lists that contains [ ][\,][]. Throughout, α\alphaα and β\betaβ are two types in the same universe uuu. The disjoint sum α⊕β\alpha \oplus \betaα⊕β has left elements inl(a)\mathrm{inl}(a)inl(a) and right elements inr(b)\mathrm{inr}(b)inr(b). Given labellings ℓa:α→Pl\ell_a : \alpha \to \mathsf{Pl}ℓa​:α→Pl and ℓb:β→Pl\ell_b : \beta \to \mathsf{Pl}ℓb​:β→Pl, write [ℓa,ℓb][\ell_a, \ell_b][ℓa​,ℓb​] for the combined labelling of α⊕β\alpha \oplus \betaα⊕β: ℓa\ell_aℓa​ on left elements and ℓb\ell_bℓb​ on right elements.

Transition relation TR\mathrm{TR}TR. For moves m,m′∈α⊕βm, m' \in \alpha \oplus \betam,m′∈α⊕β, the relation TRℓa,ℓb(m,m′)\mathrm{TR}_{\ell_a, \ell_b}(m, m')TRℓa​,ℓb​​(m,m′) holds exactly when both of the following hold:

[ℓa,ℓb](m)≠[ℓa,ℓb](m′)and( m,m′ are on the same side    or    [ℓa,ℓb](m′)=O ).[\ell_a,\ell_b](m) \neq [\ell_a,\ell_b](m') \quad\text{and}\quad \bigl(\, m, m' \text{ are on the same side} \;\;\text{or}\;\; [\ell_a,\ell_b](m') = O \,\bigr).[ℓa​,ℓb​](m)=[ℓa​,ℓb​](m′)and(m,m′ are on the same sideor[ℓa​,ℓb​](m′)=O).

Here "same side" means both are left elements or both are right elements. In words: the labels of mmm and m′m'm′ differ, and a step from one side to the other is allowed only when the move arrived at, m′m'm′, is labelled OOO. A step that stays on the same side only needs the labels to differ.

Projections. For a list sss over α⊕β\alpha \oplus \betaα⊕β:

  • πL(s)\pi_L(s)πL​(s) is the list of α\alphaα-elements obtained by keeping the left entries of sss, in order, and deleting the right entries;
  • πR(s)\pi_R(s)πR​(s) does the same for the right entries.

Both projections are empty when sss is empty, or when sss has no entries on that side.

Tensor A⊗BA \otimes BA⊗B. For games AAA and BBB over the same universe:

  • the moves are MA⊕MBM_A \oplus M_BMA​⊕MB​;
  • the labelling is [λA,λB][\lambda_A, \lambda_B][λA​,λB​], so each move keeps its label from its own game;
  • a list sss is a position exactly when three conditions hold together:
    1. consecutive entries satisfy TRλA,λB\mathrm{TR}_{\lambda_A, \lambda_B}TRλA​,λB​​, that is, TR(si,si+1)\mathrm{TR}(s_i, s_{i+1})TR(si​,si+1​) for every consecutive pair;
    2. πL(s)∈posA\pi_L(s) \in \mathrm{pos}_AπL​(s)∈posA​;
    3. πR(s)∈posB\pi_R(s) \in \mathrm{pos}_BπR​(s)∈posB​.

The empty list is a position. Prefix closure holds because each of the three conditions passes to prefixes. Alternation of sss follows from the first half of TR\mathrm{TR}TR.

Several things are not imposed:

  • The first move of a tensor position is not required to be OOO. If AAA or BBB has positions starting with a PPP-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 OOO-move. Combined with alternation, the move before a switch is then labelled PPP.
  • If posB={[ ]}\mathrm{pos}_B = \{[\,]\}posB​={[]}, the positions of A⊗BA \otimes BA⊗B are exactly the left-injected positions of AAA. In those, consecutive moves only need differing labels, which AAA's positions already have.

The tensor is marked reducible.

Linear implication A⊸BA \multimap BA⊸B. This is defined as (A⊗B⊥)⊥(A \otimes B^\perp)^\perp(A⊗B⊥)⊥. Unfolded:

  • the moves are MA⊕MBM_A \oplus M_BMA​⊕MB​;
  • a left move aaa has label λA(a)‾\overline{\lambda_A(a)}λA​(a)​;
  • a right move bbb has label λB(b)‾‾\overline{\overline{\lambda_B(b)}}λB​(b)​​, which equals λB(b)\lambda_B(b)λB​(b) by the involution fact;
  • a list sss is a position exactly when:
    1. consecutive entries satisfy TRλA, λB‾\mathrm{TR}_{\lambda_A,\, \overline{\lambda_B}}TRλA​,λB​​​;
    2. πL(s)∈posA\pi_L(s) \in \mathrm{pos}_AπL​(s)∈posA​;
    3. πR(s)∈posB\pi_R(s) \in \mathrm{pos}_BπR​(s)∈posB​.

The first condition is stated with the inner labels: λA\lambda_AλA​ on the left and λB‾\overline{\lambda_B}λB​​ on the right. Under it, two consecutive moves must have different inner labels, which is the same as having different labels in A⊸BA \multimap BA⊸B. A step from one side to the other is allowed only when the move arrived at has inner label OOO. For a left move this means λA=O\lambda_A = OλA​=O; for a right move it means λB=P\lambda_B = PλB​=P. In both cases the move's label in A⊸BA \multimap BA⊸B is PPP. So in A⊸BA \multimap BA⊸B, a switch of side is allowed only into a move labelled PPP there. Again the first move is unconstrained.

Par A⅋BA \mathbin{⅋} BA⅋B. This is defined as (A⊥⊗B⊥)⊥(A^\perp \otimes B^\perp)^\perp(A⊥⊗B⊥)⊥. Unfolded:

  • the moves are MA⊕MBM_A \oplus M_BMA​⊕MB​;
  • the labels are λA‾‾\overline{\overline{\lambda_A}}λA​​​ and λB‾‾\overline{\overline{\lambda_B}}λB​​​, which equal λA\lambda_AλA​ and λB\lambda_BλB​;
  • a list sss is a position exactly when consecutive entries satisfy TRλA‾,λB‾\mathrm{TR}_{\overline{\lambda_A}, \overline{\lambda_B}}TRλA​​,λB​​​, πL(s)∈posA\pi_L(s) \in \mathrm{pos}_AπL​(s)∈posA​ and πR(s)∈posB\pi_R(s) \in \mathrm{pos}_BπR​(s)∈posB​.

Here a switch of side is allowed only into a move whose own label is PPP. Both implication and par are marked reducible.

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