Documentation

ToCslib.Order.OmegaCompletePartialOrder

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.

theorem OmegaCompletePartialOrder.ωScottContinuous.ite {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] (p : Prop) [Decidable p] {f g : α → β} (hf : ωScottContinuous f) (hg : ωScottContinuous g) :
ωScottContinuous fun (x : α) => if p then f x else g x

A fixed choice between continuous functions is continuous.

theorem OmegaCompletePartialOrder.ContinuousHom.ωScottContinuous_of_apply {α : Type u_1} {β : Type u_2} {γ : Type u_3} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] [OmegaCompletePartialOrder γ] {f : α → β →𝒄 γ} (h : ∀ (b : β), ωScottContinuous fun (a : α) => (f a) b) :

Continuity into a space of continuous maps is pointwise continuity.

theorem OmegaCompletePartialOrder.ContinuousHom.ωScottContinuous_ofFun {α : Type u_1} {β : Type u_2} {γ : Type u_3} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] [OmegaCompletePartialOrder γ] {f : α → β → γ} (h : ∀ (a : α), ωScottContinuous (f a)) (hf : ωScottContinuous f) :
ωScottContinuous fun (a : α) => ofFun (f a) ⋯

Packaging pointwise continuous functions preserves continuity in their parameter.

Curry a continuous map on a product.

Equations
Instances For

    Uncurry a continuous map into a space of continuous maps.

    Equations
    Instances For

      Exchange two continuous arguments.

      Equations
      Instances For
        def OmegaCompletePartialOrder.ContinuousHom.ofEq {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i j : ι} (h : i = j) :
        D i →𝒄 D j

        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
          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_apply {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i j : ι} (h : i = j) (x : D i) :
          (ofEq D h) x = cast ⋯ x
          @[simp]
          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_self {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i : ι} (h : i = i) (x : D i) :
          (ofEq D h) x = x

          Transport along any equation of an index with itself is the identity.

          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_heq {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i j : ι} (h : i = j) (x : D i) :
          (ofEq D h) x ≍ x

          Transport keeps the value, across the equal members of the family.

          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_eq_iff {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i j : ι} (h : i = j) (x : D i) (y : D j) :
          (ofEq D h) x = y ↔ x ≍ y

          Equality after transport is heterogeneous equality before it.

          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_ofEq {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] {i j k : ι} (h : i = j) (h' : j = k) (x : D i) :
          (ofEq D h') ((ofEq D h) x) = (ofEq D ⋯) x

          Successive transports compose.

          @[simp]
          theorem OmegaCompletePartialOrder.ContinuousHom.ofEq_bot {ι : Type u_4} (D : ι → Type u_5) [(i : ι) → OmegaCompletePartialOrder (D i)] [(i : ι) → OrderBot (D i)] {i j : ι} (h : i = j) :
          (ofEq D h) ⊥ = ⊥

          Transport keeps the least element.

          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.

              theorem OmegaCompletePartialOrder.ContinuousHom.fix_le {α : Type u_1} [OmegaCompletePartialOrder α] [OrderBot α] (f : α →𝒄 α) {x : α} (h : f x ≤ x) :
              f.fix ≤ x

              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.

              theorem OmegaCompletePartialOrder.ContinuousHom.fix_induction {α : Type u_1} [OmegaCompletePartialOrder α] [OrderBot α] (f : α →𝒄 α) (p : α → Prop) (hbot : p ⊥) (hstep : ∀ (x : α), p x → p (f x)) (hclosed : ∀ (c : Chain α), (∀ (n : ℕ), p (c n)) → p (ωSup c)) :
              p f.fix

              Induction over finite approximations followed by an admissibility step.

              theorem OmegaCompletePartialOrder.ContinuousHom.fix_fusion {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] [OrderBot α] [OrderBot β] (f : α →𝒄 α) (g : β →𝒄 β) (h : α →𝒄 β) (hbot : h ⊥ = ⊥) (hcomm : ∀ (x : α), h (f x) = g (h x)) :
              h f.fix = g.fix

              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.

              Equations
              Instances For