AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_zero_dim

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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.

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

    lines 3–4

    uses TarskiQueryTree.output

      intro a b hab
      refine ⟨TarskiQueryTree.output a, ?_⟩
  2. 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.

    lines 5–6

    uses le_rfl, Subsingleton.elim, Nat.zero_le

      intro 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

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