tarski_box_query_le_zero_dim
Dimension zero is free: in dimension 0 (the one-point box) one query suffices, for every n and every box.
Statement
theorem tarski_box_query_le_zero_dim (n : ℕ) : tarski_box_query_le n 0 1- Source
- step towards tarski_box_query_le_five_log_sq
- Verified
- 22 Oct 2026
- Axioms
Quot.soundpropext- Built on 7
- tarski_box_query_leBox-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on…
- 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.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… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TarskiQueryTree.runThe point a query tree outputs when the black box is f.
- tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…
- Used by 1
- tarski_box_query_le_polylogBox-form state of the art: for every dimension k there is a constant C such that every sub-box of [n]^k admits a box algorithm with at…
The proof, explained
In dimension 0, the domain Fin 0 → Fin n is a subsingleton containing only the unique function from the empty type. The query tree TarskiQueryTree.output a makes no queries and immediately returns a. This point a is trivially a fixed point of any function on the space, lies in the box [a, b], and requires zero queries, which is at most one.
For any box endpoints a ≤ b in dimension 0, the constant query tree that outputs a without making any queries is a valid candidate.
We introduce the endpoints a and b together with the hypothesis hab that a ≤ b. Since the space of 0-dimensional points Fin 0 → Fin n consists of a single point, no queries are needed. We provide TarskiQueryTree.output a as the witness tree.
uses
TarskiQueryTree.outputintro a b hab refine ⟨TarskiQueryTree.output a, ?_⟩
The candidate tree outputs a value between a and b, is a fixed point of f, and incurs cost at most 1.
We introduce an arbitrary function f and discard the assumptions that f is monotone and preserves the interval [a, b], as they are unneeded. Evaluating TarskiQueryTree.output a on f yields a at cost 0. The bounds a ≤ a and a ≤ b hold by reflexivity (le_rfl) and the hypothesis hab. Because Fin 0 → Fin n is a subsingleton, f a = a holds automatically by Subsingleton.elim. Finally, the query cost 0 ≤ 1 holds by Nat.zero_le.
uses
le_rfl,Subsingleton.elim,Nat.zero_leintro f _ _ _ exact ⟨le_rfl, hab, Subsingleton.elim _ _, Nat.zero_le 1⟩
TarskiQueryTree.output- The constructor for a query tree that performs no queries and immediately outputs a given point.
le_rfl- Reflexivity of preorder: every element is less than or equal to itself.
Subsingleton.elim- In any type with at most one element (a subsingleton), all elements are equal.
Nat.zero_le- Zero is less than or equal to any natural number.
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.
/-- Base of every dimension ladder for the box invariant, stated for all n (no NeZero needed, unlike tarski_box_query_le_small). -/theorem tarski_box_query_le_zero_dim (n : ℕ) : tarski_box_query_le n 0 1 := by intro a b hab refine ⟨TarskiQueryTree.output a, ?_⟩ intro f _ _ _ exact ⟨le_rfl, hab, Subsingleton.elim _ _, Nat.zero_le 1⟩