AFTD Auto-Formalizing Theoretical Domains

spr_minimax_sign_deletion_monotonicity

theoremverifiedformalization

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.

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

    lines 10–11

    uses Finset.notMem_empty

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

    lines 15–18

    uses spr_minimax_sign_deletion_monotonicity_pal_of_pointwise

      intro i v hv
      rcases h i with h1 | h1
      · rw [h1] at hv; exact absurd hv (by simp)
      · rw [← h1]; exact hv
  3. 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.

    lines 23–29

    uses spr_sign_count, Finset.card_le_card, Option.isSome_iff_exists

      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⟩
  4. 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.

    lines 34–44

    uses spr_minimax_sign_deletion_monotonicity_pal_of_pointwise, spr_move, if_neg, if_pos

      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]
  5. 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'.

    lines 50–66

    uses spr_move, if_neg, if_pos, spr_minimax_sign_deletion_monotonicity_del_set

      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 hv
  6. 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.

    lines 71–81

    uses spr_minimax_sign_deletion_monotonicity_pal_of_pointwise, spr_move, if_neg, Finset.notMem_empty, if_false

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

    lines 85–96

    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'_le

      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 _)
  8. 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.

    lines 102–105

    uses spr_value.eq_1, spr_minimax_sign_deletion_monotonicity_sign_count_le

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

    lines 106–112

    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 _ _
  10. 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).

    lines 113–166

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

    lines 167–175

    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

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