spr_minimax_sign_deletion_monotonicity
In the sign-preservation-with-reuse game, the minimax value is monotone under adding existing signs: for every number n of ordered cells, remaining horizon r, and boards b, b' : Fin n → Option Bool where b' is obtained from b by turning a subset of signs into empty cells (partial_assignment_le b' b), spr_value n r b' ≤ spr_value n r b.
Statement
theorem spr_minimax_sign_deletion_monotonicity (n r : ℕ) (b b' : Fin n → Option Bool)
(hle : partial_assignment_le b' b) :
spr_value n r b' ≤ spr_value n r b- Formalizes
- arXiv:2410.07623, Section 2.2
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- spr_moveThe board after the labeler empties the cells of a set R and places the sign s in the selected cell j.
Read back from the Lean
For any natural numbers $n$ and $r$, and any two partial sign assignments $b, b' : \mathrm{Fin}\ n \to \mathrm{Option}\ \mathrm{Bool}$, if $b'$ is a sub-assignment of $b$ (i.e., partial_assignment_le b' b, meaning that whenever $b'$ assigns a boolean value to an index, $b$ assigns the same boolean value to that index), then the minimax value of $b'$ at depth $r$ is at most the minimax value of $b$ at depth $r$ (spr_value n r b' ≤ spr_value n r 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 is proved by induction on the horizon r. At horizon 0, the game value is the number of signs on the board, which is monotone because b' contains a subset of the signs of b. For the inductive step with horizon k + 1, we consider the maximizer choosing an empty cell j in b'. If j is also empty in b, the opponent's worst-case deletion in b' can be compared to that in b using the maximal allowable deletion sets, establishing that the minimax value in b' is at most that in b. If j is already occupied by a sign in b, the opponent in b' can simply play that existing sign without deleting anything, yielding a sub-board of b whose value at horizon k is bounded by spr_value n (k + 1) b through induction and horizon monotonicity.
The set of valid opponent moves at cell j is nonempty.
The pair (∅, true) deletes nothing and is therefore trivially valid, as the deletion set is empty.
uses
Finset.notMem_emptysimp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] intro i hi; exact absurd hi (Finset.notMem_empty i)⟩
A pointwise condition implies the partial assignment ordering.
If for every cell i, either β(i) is none or β(i) = γ(i), then whenever β(i) = some v, β(i) cannot be none, so β(i) = γ(i) = some v.
uses
spr_minimax_sign_deletion_monotonicity_pal_of_pointwiseintro i v hv rcases h i with h1 | h1 · rw [h1] at hv; exact absurd hv (by simp) · rw [← h1]; exact hv
The number of signs is monotone under partial assignment ordering.
Since b' ≤ b, every cell assigned in b' is also assigned in b, so the set of assigned cells in b' is a subset of that in b, and the cardinality is at most that of b.
uses
spr_sign_count,Finset.card_le_card,Option.isSome_iff_existsunfold spr_sign_count apply Finset.card_le_card intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢ rw [Option.isSome_iff_exists] at hi ⊢ obtain ⟨v, hv⟩ := hi exact ⟨v, hle i v hv⟩
Deleting more cells produces a sub-assignment of deleting fewer cells.
If R ⊆ D, then any cell deleted under R is also deleted under D. At cells not deleted in D, neither is deleted in R and both agree with b; at the played cell j, both set sign s. Thus the move with deletion set D is pointwise a sub-assignment of the move with deletion set R.
uses
spr_minimax_sign_deletion_monotonicity_pal_of_pointwise,spr_move,if_neg,if_posapply spr_minimax_sign_deletion_monotonicity_pal_of_pointwise intro i simp only [spr_move] by_cases hij : i = j · subst hij; simp · simp only [if_neg hij] by_cases hiD : i ∈ D · left; simp only [if_pos hiD] · right have hiR : i ∉ R := fun h => hiD (hRD h) simp only [if_neg hiD, if_neg hiR]
Maximal deletion preserves sub-assignment ordering across boards.
For b' ≤ b, playing sign s at cell j and deleting the maximal allowable deletion set D(j, b') in b' produces a sub-assignment of doing the same with D(j, b) in b. At cell j both are some s; at other cells, any sign retained in b' must also be retained in b because the condition for deletion in b is identical on any cell where b has the same sign as b'.
uses
spr_move,if_neg,if_pos,spr_minimax_sign_deletion_monotonicity_del_setintro i v hv simp only [spr_move] at hv ⊢ by_cases hij : i = j · subst hij; simpa using hv · simp only [if_neg hij] at hv ⊢ by_cases hiD' : i ∈ spr_minimax_sign_deletion_monotonicity_del_set j b' · simp only [if_pos hiD'] at hv; exact absurd hv (by simp) · simp only [if_neg hiD'] at hv by_cases hiD : i ∈ spr_minimax_sign_deletion_monotonicity_del_set j b · exfalso have hb' : b' i = some v := hv have hb : b i = some v := hle i v hb' simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] at hiD hiD' rw [hb] at hiD rw [hb'] at hiD' exact hiD' hiD · simp only [if_neg hiD]; exact hle i v hv
Filling an already-occupied cell with its existing sign yields a sub-assignment of the original board.
If b(j) = some v, then in b' setting cell j to v with an empty deletion set gives v at j (matching b(j)), and leaves all other cells unchanged from b'. Since b' ≤ b, every other assigned cell matches b.
uses
spr_minimax_sign_deletion_monotonicity_pal_of_pointwise,spr_move,if_neg,Finset.notMem_empty,if_falseapply spr_minimax_sign_deletion_monotonicity_pal_of_pointwise intro i by_cases hij : i = j · subst hij right simp only [spr_move] exact hv.symm · simp only [spr_move, if_neg hij, Finset.notMem_empty, if_false] cases hbi : b' i with | none => left; rfl | some c => right; exact (hle i c hbi).symm
The minimax game value is non-decreasing in the remaining horizon r.
By induction on r: at r = 0, the value is spr_sign_count b, which is at most the maximum defining spr_value at horizon 1. For r = k + 1, each term in the max and sup is bounded by the corresponding term with horizon k + 2 via the inductive hypothesis.
uses
spr_value.eq_1,spr_value.eq_2,Nat.le_max_left,le_trans,Finset.sup_le,Nat.le_max_right,Finset.le_sup,Finset.le_inf',Finset.inf'_leinduction r generalizing b with | zero => rw [spr_value.eq_1, spr_value.eq_2]; exact Nat.le_max_left _ _ | succ k ih => rw [spr_value.eq_2, spr_value.eq_2] apply Nat.max_le.2 refine ⟨Nat.le_max_left _ _, ?_⟩ apply le_trans (Finset.sup_le ?_) (Nat.le_max_right _ _) intro j hj refine le_trans ?_ (Finset.le_sup hj) apply Finset.le_inf' intro p hp exact le_trans (Finset.inf'_le _ hp) (ih _)
At horizon 0, spr_value b' ≤ spr_value b.
At horizon 0, the game value is the number of signs on the board, which is monotone under b' ≤ b by spr_minimax_sign_deletion_monotonicity_sign_count_le.
uses
spr_value.eq_1,spr_minimax_sign_deletion_monotonicity_sign_count_leinduction r generalizing b b' with | zero => rw [spr_value.eq_1, spr_value.eq_1] exact spr_minimax_sign_deletion_monotonicity_sign_count_le hle
At horizon k + 1, the immediate sign count of b' is bounded by spr_value n (k + 1) b.
The sign count of b' is at most that of b, which in turn is at most spr_value n (k + 1) b as the left component of the defining maximum.
uses
spr_value.eq_2,le_trans,spr_minimax_sign_deletion_monotonicity_sign_count_le,Nat.le_max_left| succ k ih => conv_lhs => rw [spr_value.eq_2] apply Nat.max_le.2 refine ⟨?_, ?_⟩ · refine le_trans (spr_minimax_sign_deletion_monotonicity_sign_count_le hle) ?_ rw [spr_value.eq_2] exact Nat.le_max_left _ _For any cell j empty in b', if j is also empty in b, the minimax outcome at j in b' is bounded by spr_value n (k + 1) b.
When b(j) is none, player 1 can choose cell j in b. The infimum over all valid opponent responses in b' is at most the value when opponent plays the maximal deletion set D(j, b') (h1). By the induction hypothesis and move_cross_le, this is bounded by the value with D(j, b) in b (h2). In turn, D(j, b) contains every valid deletion set Rf in b, so by move_delete_le and the induction hypothesis, this is bounded by the infimum over all valid moves in b (h3). Finally, the outcome at j in b is bounded by the supremum over all empty cells in b, which is at most spr_value n (k + 1) b (h4).
uses
Finset.sup_le,spr_value.eq_2,Finset.le_inf',Finset.inf'_le,spr_minimax_sign_deletion_monotonicity_opt_set_nonempty,spr_minimax_sign_deletion_monotonicity_move_cross_le,spr_minimax_sign_deletion_monotonicity_move_delete_le,Finset.le_sup,Nat.le_max_right,le_trans· apply Finset.sup_le intro j hj by_cases hbj : b j = none · rw [spr_value.eq_2] have hB : (Finset.univ : Finset Bool).Nonempty := ⟨true, Finset.mem_univ _⟩ have h1 : (spr_minimax_sign_deletion_monotonicity_opt_set j b').inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b') (fun p => spr_value n k (spr_move b' j p.1 p.2)) ≤ (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) := by refine Finset.le_inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) ?_ intro s hs refine Finset.inf'_le (f := fun p : Finset (Fin n) × Bool => spr_value n k (spr_move b' j p.1 p.2)) (b := (spr_minimax_sign_deletion_monotonicity_del_set j b', s)) ?_ simp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] intro i hi simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] at hi exact hi have h2 : (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) ≤ (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) := by refine Finset.le_inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) ?_ intro s hs refine le_trans (Finset.inf'_le (f := fun t => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') t)) (Finset.mem_univ s)) ?_ exact ih _ _ (spr_minimax_sign_deletion_monotonicity_move_cross_le hle j s) have h3 : (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) ≤ (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) := by refine Finset.le_inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) ?_ intro p hp obtain ⟨Rf, s⟩ := p simp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] at hp have hRD : Rf ⊆ spr_minimax_sign_deletion_monotonicity_del_set j b := by intro i hi simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] exact hp i hi refine le_trans (Finset.inf'_le (f := fun t => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) t)) (Finset.mem_univ s)) ?_ exact ih _ _ (spr_minimax_sign_deletion_monotonicity_move_delete_le b j Rf (spr_minimax_sign_deletion_monotonicity_del_set j b) s hRD) have h4 : (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) ≤ max (spr_sign_count b) ((Finset.univ.filter (fun j => b j = none)).sup (fun j => (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)))) := by refine le_trans (Finset.le_sup (f := fun j' => (spr_minimax_sign_deletion_monotonicity_opt_set j' b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j' b) (fun p => spr_value n k (spr_move b j' p.1 p.2))) ?_) (Nat.le_max_right _ _) exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hbj⟩ exact le_trans h1 (le_trans h2 (le_trans h3 h4))
For any cell j empty in b', if j is already assigned in b, the minimax outcome at j in b' is bounded by spr_value n (k + 1) b.
If b(j) = some v, the opponent in b' can choose to assign v with empty deletion set. By move_none_pal, the resulting board is a sub-assignment of b. By the induction hypothesis, its value at horizon k is at most spr_value n k b. By horizon monotonicity, this is at most spr_value n (k + 1) b.
uses
le_trans,spr_minimax_sign_deletion_monotonicity_horizon_mono,spr_minimax_sign_deletion_monotonicity_move_none_pal,Finset.inf'_le,Finset.notMem_empty· obtain ⟨v, hv⟩ : ∃ v, b j = some v := by cases h : b j with | none => exact absurd h hbj | some v => exact ⟨v, rfl⟩ refine le_trans ?_ (spr_minimax_sign_deletion_monotonicity_horizon_mono k b) refine le_trans ?_ (ih _ _ (spr_minimax_sign_deletion_monotonicity_move_none_pal hle j hv)) refine Finset.inf'_le (f := fun p : Finset (Fin n) × Bool => spr_value n k (spr_move b' j p.1 p.2)) (b := (∅, v)) ?_ simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi; exact absurd hi (Finset.notMem_empty i)
Finset.notMem_empty- The empty finset has no elements
spr_sign_count- The number of assigned cells in a board
Finset.card_le_card- If s ⊆ t as finsets, then |s| ≤ |t|
Option.isSome_iff_exists- An option is some if and only if there exists a value
spr_minimax_sign_deletion_monotonicity_pal_of_pointwise- If for every cell i, β i is either none or matches γ i, then β ≤ γ in the partial assignment order
spr_move- The board resulting from playing sign s at cell j and deleting cells in R
if_neg- if c then t else e equals e when c is false
if_pos- if c then t else e equals t when c is true
if_false- if False then t else e equals e
spr_minimax_sign_deletion_monotonicity_del_set- The maximal set of cells opponent is allowed to delete when player plays at cell j
spr_value.eq_1- At horizon 0, the SPR game value is the number of assigned signs
spr_value.eq_2- At horizon r+1, the SPR game value is the maximum of the current sign count and the minimax value over valid moves
Nat.le_max_left- For natural numbers, a ≤ max a b
Nat.le_max_right- For natural numbers, b ≤ max a b
le_trans- Inequality in a preorder is transitive
Finset.sup_le- The supremum of a finset is ≤ a if every element is ≤ a
Finset.le_sup- An element of a finset is ≤ the supremum of the finset
Finset.le_inf'- A value a is ≤ the infimum of a nonempty finset if a is ≤ every element
Finset.inf'_le- The infimum of a nonempty finset is ≤ any element of the finset
spr_minimax_sign_deletion_monotonicity_opt_set_nonempty- The set of valid moves for the opponent at cell j is always nonempty
spr_minimax_sign_deletion_monotonicity_sign_count_le- The sign count is monotone under the partial assignment ordering
spr_minimax_sign_deletion_monotonicity_move_delete_le- Deleting a larger set of cells produces a smaller partial assignment
spr_minimax_sign_deletion_monotonicity_move_cross_le- A move with maximal deletion on a sub-assignment produces a sub-assignment of the corresponding move on the larger assignment
spr_minimax_sign_deletion_monotonicity_move_none_pal- Playing the existing sign of a cell with no deletions on a sub-assignment yields a sub-assignment of the original board
spr_minimax_sign_deletion_monotonicity_horizon_mono- The SPR game value is monotone in the remaining horizon r
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.
noncomputable def spr_minimax_sign_deletion_monotonicity_del_set {n : ℕ} (j : Fin n) (b : Fin n → Option Bool) : Finset (Fin n) := Finset.univ.filter (fun i => (i < j ∧ b i = some false) ∨ (j < i ∧ b i = some true))noncomputable def spr_minimax_sign_deletion_monotonicity_opt_set {n : ℕ} (j : Fin n) (b : Fin n → Option Bool) : Finset (Finset (Fin n) × Bool) := Finset.univ.filter (fun p => ∀ i ∈ p.1, (i < j ∧ b i = some false) ∨ (j < i ∧ b i = some true))lemma spr_minimax_sign_deletion_monotonicity_opt_set_nonempty {n : ℕ} (j : Fin n) (b : Fin n → Option Bool) : (spr_minimax_sign_deletion_monotonicity_opt_set j b).Nonempty := ⟨(∅, true), by simp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] intro i hi; exact absurd hi (Finset.notMem_empty i)⟩lemma spr_minimax_sign_deletion_monotonicity_pal_of_pointwise {n : ℕ} {β γ : Fin n → Option Bool} (h : ∀ i, β i = none ∨ β i = γ i) : partial_assignment_le β γ := by intro i v hv rcases h i with h1 | h1 · rw [h1] at hv; exact absurd hv (by simp) · rw [← h1]; exact hvlemma spr_minimax_sign_deletion_monotonicity_sign_count_le {n : ℕ} {b b' : Fin n → Option Bool} (hle : partial_assignment_le b' b) : spr_sign_count b' ≤ spr_sign_count b := by unfold spr_sign_count apply Finset.card_le_card intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢ rw [Option.isSome_iff_exists] at hi ⊢ obtain ⟨v, hv⟩ := hi exact ⟨v, hle i v hv⟩lemma spr_minimax_sign_deletion_monotonicity_move_delete_le {n : ℕ} (b : Fin n → Option Bool) (j : Fin n) (R D : Finset (Fin n)) (s : Bool) (hRD : R ⊆ D) : partial_assignment_le (spr_move b j D s) (spr_move b j R s) := by apply spr_minimax_sign_deletion_monotonicity_pal_of_pointwise intro i simp only [spr_move] by_cases hij : i = j · subst hij; simp · simp only [if_neg hij] by_cases hiD : i ∈ D · left; simp only [if_pos hiD] · right have hiR : i ∉ R := fun h => hiD (hRD h) simp only [if_neg hiD, if_neg hiR]lemma spr_minimax_sign_deletion_monotonicity_move_cross_le {n : ℕ} {b b' : Fin n → Option Bool} (hle : partial_assignment_le b' b) (j : Fin n) (s : Bool) : partial_assignment_le (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s) (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s) := by intro i v hv simp only [spr_move] at hv ⊢ by_cases hij : i = j · subst hij; simpa using hv · simp only [if_neg hij] at hv ⊢ by_cases hiD' : i ∈ spr_minimax_sign_deletion_monotonicity_del_set j b' · simp only [if_pos hiD'] at hv; exact absurd hv (by simp) · simp only [if_neg hiD'] at hv by_cases hiD : i ∈ spr_minimax_sign_deletion_monotonicity_del_set j b · exfalso have hb' : b' i = some v := hv have hb : b i = some v := hle i v hb' simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] at hiD hiD' rw [hb] at hiD rw [hb'] at hiD' exact hiD' hiD · simp only [if_neg hiD]; exact hle i v hvlemma spr_minimax_sign_deletion_monotonicity_move_none_pal {n : ℕ} {b b' : Fin n → Option Bool} (hle : partial_assignment_le b' b) (j : Fin n) {v : Bool} (hv : b j = some v) : partial_assignment_le (spr_move b' j ∅ v) b := by apply spr_minimax_sign_deletion_monotonicity_pal_of_pointwise intro i by_cases hij : i = j · subst hij right simp only [spr_move] exact hv.symm · simp only [spr_move, if_neg hij, Finset.notMem_empty, if_false] cases hbi : b' i with | none => left; rfl | some c => right; exact (hle i c hbi).symmlemma spr_minimax_sign_deletion_monotonicity_horizon_mono {n : ℕ} (r : ℕ) (b : Fin n → Option Bool) : spr_value n r b ≤ spr_value n (r+1) b := by induction r generalizing b with | zero => rw [spr_value.eq_1, spr_value.eq_2]; exact Nat.le_max_left _ _ | succ k ih => rw [spr_value.eq_2, spr_value.eq_2] apply Nat.max_le.2 refine ⟨Nat.le_max_left _ _, ?_⟩ apply le_trans (Finset.sup_le ?_) (Nat.le_max_right _ _) intro j hj refine le_trans ?_ (Finset.le_sup hj) apply Finset.le_inf' intro p hp exact le_trans (Finset.inf'_le _ hp) (ih _)/-- Sign deletion monotonicity of the minimax value in the SPR game (OP-1114). -/theorem spr_minimax_sign_deletion_monotonicity (n r : ℕ) (b b' : Fin n → Option Bool) (hle : partial_assignment_le b' b) : spr_value n r b' ≤ spr_value n r b := by induction r generalizing b b' with | zero => rw [spr_value.eq_1, spr_value.eq_1] exact spr_minimax_sign_deletion_monotonicity_sign_count_le hle | succ k ih => conv_lhs => rw [spr_value.eq_2] apply Nat.max_le.2 refine ⟨?_, ?_⟩ · refine le_trans (spr_minimax_sign_deletion_monotonicity_sign_count_le hle) ?_ rw [spr_value.eq_2] exact Nat.le_max_left _ _ · apply Finset.sup_le intro j hj by_cases hbj : b j = none · rw [spr_value.eq_2] have hB : (Finset.univ : Finset Bool).Nonempty := ⟨true, Finset.mem_univ _⟩ have h1 : (spr_minimax_sign_deletion_monotonicity_opt_set j b').inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b') (fun p => spr_value n k (spr_move b' j p.1 p.2)) ≤ (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) := by refine Finset.le_inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) ?_ intro s hs refine Finset.inf'_le (f := fun p : Finset (Fin n) × Bool => spr_value n k (spr_move b' j p.1 p.2)) (b := (spr_minimax_sign_deletion_monotonicity_del_set j b', s)) ?_ simp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] intro i hi simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] at hi exact hi have h2 : (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') s)) ≤ (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) := by refine Finset.le_inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) ?_ intro s hs refine le_trans (Finset.inf'_le (f := fun t => spr_value n k (spr_move b' j (spr_minimax_sign_deletion_monotonicity_del_set j b') t)) (Finset.mem_univ s)) ?_ exact ih _ _ (spr_minimax_sign_deletion_monotonicity_move_cross_le hle j s) have h3 : (Finset.univ : Finset Bool).inf' hB (fun s => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) s)) ≤ (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) := by refine Finset.le_inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) ?_ intro p hp obtain ⟨Rf, s⟩ := p simp only [spr_minimax_sign_deletion_monotonicity_opt_set, Finset.mem_filter, Finset.mem_univ, true_and] at hp have hRD : Rf ⊆ spr_minimax_sign_deletion_monotonicity_del_set j b := by intro i hi simp only [spr_minimax_sign_deletion_monotonicity_del_set, Finset.mem_filter, Finset.mem_univ, true_and] exact hp i hi refine le_trans (Finset.inf'_le (f := fun t => spr_value n k (spr_move b j (spr_minimax_sign_deletion_monotonicity_del_set j b) t)) (Finset.mem_univ s)) ?_ exact ih _ _ (spr_minimax_sign_deletion_monotonicity_move_delete_le b j Rf (spr_minimax_sign_deletion_monotonicity_del_set j b) s hRD) have h4 : (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)) ≤ max (spr_sign_count b) ((Finset.univ.filter (fun j => b j = none)).sup (fun j => (spr_minimax_sign_deletion_monotonicity_opt_set j b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j b) (fun p => spr_value n k (spr_move b j p.1 p.2)))) := by refine le_trans (Finset.le_sup (f := fun j' => (spr_minimax_sign_deletion_monotonicity_opt_set j' b).inf' (spr_minimax_sign_deletion_monotonicity_opt_set_nonempty j' b) (fun p => spr_value n k (spr_move b j' p.1 p.2))) ?_) (Nat.le_max_right _ _) exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hbj⟩ exact le_trans h1 (le_trans h2 (le_trans h3 h4)) · obtain ⟨v, hv⟩ : ∃ v, b j = some v := by cases h : b j with | none => exact absurd h hbj | some v => exact ⟨v, rfl⟩ refine le_trans ?_ (spr_minimax_sign_deletion_monotonicity_horizon_mono k b) refine le_trans ?_ (ih _ _ (spr_minimax_sign_deletion_monotonicity_move_none_pal hle j hv)) refine Finset.inf'_le (f := fun p : Finset (Fin n) × Bool => spr_value n k (spr_move b' j p.1 p.2)) (b := (∅, v)) ?_ simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi; exact absurd hi (Finset.notMem_empty i)