AFTD Auto-Formalizing Theoretical Domains

tarski_query_complexity_mono_budget

theoremverified

Query complexity is monotone in the query budget: any algorithm using at most q queries also satisfies the bound for any q' ≥ q.

Statement

theorem tarski_query_complexity_mono_budget (n k q q' : ℕ)
    (h : tarski_query_complexity_le n k q) (hle : q ≤ q') :
    tarski_query_complexity_le n k q'
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
propext
Built on 4
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
  • TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
  • TarskiQueryTree.runThe point a query tree outputs when the black box is f.
  • tarski_query_complexity_leTarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order)…
Used by 1
  • tarski_box_query_le_mono_budgetThe box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for…

The proof, explained

The proof witnesses that query complexity is at most q' using the exact same query tree t that witnesses query complexity at most q. For any monotone function, the algorithm still outputs a fixed point, and the query cost is bounded by q' by transitivity of ≤ applied to the cost bound q and the hypothesis q ≤ q'.

  1. Let t be an algorithm (query tree) witnessing that the query complexity is at most q.

    From the assumption h that the query complexity is at most q, extract a query tree t along with the property ht that for any monotone function f, running t on f produces a fixed point of f and incurs a query cost of at most q.

    line 5

      obtain ⟨t, ht⟩ := h
  2. The tree t also witnesses that the query complexity is at most q'.

    We exhibit t as the witness for query complexity at most q'. Given any monotone function f, t outputs a fixed point by the first part of ht, and its query cost is at most q' by chaining the bound cost ≤ q from ht with q ≤ q' via transitivity (le_trans).

    line 6

    uses le_trans

      exact ⟨t, fun f hf => ⟨(ht f hf).1, le_trans (ht f hf).2 hle⟩⟩
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.

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

/-- Query complexity is monotone in the query budget: any algorithm using at most q queries also satisfies the bound for any q' ≥ q. -/theorem tarski_query_complexity_mono_budget (n k q q' : ℕ)    (h : tarski_query_complexity_le n k q) (hle : q ≤ q') :    tarski_query_complexity_le n k q' := by  obtain ⟨t, ht⟩ := h  exact ⟨t, fun f hf => ⟨(ht f hf).1, le_trans (ht f hf).2 hle⟩⟩
See it in the graphDiscuss this resultChallenge it