Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Positions of A⊸BA\multimap BA⊸B alternate

Proved
AJGames.imp_alt

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

game-semanticsonline-algorithms

For all games A,BA,BA,B, every position of A⊸BA\multimap BA⊸B alternates between Player and Opponent moves.

It follows from the tensor's alternation clause alone, without using that the positions of AAA and BBB alternate.

Preamble
import Mathlib
import Definitions.Def_AJGames_Game
import Definitions.Def_AJGames_Tensor
Formal statement
namespace AJGames

/-- **Positions of `A ⊸ B` alternate by T1 alone** (Abramsky and Jagadeesan, *Games and Full Completeness for Multiplicative Linear Logic*, J. Symbolic Logic 59(2) (1994), §3.2: `A ⊸ B := (A ⊗ B⊥)⊥`). No alternation of `A` or `B` is used.
AJ axioms used: T1 only. -/
theorem imp_alt (A B : Game) {s : List (Game.imp A B).M} (h : s ∈ (Game.imp A B).pos) :
    Alt (Game.imp A B).lab s := by sorry

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 (linear implication)
Read-back

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

Setting. Players are PPP and OOO, with  ⋅ ‾\overline{\,\cdot\,}⋅ swapping them. A game A=(MA,λA,PosA)A=(M_A,\lambda_A,\mathrm{Pos}_A)A=(MA​,λA​,PosA​) has a move type MAM_AMA​, a labelling λA:MA→{P,O}\lambda_A : M_A\to\{P,O\}λA​:MA​→{P,O}, and a set PosA\mathrm{Pos}_APosA​ of finite move sequences that contains the empty sequence, is prefix-closed, and in which every position alternates: consecutive moves have different labels. A sequence s=(m1,…,mn)s = (m_1,\dots,m_n)s=(m1​,…,mn​) alternates for a labelling λ\lambdaλ, written Altλ(s)\mathrm{Alt}_\lambda(s)Altλ​(s), when λ(mi)≠λ(mi+1)\lambda(m_i)\neq\lambda(m_{i+1})λ(mi​)=λ(mi+1​) for all 1≤i<n1\le i<n1≤i<n (vacuous for n≤1n\le 1n≤1).

The dual A⊥A^\perpA⊥ keeps moves and positions and swaps every label. For labellings λa\lambda_aλa​ on α\alphaα and λb\lambda_bλb​ on β\betaβ, write λ=[λa,λb]\lambda = [\lambda_a,\lambda_b]λ=[λa​,λb​] for the combined labelling on the disjoint union α⊔β\alpha \sqcup \betaα⊔β, and define the relation TR(m,m′)\mathrm{TR}(m,m')TR(m,m′) on α⊔β\alpha\sqcup\betaα⊔β by

TR(m,m′)  ⟺  λ(m)≠λ(m′)  and  (m,m′ lie in the same summand  or  λ(m′)=O).\mathrm{TR}(m,m') \iff \lambda(m)\neq\lambda(m') \ \text{ and }\ \bigl(m, m' \text{ lie in the same summand} \ \text{ or } \ \lambda(m') = O\bigr).TR(m,m′)⟺λ(m)=λ(m′)  and  (m,m′ lie in the same summand  or  λ(m′)=O).

For sss a sequence in α⊔β\alpha\sqcup\betaα⊔β, s↾Ls{\restriction}_Ls↾L​ and s↾Rs{\restriction}_Rs↾R​ are the subsequences of left and right moves. The tensor A⊗BA\otimes BA⊗B has moves MA⊔MBM_A\sqcup M_BMA​⊔MB​, labelling [λA,λB][\lambda_A,\lambda_B][λA​,λB​], and positions the sequences sss such that every consecutive pair satisfies TR\mathrm{TR}TR (for λA,λB\lambda_A,\lambda_BλA​,λB​), s↾L∈PosAs{\restriction}_L\in\mathrm{Pos}_As↾L​∈PosA​ and s↾R∈PosBs{\restriction}_R\in\mathrm{Pos}_Bs↾R​∈PosB​. The linear implication is

A⊸B:=(A⊗B⊥)⊥.A\multimap B := (A\otimes B^\perp)^\perp .A⊸B:=(A⊗B⊥)⊥.

Concretely, A⊸BA\multimap BA⊸B has moves MA⊔MBM_A\sqcup M_BMA​⊔MB​; its labelling sends a left move aaa to λA(a)‾\overline{\lambda_A(a)}λA​(a)​ and a right move bbb to λB(b)‾‾\overline{\overline{\lambda_B(b)}}λB​(b)​​ (i.e. λB(b)\lambda_B(b)λB​(b)); its positions are the sequences sss whose consecutive pairs satisfy TR\mathrm{TR}TR computed with λA\lambda_AλA​ and λB‾\overline{\lambda_B}λB​​, with s↾L∈PosAs{\restriction}_L\in\mathrm{Pos}_As↾L​∈PosA​ and s↾R∈PosBs{\restriction}_R\in\mathrm{Pos}_Bs↾R​∈PosB​.

Statement. For all games A,BA, BA,B and every finite sequence sss of moves of A⊸BA\multimap BA⊸B: if sss is a position of A⊸BA\multimap BA⊸B, then sss alternates for the labelling of A⊸BA\multimap BA⊸B,

s∈PosA⊸B ⟹ AltλA⊸B(s).s\in\mathrm{Pos}_{A\multimap B}\ \Longrightarrow\ \mathrm{Alt}_{\lambda_{A\multimap B}}(s).s∈PosA⊸B​ ⟹ AltλA⊸B​​(s).

The alternation is with respect to the outer labelling of A⊸BA\multimap BA⊸B (left labels flipped, right labels as in BBB), not the labelling used inside TR\mathrm{TR}TR. Sequences of length 000 or 111 alternate trivially. Note that alternation of every position is one of the conditions in the definition of a game, and A⊸BA\multimap BA⊸B is itself constructed as a game.

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