Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5: the Pos CNF game is outcome-equivalent to its variant with passes and free truth values

Proved
ArcKayles192.PSPACE.lemma_5

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-gamesmaker-breakerp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1pos-cnf

Let φ\varphiφ be a Pos CNF instance and let (T,F)(T,F)(T,F) be a position: disjoint sets of variables set to true and to false, with either player to move. For every pass budget p∈Np\in\mathbb Np∈N,

TrueWins(φ,T,F,mover)  ⟺  TrueWinsVar(φ,T,F,mover,p).\mathrm{TrueWins}(\varphi,T,F,\text{mover})\iff\mathrm{TrueWinsVar}(\varphi,T,F,\text{mover},p).TrueWins(φ,T,F,mover)⟺TrueWinsVar(φ,T,F,mover,p).

That is, True wins the Pos CNF game from this position iff True wins the variant in which, in addition, the player to move may pass (at most ppp passes in total, shared by both players) or may give the selected variable either truth value.

Since both games are finite and determined, this says that the first player (the one to move) and the second player have winning strategies from the same positions in both games, which is the paper's outcome-equivalence. The proof of Claims 9 and 10 uses it to let the simulating player ignore the opponent's passes and helpful assignments.

Differences from the source:

  • reading: the variant where players can additionally pass, with no rule for an infinite run of passes → a shared pass budget p, every p ∈ ℕ; a pass costs one unit, the play ends when all variables are claimed; reason: the paper does not say who wins an infinite play of passes; in G_φ passes are the finitely many pass edges, shared by both players, so a finite shared budget is how the lemma is used; stating it for every p never fixes the budget
  • encoding: outcome-equivalent: the first player (resp. second player) wins from the same positions → for every position and either mover, TrueWins ↔ TrueWinsVar; reason: both games are finite and determined, so the mover wins iff (True moves and True wins) or (False moves and True does not win), and the second clause is the negation of the first
  • encoding: True wins if she has a winning strategy in the alternating claiming game (p.4) → PosCNF.TrueWins φ T F trueToMove by backward induction on the unclaimed variables, positions being the sets T (claimed by True) and F (claimed by False); reason: finite determined game; "False has a winning strategy" is the negation of TrueWins
Preamble
import Mathlib
import Definitions.Def_ArcKayles192_PSPACE_PosCNF
Formal statement
namespace ArcKayles192.PSPACE

/-- **Lemma 5** (p.4). The Pos CNF game is outcome-equivalent to its variant where players can
additionally pass (here from a shared budget of `p` passes, for every `p`) or assign either truth
value to the selected variable: from every position (disjoint sets `T`, `F` of variables set to
true and false, either player to move) True wins the Pos CNF game iff True wins the variant. -/
theorem lemma_5 (φ : PosCNF) (T F : Finset (Fin φ.n)) (hTF : Disjoint T F)
    (trueToMove : Bool) (p : ℕ) :
    PosCNF.TrueWins φ T F trueToMove ↔ PosCNF.TrueWinsVar φ T F trueToMove p := by sorry

end ArcKayles192.PSPACE
Source
Édouard Bonnet, Arc Kayles is PSPACE-complete, STOC 2027 submission #192 (October 2026), source.pdf SHA-256 f8b3a1c14347452b03dab2f19656aa6d2b17ba3956fefe2abc190b98ce44fc53, p.4, Lemma 5 (and the definition of outcome-equivalent just above it)
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 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