AFTD Auto-Formalizing Theoretical Domains

tarski_query_complexity_dim_le_succ

theoremverified

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 LinearOrder is a TotalPreorder.
  • 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 than LinearOrder — 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.

  1. 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.

    lines 15–19

    uses Fin.lastCases, Fin.snoc_last

      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)
  2. 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.

    lines 20–22

    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)) i
  3. For 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.

    lines 28–30

      induction t with
      | output z =>
        rfl
  4. 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.

    lines 31–36

    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)
  5. 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.

    lines 42–44

      induction t with
      | output z =>
        rfl
  6. 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.

    lines 45–50

    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)]
  7. 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.

    lines 59–66

    uses tarski_query_complexity_dim_le_succ_embed_tree_run, funext, congr_fun, Fin.snoc_castSucc

      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
  8. 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.

    lines 72–76

    uses tarski_query_complexity_dim_le_succ_lift_map_mono, tarski_query_complexity_dim_le_succ_embed_tree_fixed

      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, ?_⟩
  9. 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.

    lines 77–78

    uses tarski_query_complexity_dim_le_succ_embed_tree_cost

      rw [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.

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

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
See it in the graphDiscuss this resultChallenge it