spr_minimax_sign_deletion_monotonicity_two_two
On two cells with horizon two, the minimax value is monotone under sign deletion: for any boards b, b' : Fin 2 → Option Bool with partial_assignment_le b' b, spr_value 2 2 b' ≤ spr_value 2 2 b.
Statement
theorem spr_minimax_sign_deletion_monotonicity_two_two (b b' : Fin 2 → Option Bool)
(hle : partial_assignment_le b' b) :
spr_value 2 2 b' ≤ spr_value 2 2 b- Related work
- arXiv:2410.07623, Section 2.2
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- spr_valueThe minimax value of the sign-preservation-with-reuse game with r rounds left from a given board: the pointer (maximizer) may stop or…
- partial_assignment_leA partial assignment β is extended by γ (written β ≼ γ) if for every element e and boolean value b, β(e) = some b implies γ(e) = some b.
Read back from the Lean
For any two partial assignments $b, b' : \text{Fin } 2 \to \text{Option Bool}$, if $b'$ is a sub-assignment of $b$ (that is, partial_assignment_le b' b, meaning that for all $e \in \text{Fin } 2$ and $v \in \text{Bool}$, if $b'(e) = \text{some } v$ then $b(e) = \text{some } v$), then spr_value 2 2 b' ≤ spr_value 2 2 b.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that for two-cell boards and horizon two, the minimax value spr_value is monotone under sub-assignments (b' ≤ b). Because a board on two cells has only 3² = 9 possible configurations, the claim is a bounded statement over a finite search space of 81 pairs. The proof synthesizes a decidability instance for the sub-assignment relation, generalizes the goal to a closed universal statement over all pairs of boards, and verifies it by exhaustive computation via the decide tactic.
The sub-assignment relation b' ≤ b is decidable for boards on two cells.
The definition of partial_assignment_le b' b is ∀ (e : Fin 2) (v : Bool), b' e = some v → b e = some v. Because Fin 2 and Bool are finite types and equality on Option Bool is decidable, this bounded universal quantification is decidable. Providing this Decidable instance enables Lean's decision procedure to evaluate the relation computationally.
let _inst (b b' : Fin 2 → Option Bool) : Decidable (partial_assignment_le b' b) := inferInstanceAs (Decidable (∀ (e : Fin 2) (v : Bool), b' e = some v → b e = some v))It suffices to establish the monotonicity inequality for all pairs of boards on two cells.
Reverting the arbitrary boards b and b' along with the hypothesis hle turns the goal into a single closed universal proposition asserting that every pair of boards b, b' : Fin 2 → Option Bool with b' ≤ b satisfies spr_value 2 2 b' ≤ spr_value 2 2 b.
revert b b' hle
The monotonicity inequality spr_value 2 2 b' ≤ spr_value 2 2 b holds for all valid pairs. automation
Since there are only 3² = 9 possible boards on Fin 2, checking all 81 pairs (b, b') is a finite computation. The decide tactic evaluates the decidable proposition by exhaustive computation of the recursive minimax function spr_value, confirming that the inequality holds in every case.
decide
- The proof contains no algebraic or inductive argument; it succeeds purely by finite enumeration and evaluation of the recursive minimax function spr_value across all 3² × 3² = 81 pairs of boards on two cells.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of spr_value for n = 2 and horizon 2. -/theorem spr_minimax_sign_deletion_monotonicity_two_two (b b' : Fin 2 → Option Bool) (hle : partial_assignment_le b' b) : spr_value 2 2 b' ≤ spr_value 2 2 b := by let _inst (b b' : Fin 2 → Option Bool) : Decidable (partial_assignment_le b' b) := inferInstanceAs (Decidable (∀ (e : Fin 2) (v : Bool), b' e = some v → b e = some v)) revert b b' hle decide