tarski_fixed_point_exists
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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.
$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$.
have : NeZero n := ⟨by omega⟩
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$.
uses
OrderHom.lfp,F.map_lfplet 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`.
- The hypothesis `1 ≤ n` is used solely to establish `NeZero n`, which Lean's typeclass resolution requires to synthesize the `CompleteLattice` structure on `Fin n` (as a finite non-empty linear order) and on the grid `Fin k → Fin n`.
- The function `f` and its monotonicity hypothesis `hf` are bundled into Mathlib's order homomorphism type `OrderHom` (`α →o α`) because Tarski's fixed-point theorem is formulated for bundled monotone maps.
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.
/-- 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⟩