spr_value_zero_mono
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.
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.
uses
Finset.card_le_cardchange spr_sign_count b' ≤ spr_sign_count b unfold spr_sign_count apply Finset.card_le_card
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.
uses
Finset.mem_filterintro i hi rw [Finset.mem_filter] at hi ⊢ refine ⟨hi.1, ?_⟩
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.
cases h : b' i with | none => simp [h] at hi
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.
| 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
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.
/-- 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]