AFTD Auto-Formalizing Theoretical Domains

spr_value_zero_mono

theoremverified

At horizon 0, the sign-preservation-with-reuse game value equals the sign count, which is monotone under sign deletion: if b' is a sub-board of b (partial_assignment_le b' b), then spr_value n 0 b' ≤ spr_value n 0 b.

Statement

theorem spr_value_zero_mono (n : ℕ) (b b' : Fin n → Option Bool)
    (hle : partial_assignment_le b' b) :
    spr_value n 0 b' ≤ spr_value n 0 b
Source
arXiv:2410.07623, Section 2.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • spr_sign_countThe number of signs on a board of the sign-preservation-with-reuse game with n cells, each empty or holding a plus or a minus.

Read back from the Lean

For any natural number $n$ and any two partial assignments $b, b' : \mathrm{Fin}\ n \to \mathrm{Option}\ \mathrm{Bool}$, if $b'$ is a sub-assignment of $b$ (meaning that whenever $b'(e) = \mathrm{some}\ x$ for some $e$ and $x$, we also have $b(e) = \mathrm{some}\ x$), then the 0-step SPR value of $b'$ is less than or equal to the 0-step SPR value of $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

At horizon 0, the sign-preservation game value is by definition the sign count, the number of coordinates where a board assigns a boolean value. Using Finset.card_le_card, the inequality spr_sign_count b' ≤ spr_sign_count b reduces to showing that every index assigned in b' is also assigned in b. This follows immediately from the sub-board hypothesis: whenever b' i = some val, b must assign the exact same value.

  1. It suffices to show that every index assigned a sign in b' is also assigned a sign in b.

    At horizon 0, the game values for b' and b definitionally equal their sign counts, spr_sign_count b' and spr_sign_count b. Unfolding spr_sign_count, each count is the cardinality of the subset of indices i where the board has an assignment ((b i).isSome = true). By Finset.card_le_card, the inequality between cardinalities reduces to showing that the set of assigned indices in b' is a subset of the set of assigned indices in b.

    lines 5–7

    uses Finset.card_le_card

      change spr_sign_count b' ≤ spr_sign_count b
      unfold spr_sign_count
      apply Finset.card_le_card
  2. For any index i assigned in b', it suffices to show that b i is also assigned, i.e., (b i).isSome = true.

    Let i be an arbitrary index belonging to the filtered set of assigned indices for b' (intro i hi). Rewriting with Finset.mem_filter in both the hypothesis hi and the goal, membership is equivalent to being in Finset.univ and having isSome = true. Supplying the fact that i ∈ Finset.univ via refine, it remains only to establish that (b i).isSome = true.

    lines 8–10

    uses Finset.mem_filter

      intro i hi
      rw [Finset.mem_filter] at hi ⊢
      refine ⟨hi.1, ?_⟩
  3. The case where b' i = none is ruled out by contradiction.

    We perform a case split on the value of b' i. If b' i = none, evaluating (b' i).isSome yields false, which contradicts the hypothesis hi that (b' i).isSome = true.

    lines 11–12

      cases h : b' i with
      | none => simp [h] at hi
  4. If b' i = some val, then b i is also assigned, completing the subset inclusion.

    In the remaining case where b' i = some val, the sub-board hypothesis hle (partial_assignment_le b' b) implies that b i = some val. Simplifying (b i).isSome with this fact yields true = true, closing the goal.

    lines 13–15

      | some val =>
        have h_b := hle i val h
        simp [h_b]
Finset.card_le_card
If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.

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

/-- Sign deletion monotonicity holds at horizon zero. -/theorem spr_value_zero_mono (n : ℕ) (b b' : Fin n → Option Bool)    (hle : partial_assignment_le b' b) :    spr_value n 0 b' ≤ spr_value n 0 b := by  change spr_sign_count b' ≤ spr_sign_count b  unfold spr_sign_count  apply Finset.card_le_card  intro i hi  rw [Finset.mem_filter] at hi ⊢  refine ⟨hi.1, ?_⟩  cases h : b' i with  | none => simp [h] at hi  | some val =>    have h_b := hle i val h    simp [h_b]
See it in the graphDiscuss this resultChallenge it