Reference · Foundations

rainbow.math.constructive-unique-fixed-point

Foundationssrc/rainbow/math/constructive_unique_fixed_point.clj0 definitions, 3 theorems

In Rainbow 1.4.1, lein verify rainbow.math.constructive-unique-fixed-point fails on its own: the module uses lemmas from math.logic.strict-contraction-stabilization, math.finite.metric-separation, math.nat.distance-core, math.nat.metric-separation, math.logic.strict-contraction-uniqueness without listing them in its dependencies. It checks once those are installed.

Constructive existence and support-relative uniqueness for strict Nat contractions.

metric/strict-contraction-bounded-fixed-point-agrees-with-fixed-point.{u} :
  (A : Type u) (source : Finset A) (transform : (A → ℕ) → A → ℕ) (initial : A → ℕ)
  (strictly-contracts : ∀ (left : A → ℕ), ∀ (right : A → ℕ), ∀ (positive : nat/strict-below 0 (metric/finite-sup-distance A source left right)), nat/strict-below (metric/finite-sup-distance A source (transform left) (transform right)) (metric/finite-sup-distance A source left right))
  (steps : ℕ)
  (bounded : steps ≤ metric/finite-sup-distance A source initial (transform initial))
  (iterate-fixed : ∀ (state : A), ∀ (member : state ∈ source), transform (iterate) state = iterate state)
  (candidate : A → ℕ)
  (candidate-fixed : ∀ (state : A), ∀ (member : state ∈ source), transform candidate state = candidate state)
  (state : A)
  (member : state ∈ source)
  → iterate state = candidate state
  where iterate := function/nat-iterate (A → ℕ) transform steps initial

metric/strict-contraction-has-bounded-canonical-support-fixed-point.{u} :
  (A : Type u) (source : Finset A) (transform : (A → ℕ) → A → ℕ) (initial : A → ℕ)
  (strictly-contracts : ∀ (left : A → ℕ), ∀ (right : A → ℕ), ∀ (positive : nat/strict-below 0 (metric/finite-sup-distance A source left right)), nat/strict-below (metric/finite-sup-distance A source (transform left) (transform right)) (metric/finite-sup-distance A source left right))
  → proposition/existence ℕ (fun steps => proposition/conjunction (steps ≤ distance) (proposition/conjunction (∀ (state : A), ∀ (member : state ∈ source), transform (function/nat-iterate (A → ℕ) transform steps initial) state = function/nat-iterate (A → ℕ) transform steps initial state) (∀ (candidate : A → ℕ), ∀ (candidate-fixed : ∀ (state : A), ∀ (member : state ∈ source), transform candidate state = candidate state), ∀ (state : A), ∀ (member : state ∈ source), function/nat-iterate (A → ℕ) transform steps initial state = candidate state)))
  where distance := metric/finite-sup-distance A source initial (transform initial)

metric/strict-contraction-support-fixed-point-exists-and-is-unique.{u} :
  (A : Type u) (source : Finset A) (transform : (A → ℕ) → A → ℕ) (initial : A → ℕ)
  (strictly-contracts : ∀ (left : A → ℕ), ∀ (right : A → ℕ), ∀ (positive : nat/strict-below 0 (metric/finite-sup-distance A source left right)), nat/strict-below (metric/finite-sup-distance A source (transform left) (transform right)) (metric/finite-sup-distance A source left right))
  → proposition/conjunction (existence) (∀ (left : A → ℕ), ∀ (right : A → ℕ), ∀ (left-fixed : ∀ (state : A), ∀ (member : state ∈ source), transform left state = left state), ∀ (right-fixed : ∀ (state : A), ∀ (member : state ∈ source), transform right state = right state), ∀ (state : A), ∀ (member : state ∈ source), left state = right state)
  where existence := proposition/existence (A → ℕ) (fun value => ∀ (state : A), ∀ (member : state ∈ source), transform value state = value state)