mathlib documentation

control.fix

Fixed point

This module defines a generic fix operator for defining recursive computations that are not necessarily well-founded or productive. An instance is defined for roption.

Main definition

@[class]
structure has_fix  :
Type u_3Type u_3
  • fix : (α → α) → α

has_fix α gives us a way to calculate the fixed point of function of type α → α.

Instances
def roption.fix.approx {α : Type u_1} {β : α → Type u_2} :
((Π (a : α), roption (β a))Π (a : α), roption (β a))stream (Π (a : α), roption (β a))

A series of successive, finite approximation of the fixed point of f, defined by approx f n = f^[n] ⊥. The limit of this chain is the fixed point of f.

Equations
def roption.fix_aux {α : Type u_1} {β : α → Type u_2} (f : (Π (a : α), roption (β a))Π (a : α), roption (β a)) {p : → Prop} (i : nat.upto p) (g : Π (j : nat.upto p), i < jΠ (a : α), roption (β a)) (a : α) :
roption (β a)

loop body for finding the fixed point of f

Equations
def roption.fix {α : Type u_1} {β : α → Type u_2} (f : (Π (a : α), roption (β a))Π (a : α), roption (β a)) (x : α) :
roption (β x)

The least fixed point of f.

If f is a continuous function (according to complete partial orders), it satisfies the equations:

  1. fix f = f (fix f) (is a fixed point)
  2. ∀ X, f X ≤ X → fix f ≤ X (least fixed point)
Equations
theorem roption.fix_def {α : Type u_1} {β : α → Type u_2} (f : (Π (a : α), roption (β a))Π (a : α), roption (β a)) {x : α} (h' : ∃ (i : ), (roption.fix.approx f i x).dom) :

theorem roption.fix_def' {α : Type u_1} {β : α → Type u_2} (f : (Π (a : α), roption (β a))Π (a : α), roption (β a)) {x : α} :
(¬∃ (i : ), (roption.fix.approx f i x).dom)roption.fix f x = roption.none

@[instance]
def roption.has_fix {α : Type u_1} :

Equations
@[instance]
def pi.roption.has_fix {α : Type u_1} {β : Type u_2} :
has_fix (α → roption β)

Equations