Least fixed points of continuous maps #
Kleene iteration in a pointed omega-complete partial order. The carrier need not be a complete lattice. In particular, distinct errors and returned values need not have a common upper bound.
The approximants are Mathlib's fixedPoints.iterateChain started at bottom, so
ContinuousHom.fix is the supremum of that Kleene chain, and its unfolding and
leastness are Mathlib's fixedPoints.ωSup_iterate_mem_fixedPoint and
fixedPoints.ωSup_iterate_le_prefixedPoint. This file adds the pointed packaging,
fixed-point induction, fusion, and continuity in the recursive body. As the least
prefixed point (ContinuousHom.isLeast_fix), the result agrees with OrderHom.lfp
on a complete lattice (ContinuousHom.fix_eq_lfp).
The file also provides currying, argument exchange, and ContinuousHom.ofEq, the continuous
map between two members of a family of omega-complete partial orders along an equation of
their indices.
A fixed choice between continuous functions is continuous.
Continuity into a space of continuous maps is pointwise continuity.
Packaging pointwise continuous functions preserves continuity in their parameter.
Curry a continuous map on a product.
Equations
- f.curry = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (a : α) => OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (b : β) => f (a, b)) ⋯) ⋯
Instances For
Uncurry a continuous map into a space of continuous maps.
Equations
- f.uncurry = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (ab : α × β) => (f ab.1) ab.2) ⋯
Instances For
Exchange two continuous arguments.
Equations
- f.swapArgs = (OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (ba : β × α) => (f ba.2) ba.1) ⋯).curry
Instances For
The continuous map between two members of a family along an equation of their indices.
It is the identity once the equation is rfl.
Equations
Instances For
Transport along any equation of an index with itself is the identity.
Transport keeps the value, across the equal members of the family.
Equality after transport is heterogeneous equality before it.
Equations
- OmegaCompletePartialOrder.ContinuousHom.orderBot = { bot := OmegaCompletePartialOrder.ContinuousHom.const ⊥, bot_le := ⋯ }
The finite Kleene approximations, starting at bottom.
Equations
Instances For
The least fixed point of a continuous map on a pointed omega-CPO.
Equations
Instances For
Unfold one recursive call.
Every finite approximation is below the least fixed point.
The least fixed point is below every prefixed point.
The least fixed point is the supremum of Mathlib's Kleene chain from bottom.
The least fixed point is the least prefixed point. Together with
OrderHom.isLeast_lfp_le, this identifies it with OrderHom.lfp whenever the
carrier is also a complete lattice with the same order.
For the omega-CPO structure of a complete lattice, the least fixed point of a
continuous map is its order-theoretic least fixed point. Carriers with a separate
omega-CPO instance, such as function types, use isLeast_fix instead.
Induction over finite approximations followed by an admissibility step.
Continuous strict maps commuting with recursive bodies commute with their least fixed points. Strictness rules out inserting a result at divergence.
Each finite approximation depends continuously on the recursive body.
Taking the least fixed point depends continuously on the recursive body.
Least fixed point as a continuous map, for recursive definitions with parameters that can themselves contain partial information.