AFTD Auto-Formalizing Theoretical Domains

spr_minimax_sign_deletion_monotonicity_two_two

theoremverifiedoriginal

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.

  1. 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.

    lines 5–6

      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))
  2. 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.

    line 7

      revert b b' hle
  3. 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.

    line 8

      decide

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

/-- 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
See it in the graphDiscuss this resultChallenge it