tarski_query_tree_bind_spec
Run/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost of a bind is the cost of the first tree plus the cost of the continuation at that output.
Statement
theorem tarski_query_tree_bind_spec {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k)
(f : (Fin k → Fin n) → Fin k → Fin n) (t : TarskiQueryTree n k) :
TarskiQueryTree.run f (tarski_query_tree_bind g t) =
TarskiQueryTree.run f (g (TarskiQueryTree.run f t)) ∧
TarskiQueryTree.cost f (tarski_query_tree_bind g t) =
TarskiQueryTree.cost f t +
TarskiQueryTree.cost f (g (TarskiQueryTree.run f t))- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Quot.soundpropext- Built on 4
- tarski_query_tree_bindSequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is…
- 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.
- TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
- Used by 1
- 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 is proved by structural induction on the query tree t. For a leaf node output x, sequential composition evaluates directly to g x, whose cost is 0 + cost f (g x). For a query node query x k', running the tree queries the oracle f at x and continues along the subtree k' (f x); applying the induction hypothesis to this response establishes the run identity immediately and reduces the cost identity to the linear arithmetic identity (c + d) + 1 = (c + 1) + d.
By structural induction on t, both identities hold for leaf nodes t = output x.
We induct on the structure of the tree t. In the base case, t = output x represents a leaf with output value x. By definition of sequential composition, tarski_query_tree_bind g (output x) = g x, and by definition of running a tree, run f (output x) = x. Thus the run of the composed tree is run f (g x), which matches run f (g (run f (output x))) definitionally. For the query cost, a leaf node performs zero queries, so cost f (output x) = 0. The cost of the composed tree is cost f (g x), while the right-hand sum is 0 + cost f (g x); these are equal by Nat.zero_add.
uses
Nat.zero_addinduction t with | output x => exact ⟨rfl, (Nat.zero_add _).symm⟩
For query nodes t = query x k', the run identity holds by the induction hypothesis on the queried subtree.
In the inductive step, the tree queries the oracle f at input x, receives the response f x, and continues along the subtree k' (f x). The induction hypothesis states that both identities hold for every subtree k' a. Specializing the induction hypothesis to the oracle's actual response a = f x, its first component establishes that run f (tarski_query_tree_bind g (k' (f x))) = run f (g (run f (k' (f x)))). Since executing a query node definitionally evaluates to running its continuation at f x, this immediately settles the run identity for the query node, leaving only the cost equation to verify.
| query x k' ih => refine ⟨(ih (f x)).1, ?_⟩For query nodes t = query x k', the cost identity also holds, completing the induction.
The cost of executing a query node is defined as 1 plus the cost of running the continuation subtree on the oracle response f x. Unfolding this definition rephrases the goal into an explicit arithmetic statement: the cost of the composed subtree plus 1 equals the subtree cost plus 1 plus the continuation cost. Rewriting with the second component of the induction hypothesis at f x substitutes the cost of the composed subtree with the sum of the subtree cost and the continuation cost. The resulting equation has the form (c + d) + 1 = (c + 1) + d, where c is the subtree cost and d is the continuation cost; this is closed by linear arithmetic over ℕ (omega).
show TarskiQueryTree.cost f (tarski_query_tree_bind g (k' (f x))) + 1 = (TarskiQueryTree.cost f (k' (f x)) + 1) + TarskiQueryTree.cost f (g (TarskiQueryTree.run f (k' (f x)))) rw [(ih (f x)).2] omega
Nat.zero_add- For any natural number n, 0 + n = n.
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.
/-- Run and cost of a sequential composition. -/theorem tarski_query_tree_bind_spec {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k) (f : (Fin k → Fin n) → Fin k → Fin n) (t : TarskiQueryTree n k) : TarskiQueryTree.run f (tarski_query_tree_bind g t) = TarskiQueryTree.run f (g (TarskiQueryTree.run f t)) ∧ TarskiQueryTree.cost f (tarski_query_tree_bind g t) = TarskiQueryTree.cost f t + TarskiQueryTree.cost f (g (TarskiQueryTree.run f t)) := by induction t with | output x => exact ⟨rfl, (Nat.zero_add _).symm⟩ | query x k' ih => refine ⟨(ih (f x)).1, ?_⟩ show TarskiQueryTree.cost f (tarski_query_tree_bind g (k' (f x))) + 1 = (TarskiQueryTree.cost f (k' (f x)) + 1) + TarskiQueryTree.cost f (g (TarskiQueryTree.run f (k' (f x)))) rw [(ih (f x)).2] omega