AFTD Auto-Formalizing Theoretical Domains

tarski_subinterval_fixed_point

theoremverified

Subinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b].

Statement

theorem tarski_subinterval_fixed_point (n k : ℕ) [NeZero n]
    (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)
    (a b : Fin k → Fin n) (hab : a ≤ b) (ha : a ≤ f a) (hb : f b ≤ b) :
    ∃ x : Fin k → Fin n, a ≤ x ∧ x ≤ b ∧ f x = x
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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.
Used by 3
  • tarski_subinterval_slice_shrinkSlicing contraction principle: if x is a fixed point of f on all coordinates j ≠ i within [a, b], then comparing f(x)_i with x_i either…
  • 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…
  • 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…

The proof, explained

The proof applies the Knaster-Tarski fixed point theorem on the complete lattice of functions from Fin k to Fin n. By bundling the monotone map $f$ into an order homomorphism, we choose $x$ as the least fixed point of $f$ lying above $a$, which is constructed as the least fixed point of the operator $y \mapsto a \sqcup f(y)$. By definition, $x$ satisfies $a \le x$ and $f(x) = x$. Finally, the upper bound $x \le b$ holds by Knaster-Tarski because $b$ is a prefixpoint of $y \mapsto a \sqcup f(y)$, as $a \le b$ and $f(b) \le b$.

  1. Define $x$ as the least fixed point of $f$ above $a$, which satisfies $f(x) = x$ and $a \le x$.

    We bundle $f$ with its monotonicity hypothesis $hf$ into an order homomorphism $F$. Using the hypothesis $a \le f(a)$, we define $x$ as the next fixed point of $F$ starting from $a$ via `F.nextFixed`. By construction, $x$ is a fixed point of $f$ ($f(x) = x$) and satisfies $a \le x$ by `F.le_nextFixed`.

    lines 6–10

    uses F.le_nextFixed

      let F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩
      have ha' : a ≤ F a := ha
      let x : Fin k → Fin n := (F.nextFixed a ha' : (Fin k → Fin n))
      have hxfix : f x = x := (F.nextFixed a ha').2
      have hax : a ≤ x := F.le_nextFixed ha'
  2. $x \le b$

    By definition of `nextFixed`, $x$ is the least fixed point of the operator $y \mapsto a \sqcup F(y)$. By `OrderHom.lfp_le`, to show this least fixed point is at most $b$, it suffices to check that $b$ is a prefixpoint, i.e., $a \sqcup f(b) \le b$. This follows from `sup_le` combined with the hypotheses $a \le b$ and $f(b) \le b$.

    lines 11–15

    uses OrderHom.lfp_le, sup_le

      have hxb : x ≤ b := by
        change (OrderHom.const (Fin k → Fin n) a ⊔ F).lfp ≤ b
        apply OrderHom.lfp_le
        change a ⊔ f b ≤ b
        exact sup_le hab hb
  3. There exists $x$ such that $a \le x$, $x \le b$, and $f(x) = x$.

    We assemble the candidate point $x$ together with the established inequalities $a \le x$, $x \le b$, and the equality $f(x) = x$ to satisfy the existential conclusion.

    line 16

      exact ⟨x, hax, hxb, hxfix⟩
F.le_nextFixed
For an order homomorphism $F$ and a point $a$ satisfying $a \le F(a)$, $a$ is less than or equal to the next fixed point of $F$ above $a$.
OrderHom.lfp_le
For an order homomorphism $f$ on a complete lattice, if $f(b) \le b$, then the least fixed point of $f$ is at most $b$.
sup_le
In a join-semilattice, if $a \le c$ and $b \le c$, then the supremum $a \sqcup b \le c$.

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

/-- Subinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b]. -/theorem tarski_subinterval_fixed_point (n k : ℕ) [NeZero n]    (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)    (a b : Fin k → Fin n) (hab : a ≤ b) (ha : a ≤ f a) (hb : f b ≤ b) :    ∃ x : Fin k → Fin n, a ≤ x ∧ x ≤ b ∧ f x = x := by  let F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩  have ha' : a ≤ F a := ha  let x : Fin k → Fin n := (F.nextFixed a ha' : (Fin k → Fin n))  have hxfix : f x = x := (F.nextFixed a ha').2  have hax : a ≤ x := F.le_nextFixed ha'  have hxb : x ≤ b := by    change (OrderHom.const (Fin k → Fin n) a ⊔ F).lfp ≤ b    apply OrderHom.lfp_le    change a ⊔ f b ≤ b    exact sup_le hab hb  exact ⟨x, hax, hxb, hxfix⟩
See it in the graphDiscuss this resultChallenge it