AFTD Auto-Formalizing Theoretical Domains

tarski_slice_upper_bound

theoremverified

Monotonicity preservation on coordinate slices (upper bound): fixing coordinate i to any value m ≤ b_i preserves the upper subinterval invariant f(b^{(i,m)})_j ≤ b_j for all coordinates j.

Statement

theorem tarski_slice_upper_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)
    (b : Fin k → Fin n) (hb : f b ≤ b) (i : Fin k) (m : Fin n) (hbm : m ≤ b i) (j : Fin k) :
    f (fun l => if l = i then m else b l) j ≤ b j
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
propext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2
  • tarski_slice_subbox_monotone_and_fixedFor any monotone map f on [a, b] in dimension k+1 and any coordinate cut c with a_i <= c <= b_i, the sliced map g y j = f (insertNth i c…
  • tarski_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…

The proof, explained

The theorem states that decreasing coordinate i of an upper invariant point b (satisfying f(b) ≤ b) to any m ≤ b_i preserves the upper invariant f(b')_j ≤ b_j at every coordinate j. The proof first shows that the modified vector b' is pointwise bounded above by b by checking coordinate i and the remaining coordinates separately. It then applies the monotonicity of f to obtain f(b') ≤ f(b), which yields f(b')_j ≤ b_j after chaining with f(b)_j ≤ b_j by transitivity.

  1. The modified vector b^{(i, m)}, obtained by setting the i-th coordinate of b to m, is pointwise less than or equal to b.

    To show that the updated vector is bounded by b, we inspect each coordinate l. If l = i, its value is m, which is bounded by b_i by the hypothesis hbm. If l ≠ i, its value remains b_l, which is bounded by b_l by reflexivity (le_rfl).

    lines 5–11

    uses le_rfl

      have h_le : (fun l => if l = i then m else b l) ≤ b := by
        intro l
        dsimp
        split_ifs with h
        · subst h
          exact hbm
        · exact le_rfl
  2. f(b^{(i, m)})_j ≤ b_j for any coordinate j.

    Because f is monotone (hf), the pointwise inequality b^{(i, m)} ≤ b implies f(b^{(i, m)}) ≤ f(b), and evaluating at coordinate j gives f(b^{(i, m)})_j ≤ f(b)_j. Chaining this with the assumption f(b)_j ≤ b_j (hb j) by transitivity completes the proof.

    line 12

      exact (hf h_le j).trans (hb j)
le_rfl
In any preorder, every element is less than or equal to itself: a ≤ a.

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 preservation on coordinate slices: decreasing coordinate i from b_i to m preserves f(b^{(i,m)}) ≤ b. -/theorem tarski_slice_upper_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)    (b : Fin k → Fin n) (hb : f b ≤ b) (i : Fin k) (m : Fin n) (hbm : m ≤ b i) (j : Fin k) :    f (fun l => if l = i then m else b l) j ≤ b j := by  have h_le : (fun l => if l = i then m else b l) ≤ b := by    intro l    dsimp    split_ifs with h    · subst h      exact hbm    · exact le_rfl  exact (hf h_le j).trans (hb j)
See it in the graphDiscuss this resultChallenge it