The Banach fixed-point theorem
ProvedFamousTheorems.banach_fixed_pointThe Banach fixed-point theorem (the contraction mapping principle).
Let be a contraction with constant on a complete metric space. Then has a fixed point , the iterates converge to it from any starting point , and the error is controlled explicitly:
Unlike Brouwer's theorem, this is entirely constructive: it not only asserts a fixed point but produces it as a limit of iterates, with a computable a-priori bound after a single step. That bound is what makes it a practical algorithm rather than an existence statement — one evaluation of tells you how many iterations suffice for any target accuracy.
Banach proved it in his 1922 thesis. It is the standard existence-and-uniqueness engine of analysis: the Picard–Lindelöf theorem for ODEs, the implicit and inverse function theorems, and the existence of invariant measures for contracting dynamical systems are all applications, and Newton's method converges for the same reason.
Formalization note. Distances are extended (ℝ≥0∞), so the hypothesis edist x (f x) ≠ ⊤ rules
out a starting point at infinite distance from its image; f^[n] is -fold iteration and
Function.IsFixedPt f y is . The result is Mathlib's
ContractingWith.exists_fixedPoint.
import Mathlib
namespace FamousTheorems
open MeasureTheory ProbabilityTheory Filter Set
open scoped Topology ENNReal NNReal
theorem banach_fixed_point {α : Type*} [EMetricSpace α] [CompleteSpace α] {K : ℝ≥0} {f : α → α}
(hf : ContractingWith K f) (x : α) (hx : edist x (f x) ≠ ⊤) :
∃ y, Function.IsFixedPt f y ∧ Tendsto (fun n ↦ f^[n] x) atTop (𝓝 y) ∧
∀ n : ℕ, edist (f^[n] x) y ≤ edist x (f x) * (K : ℝ≥0∞) ^ n / (1 - K) := by sorry
end FamousTheorems