A self-map f : X → X is a contraction if it is 1-Lipschitz.
Equations
- IsContraction f = ∀ (x y : X), dist (f x) (f y) ≤ dist x y
Instances For
A real number c is a contraction constant of f if 0 < c < 1 and dist (f x) (f y) ≤ c * dist x y for all x,y.
Instances For
Definition 6.13 (Contraction and strict contraction):
(i) f is a contraction iff dist (f x) (f y) ≤ dist x y for all x,y.
(ii) f is a strict contraction iff there exists c with 0 < c < 1 such that
dist (f x) (f y) ≤ c * dist x y for all x,y; such a c is a contraction constant.
Proposition 6.13(1): if f : [a,b] → [a,b] is continuous on [a,b],
differentiable on (a,b), and |f'| ≤ 1 on (a,b), then
|f(x) - f(y)| ≤ |x - y| for all x,y ∈ [a,b];
in particular, the induced self-map of [a,b] is a non-expanding contraction.
Proposition 6.14: Let f : [a,b] → ℝ be differentiable and assume
|f x - f y| ≤ |x - y| for all x,y ∈ [a,b]. Then the derivative of f
within [a,b] satisfies |f'(x)| ≤ 1 for all x ∈ [a,b].
Helper for Proposition 6.15: from a contraction witness with 0 ≤ c < 1,
extract the nonnegativity and distance bound needed for Lipschitz control.
Helper for Proposition 6.15: convert a real-valued contraction estimate with
c ≥ 0 into an NNReal-valued LipschitzWith bound.
Helper for Proposition 6.15: any map with an NNReal Lipschitz bound is continuous.
Proposition 6.15: If f : X → X on a metric space satisfies
dist (f x) (f y) ≤ c * dist x y for some c ∈ [0,1) and all x,y,
then f is Lipschitz and therefore continuous on X.
Definition 6.14 (Fixed point): Let X be a set and let f : X → X be a map. An element x ∈ X is a fixed point of f if f x = x.
Equations
- IsFixedPoint f x = (f x = x)
Instances For
Helper for Theorem 6.7: convert a real-valued contraction bound with
0 ≤ c < 1 into ContractingWith with an NNReal constant.
Helper for Theorem 6.7: fixed points of a ContractingWith map are unique.
Helper for Theorem 6.7: in a nonempty complete metric space, a
ContractingWith map has a unique fixed point.
Theorem 6.7 (Contraction mapping theorem): Let (X,d) be a metric space and
f : X → X satisfy dist (f x) (f y) ≤ c * dist x y for some c ∈ [0,1) and all
x,y. Then f has at most one fixed point. If, in addition, X is nonempty and
complete, then f has exactly one fixed point.
Helper for Proposition 6.16: the f-centered triangle inequality and contraction
bound imply dist x0 y0 ≤ ε + c * dist x0 y0.
Helper for Proposition 6.16: the g-centered triangle inequality and contraction
bound imply dist x0 y0 ≤ ε + c' * dist x0 y0.
Proposition 6.16: Let (X,d) be a complete metric space, and let f,g : X → X
be strict contractions with contraction constants c,c' ∈ (0,1), respectively.
If x₀ and y₀ are fixed points of f and g, and there exists ε > 0 such that
dist (f x) (g x) ≤ ε for all x, then
dist x₀ y₀ ≤ ε / (1 - min c c').
Helper for Theorem 6.6: turn the real-valued contraction hypothesis into
ContractingWith with an NNReal constant.
Helper for Theorem 6.6: the local fixed-point predicate agrees with mathlib's
IsFixedPt.
Helper for Theorem 6.6: uniqueness stated using
ContractingWith.fixedPoint.
Helper for Theorem 6.6: iterates Nat.iterate f n x₀ converge to the
ContractingWith.fixedPoint.
Theorem 6.6 (Banach fixed-point theorem): If X is a nonempty complete metric
space and f : X → X is a contraction with constant c satisfying 0 < c < 1, then
f has a unique fixed point x*; moreover, for every initial point x₀, the iterates
x_{n+1} = f(x_n) converge to x*.
The unit 2-sphere in ℝ^3, viewed as a subtype of EuclideanSpace ℝ (Fin 3).
Equations
- UnitSphereTwo = { x : EuclideanSpace ℝ (Fin 3) // x ∈ Metric.sphere 0 1 }
Instances For
Helper for Theorem 6.8: the antipode of a point on S² still lies on S².
Helper for Theorem 6.8: every point of S² has an antipodal point in S².
Helper for Theorem 6.8: no point on S² is equal to its antipode.
Helper for Theorem 6.8: the antipode self-map on S².
Equations
- helperForTheorem_6_8_antipode point = -point
Instances For
Helper for Theorem 6.8: the antipode map on S² is continuous.
Helper for Theorem 6.8: applying the antipode map twice gives the original point.
Helper for Theorem 6.8: fixed points of antipode ∘ f are exactly points where
f agrees with the antipode map.
Helper for Theorem 6.8: f x = antipode x is equivalent to the ambient anti-fixed
equation (f x).1 = -x.1.
Helper for Theorem 6.8: if f x = antipode x for some x, then f has an
ambient anti-fixed point.
Helper for Theorem 6.8: if f has an ambient anti-fixed point, then f
agrees with antipode at some point.
Helper for Theorem 6.8: existence of a point with f x = antipode x is equivalent
to existence of an ambient anti-fixed point.
Helper for Theorem 6.8: from a fixed point or a point with f x = antipode x,
one obtains the theorem's fixed/anti-fixed alternative.
Helper for Theorem 6.8: existence of a fixed point of antipode ∘ f is equivalent
to existence of a point with f x = antipode x.
Helper for Theorem 6.8: existence of a fixed point of antipode ∘ f is equivalent
to existence of an ambient anti-fixed point.
Helper for Theorem 6.8: rewriting the second disjunct between
f x = antipode x and fixed points of antipode ∘ f.
Helper for Theorem 6.8: convert the fixed-or-antipode-equality disjunction into
the fixed-or-antipode ∘ f-fixed disjunction.
Helper for Theorem 6.8: a fixed point of antipode ∘ f gives an anti-fixed point of f.
Helper for Theorem 6.8: anti-fixed points are exactly fixed points of antipode ∘ f.
Helper for Theorem 6.8: if f is continuous then antipode ∘ f is continuous.
Helper for Theorem 6.8: if f or antipode ∘ f has a fixed point, then the theorem's
fixed/anti-fixed alternative follows.
Helper for Theorem 6.8: the target fixed/anti-fixed-point existence statement is
equivalent to the disjunction of a fixed point or a point where f equals antipode.
Helper for Theorem 6.8: the target fixed/anti-fixed-point existence statement is
equivalent to the disjunction of a fixed point of f or of antipode ∘ f.
Helper for Theorem 6.8: an established fixed/anti-fixed witness yields the fixed-or-antipode- fixed disjunction.
Helper for Theorem 6.8: an established fixed/anti-fixed witness yields the fixed-or-antipode- equality disjunction.
Helper for Theorem 6.8: any fixed point of f directly gives a witness for the
target fixed/anti-fixed alternative.
Helper for Theorem 6.8: if f agrees with antipode at some point, then we obtain
the target fixed/anti-fixed alternative witness.
Helper for Theorem 6.8: from a disjunction of existence of a fixed point or of an ambient anti-fixed point, obtain a direct witness of the target existential alternative.
Helper for Theorem 6.8: any upstream principle asserting fixed-point-or-antipode-
equality for continuous self-maps of S² yields the target fixed/anti-fixed alternative.
Helper for Theorem 6.8: any upstream principle asserting fixed-point-or-antipode-
comp-fixed alternatives for continuous self-maps of S² yields the fixed-point-or-
antipode-equality alternative.
Helper for Theorem 6.8: any upstream principle asserting fixed-point-or-antipode-
comp-fixed alternatives for continuous self-maps of S² yields the target fixed/anti-
fixed alternative.
Helper for Theorem 6.8: the fixed-or-antipode-equality disjunction is equivalent to the target fixed/anti-fixed existence statement.
Helper for Theorem 6.8: global fixed/anti-fixed existence and global fixed-or-antipode-
equality principles on S² are equivalent.
Helper for Theorem 6.8: global fixed-or-antipode-equality and global fixed-or-
antipode ∘ g-fixed principles on S² are equivalent.
Helper for Theorem 6.8: global fixed/anti-fixed existence and global fixed-or-
antipode ∘ g-fixed principles on S² are equivalent.
Helper for Theorem 6.8: a global fixed/anti-fixed existence principle for continuous
self-maps of S² yields the global fixed-point-or-antipode ∘ g-fixed disjunction principle.
Helper for Theorem 6.8: any upstream fixed/anti-fixed existence principle for
continuous self-maps of S² yields the fixed-point-or-antipode-equality disjunction.
Helper for Theorem 6.8: any upstream fixed/anti-fixed existence principle for
continuous self-maps of S² yields the fixed-point-or-antipode ∘ f-fixed disjunction.
Helper for Theorem 6.8: a global fixed/anti-fixed existence principle for continuous
self-maps of S² yields the global fixed-point-or-antipode-equality disjunction principle.
Helper for Theorem 6.8: applying a global fixed-point-or-antipode-equality disjunction principle gives the local fixed-point-or-antipode-equality conclusion.
Helper for Theorem 6.8: a Borsuk-Ulam-style antipodal-equality principle on maps
S² → ℝ², together with a reduction from that principle to self-maps of S², yields
the global fixed/anti-fixed existence principle on S².
Helper for Theorem 6.8: a Borsuk-Ulam-to-self-map reduction pipeline implies the
local fixed-point-or-antipode-equality disjunction for continuous self-maps of S².
Helper for Theorem 6.8: a Borsuk-Ulam-to-self-map reduction pipeline implies the
target fixed/anti-fixed alternative for each continuous self-map of S².
Helper for Theorem 6.8: the ambient space ℝ^3 has real module rank greater than one.