AFTD Auto-Formalizing Theoretical Domains

tarski_fixed_point_exists

theoremverified

Every monotone self-map on the discrete grid [n]^k possesses at least one fixed point, by Tarski's fixed point theorem on finite complete lattices.

Statement

theorem tarski_fixed_point_exists (n k : ℕ) (hn : 1 ≤ n)
    (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) :
    ∃ x : Fin k → Fin n, f x = x
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The discrete grid $[n]^k$, modeled as the function space $\operatorname{Fin} k \to \operatorname{Fin} n$, is a finite complete lattice when $n \ge 1$. The monotone function $f$ is packaged into an order homomorphism, and the result follows immediately from the Knaster-Tarski fixed-point theorem, which guarantees that every order homomorphism on a complete lattice has a least fixed point.

  1. $n$ is non-zero, allowing Lean to recognize $\operatorname{Fin} k \to \operatorname{Fin} n$ as a complete lattice.

    From the hypothesis $1 \le n$, linear integer arithmetic (`omega`) deduces $n \neq 0$. This establishes the typeclass instance `NeZero n`, enabling Lean to synthesize a complete lattice structure on the finite linear order $\operatorname{Fin} n$ and, by pointwise extension, on the grid $\operatorname{Fin} k \to \operatorname{Fin} n$.

    line 5

      have : NeZero n := ⟨by omega⟩
  2. The map $f$ has a fixed point, given by the least fixed point of its bundled order homomorphism.

    The function $f$ and its monotonicity assumption $hf$ are bundled into an order homomorphism $F : (\operatorname{Fin} k \to \operatorname{Fin} n) \too (\operatorname{Fin} k \to \operatorname{Fin} n)$. By Tarski's fixed point theorem, $F$ possesses a least fixed point `OrderHom.lfp F`, and `F.map_lfp` certifies that $F(\operatorname{lfp} F) = \operatorname{lfp} F$. This yields an explicit witness satisfying $f x = x$.

    lines 6–7

    uses OrderHom.lfp, F.map_lfp

      let F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩
      exact ⟨OrderHom.lfp F, F.map_lfp⟩
OrderHom.lfp
The least fixed point operator for an order homomorphism on a complete lattice, guaranteed by the Knaster-Tarski fixed-point theorem.
F.map_lfp
The least fixed point of an order homomorphism `F` is a fixed point of `F`, that is, `F (OrderHom.lfp F) = OrderHom.lfp 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

/-- Every monotone self-map on the discrete grid [n]^k has a fixed point, by Tarski's fixed point theorem on finite complete lattices. -/theorem tarski_fixed_point_exists (n k : ℕ) (hn : 1 ≤ n)    (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) :    ∃ x : Fin k → Fin n, f x = x := by  have : NeZero n := ⟨by omega⟩  let F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩  exact ⟨OrderHom.lfp F, F.map_lfp⟩
See it in the graphDiscuss this resultChallenge it