tarski_query_complexity_dim_le_succ
Dimension reduction: any query algorithm finding a fixed point in dimension k + 1 in at most q queries can be simulated in dimension k with at most q queries.
Statement
theorem tarski_query_complexity_dim_le_succ (n k q : ℕ)
(h : tarski_query_complexity_le n (k + 1) q) :
tarski_query_complexity_le n k q- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Quot.soundpropext- Built on 6
- 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)…
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - TarskiQueryTree.runThe point a query tree outputs when the black box is f.
- Used by 1
- tarski_query_complexity_dim_leGeneral dimension simulation reduction: any query algorithm finding a fixed point in dimension k in at most q queries can be simulated in…
The proof, explained
To simulate a (k + 1)-dimensional query algorithm for Tarski's fixed point theorem in dimension k with at most q queries, we construct an embedded query tree that restricts all queries to the first k coordinates and keeps the last coordinate fixed. Given any monotone function f on (Fin n)^k, we lift it to a monotone function on (Fin n)^(k + 1) by applying f on the first k coordinates and acting as the identity on the last coordinate. The original (k + 1)-dimensional tree finds a fixed point of this lifted map in at most q queries, and the embedded tree faithfully traces this execution, outputting a fixed point of f within the same query bound.
The lifted map is monotone at the last coordinate.
Let x ≤ y in (Fin n)^(k + 1). We decompose coordinate index i using Fin.lastCases. When i is the last coordinate Fin.last k, the definition of the lifted map leaves the last coordinate unchanged via Fin.snoc_last, so the inequality simplifies to x(last) ≤ y(last), which holds by x ≤ y.
uses
Fin.lastCases,Fin.snoc_lastintro x y hxy i induction i using Fin.lastCases with | last => simp only [tarski_query_complexity_dim_le_succ_lift_map, Fin.snoc_last] exact hxy (Fin.last k)
The lifted map is monotone at the first k coordinates, and therefore monotone overall.
When i = Fin.castSucc j for some j ∈ Fin k, simplifying with Fin.snoc_castSucc shows that the i-th coordinate is (f(x|_{1..k}))_j and (f(y|_{1..k}))_j. Since x ≤ y implies x|_{1..k} ≤ y|_{1..k}, the inequality follows directly from the assumption that f is monotone.
uses
Fin.snoc_castSucc| cast i => simp only [tarski_query_complexity_dim_le_succ_lift_map, Fin.snoc_castSucc] exact hf (fun j => hxy (Fin.castSucc j)) iFor an output leaf, running the embedded tree produces the projection of the original output onto the first k coordinates.
By structural induction on the tree t, if t is an output leaf output z, both sides are definitionally equal to the restriction of z to the first k coordinates.
induction t with | output z => rfl
For a query tree, running the embedded tree on f equals projecting the run of the original tree on the lifted map onto the first k coordinates.
For a query node querying z with continuation next, the embedded tree queries the first k coordinates of z using f, obtaining f(z|_{1..k}). Appending the unchanged last coordinate z(last) reconstructs the lifted query response. The embedded tree then recurses on the embedding of the next tree, matching the original tree running on the lifted map by the induction hypothesis.
uses
TarskiQueryTree.run| query z next ih => simp only [tarski_query_complexity_dim_le_succ_embed_tree, TarskiQueryTree.run] have hlift : Fin.snoc (f (fun i => z (Fin.castSucc i))) (z (Fin.last k)) = tarski_query_complexity_dim_le_succ_lift_map f z := rfl rw [hlift] exact ih (tarski_query_complexity_dim_le_succ_lift_map f z)For an output leaf, the query cost of the embedded tree on f matches that of the original tree on the lifted map.
In the base case of an output leaf, no queries are made by either tree, so both costs are definitionally zero.
induction t with | output z => rfl
For query trees, the query cost of the embedded tree on f equals the cost of the original tree on the lifted map.
At a query node, each tree expends exactly 1 query at the root and branches to the subtree corresponding to the response of the lifted map. By the induction hypothesis, the recursive costs of the subtrees are equal, hence the total costs match.
uses
TarskiQueryTree.cost| query z next ih => simp only [tarski_query_complexity_dim_le_succ_embed_tree, TarskiQueryTree.cost] have hlift : Fin.snoc (f (fun i => z (Fin.castSucc i))) (z (Fin.last k)) = tarski_query_complexity_dim_le_succ_lift_map f z := rfl rw [hlift] rw [ih (tarski_query_complexity_dim_le_succ_lift_map f z)]If the original tree on the lifted map finds a fixed point of that lifted map, the embedded tree on f finds a fixed point of f.
By the simulation lemma, the embedded tree outputs the first k coordinates of the result of t on the lifted map. By function extensionality, it suffices to check each coordinate i < k. Evaluating the fixed-point hypothesis at coordinate Fin.castSucc i via congr_fun and simplifying with Fin.snoc_castSucc shows that f applied to the output equals the output at coordinate i.
uses
tarski_query_complexity_dim_le_succ_embed_tree_run,funext,congr_fun,Fin.snoc_castSucchave hrun := tarski_query_complexity_dim_le_succ_embed_tree_run f t rw [hrun] apply funext intro i have h := congr_fun hfix (Fin.castSucc i) dsimp [tarski_query_complexity_dim_le_succ_lift_map] at h rw [Fin.snoc_castSucc] at h exact h
The embedded tree correctly finds a fixed point for any monotone map f in dimension k.
Given an algorithm tree t for dimension k + 1 that uses at most q queries, we choose its embedded counterpart for dimension k. For any monotone f, lifting f produces a monotone map on dimension k + 1. The hypothesis on t guarantees that running t on the lifted map produces a fixed point of the lifted map. By the fixed-point preservation lemma, the embedded tree's output is therefore a fixed point of f.
uses
tarski_query_complexity_dim_le_succ_lift_map_mono,tarski_query_complexity_dim_le_succ_embed_tree_fixedobtain ⟨t, ht⟩ := h refine ⟨tarski_query_complexity_dim_le_succ_embed_tree t, fun f hf => ?_⟩ have hmono := tarski_query_complexity_dim_le_succ_lift_map_mono f hf obtain ⟨hfix, hcost⟩ := ht (tarski_query_complexity_dim_le_succ_lift_map f) hmono refine ⟨tarski_query_complexity_dim_le_succ_embed_tree_fixed f t hfix, ?_⟩
The query complexity of the embedded tree on f is at most q.
By the cost-preservation lemma, the query cost of the embedded tree on f equals the cost of t on the lifted map, which is bounded by q.
uses
tarski_query_complexity_dim_le_succ_embed_tree_costrw [tarski_query_complexity_dim_le_succ_embed_tree_cost] exact hcost
Fin.lastCases- Case analysis principle on Fin (n + 1), splitting an index into either the final coordinate Fin.last n or an earlier coordinate Fin.castSucc i for i ∈ Fin n.
Fin.snoc_last- Evaluating an extended vector (Fin.snoc p x) at the final position Fin.last n returns x.
Fin.snoc_castSucc- Evaluating an extended vector (Fin.snoc p x) at an earlier position Fin.castSucc i returns p i.
TarskiQueryTree.run- Evaluates a Tarski query tree on a given map, returning the final output vector.
TarskiQueryTree.cost- Computes the total number of queries made by a query tree on a given map.
tarski_query_complexity_dim_le_succ_embed_tree_run- Running the embedded tree on f gives the projection onto the first k coordinates of running the original (k + 1)-dimensional tree on the lifted map of f.
funext- Two functions are equal if their values agree on all inputs (function extensionality).
congr_fun- If two functions are equal, their evaluations at any argument are equal.
tarski_query_complexity_dim_le_succ_lift_map_mono- Lifting a monotone map on (Fin n)^k to (Fin n)^(k + 1) by fixing the last coordinate preserves monotonicity.
tarski_query_complexity_dim_le_succ_embed_tree_fixed- If running the original tree on the lifted map yields a fixed point of that lifted map, then running the embedded tree on f yields a fixed point of f.
tarski_query_complexity_dim_le_succ_embed_tree_cost- The query cost of the embedded tree on f equals the query cost of the original tree on the lifted map of f.
- The formalization models coordinates in dimension k + 1 using Fin (k + 1), where the first k coordinates are mapped via Fin.castSucc and the final coordinate is Fin.last k; Fin.snoc appends the final value to a k-tuple.
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.
def tarski_query_complexity_dim_le_succ_embed_tree {n k : ℕ} : TarskiQueryTree n (k + 1) → TarskiQueryTree n k | .output z => .output (fun i => z (Fin.castSucc i)) | .query z next => .query (fun i => z (Fin.castSucc i)) (fun y => tarski_query_complexity_dim_le_succ_embed_tree (next (Fin.snoc y (z (Fin.last k)))))def tarski_query_complexity_dim_le_succ_lift_map {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) : (Fin (k + 1) → Fin n) → (Fin (k + 1) → Fin n) := fun z => Fin.snoc (f (fun i => z (Fin.castSucc i))) (z (Fin.last k))theorem tarski_query_complexity_dim_le_succ_lift_map_mono {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) : Monotone (tarski_query_complexity_dim_le_succ_lift_map f) := by intro x y hxy i induction i using Fin.lastCases with | last => simp only [tarski_query_complexity_dim_le_succ_lift_map, Fin.snoc_last] exact hxy (Fin.last k) | cast i => simp only [tarski_query_complexity_dim_le_succ_lift_map, Fin.snoc_castSucc] exact hf (fun j => hxy (Fin.castSucc j)) itheorem tarski_query_complexity_dim_le_succ_embed_tree_run {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) (t : TarskiQueryTree n (k + 1)) : (tarski_query_complexity_dim_le_succ_embed_tree t).run f = fun i => (t.run (tarski_query_complexity_dim_le_succ_lift_map f)) (Fin.castSucc i) := by induction t with | output z => rfl | query z next ih => simp only [tarski_query_complexity_dim_le_succ_embed_tree, TarskiQueryTree.run] have hlift : Fin.snoc (f (fun i => z (Fin.castSucc i))) (z (Fin.last k)) = tarski_query_complexity_dim_le_succ_lift_map f z := rfl rw [hlift] exact ih (tarski_query_complexity_dim_le_succ_lift_map f z)theorem tarski_query_complexity_dim_le_succ_embed_tree_cost {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) (t : TarskiQueryTree n (k + 1)) : (tarski_query_complexity_dim_le_succ_embed_tree t).cost f = t.cost (tarski_query_complexity_dim_le_succ_lift_map f) := by induction t with | output z => rfl | query z next ih => simp only [tarski_query_complexity_dim_le_succ_embed_tree, TarskiQueryTree.cost] have hlift : Fin.snoc (f (fun i => z (Fin.castSucc i))) (z (Fin.last k)) = tarski_query_complexity_dim_le_succ_lift_map f z := rfl rw [hlift] rw [ih (tarski_query_complexity_dim_le_succ_lift_map f z)]theorem tarski_query_complexity_dim_le_succ_embed_tree_fixed {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) (t : TarskiQueryTree n (k + 1)) (hfix : tarski_query_complexity_dim_le_succ_lift_map f (t.run (tarski_query_complexity_dim_le_succ_lift_map f)) = t.run (tarski_query_complexity_dim_le_succ_lift_map f)) : f ((tarski_query_complexity_dim_le_succ_embed_tree t).run f) = (tarski_query_complexity_dim_le_succ_embed_tree t).run f := by have hrun := tarski_query_complexity_dim_le_succ_embed_tree_run f t rw [hrun] apply funext intro i have h := congr_fun hfix (Fin.castSucc i) dsimp [tarski_query_complexity_dim_le_succ_lift_map] at h rw [Fin.snoc_castSucc] at h exact h/-- Dimension reduction: any query algorithm finding a fixed point in dimension k + 1 in at most q queries can be simulated in dimension k with at most q queries. -/theorem tarski_query_complexity_dim_le_succ (n k q : ℕ) (h : tarski_query_complexity_le n (k + 1) q) : tarski_query_complexity_le n k q := by obtain ⟨t, ht⟩ := h refine ⟨tarski_query_complexity_dim_le_succ_embed_tree t, fun f hf => ?_⟩ have hmono := tarski_query_complexity_dim_le_succ_lift_map_mono f hf obtain ⟨hfix, hcost⟩ := ht (tarski_query_complexity_dim_le_succ_lift_map f) hmono refine ⟨tarski_query_complexity_dim_le_succ_embed_tree_fixed f t hfix, ?_⟩ rw [tarski_query_complexity_dim_le_succ_embed_tree_cost] exact hcost