tarski_query_complexity_mono_budget
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'.
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.
obtain ⟨t, ht⟩ := hThe 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).
uses
le_transexact ⟨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
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.
/-- 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⟩⟩