Documentation

ToCslib.Order.Admissible

Predicates closed under increasing suprema #

Admissible predicates support fixed-point induction and logical relations for lazy values. Closure is preserved by continuous inverse images, universal quantification, disjoint sums, and adjoining bottom. Admissible.fix_induction states fixed-point induction with this hypothesis.

A predicate closed under suprema of increasing sequences.

Equations
Instances For
    theorem OmegaCompletePartialOrder.Admissible.fix_induction {α : Type u_1} [OmegaCompletePartialOrder α] [OrderBot α] {p : α → Prop} (hp : Admissible p) (f : α →𝒄 α) (hbot : p ⊥) (hstep : ∀ (x : α), p x → p (f x)) :
    p f.fix

    Fixed-point induction for an admissible predicate: it holds at the least fixed point when it holds at bottom and is preserved by the recursive body.

    theorem OmegaCompletePartialOrder.Admissible.fix_induction₂ {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] [OrderBot α] [OrderBot β] {p : α → β → Prop} (hp : Admissible fun (q : α × β) => p q.1 q.2) (f : α →𝒄 α) (g : β →𝒄 β) (hbot : p ⊥ ⊥) (hstep : ∀ (x : α) (y : β), p x y → p (f x) (g y)) :
    p f.fix g.fix

    Fixed-point induction for a relation between two least fixed points: it holds of the pair when it holds at bottom and the recursive bodies preserve it in lockstep.

    theorem OmegaCompletePartialOrder.Admissible.comp {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] {p : β → Prop} (hp : Admissible p) (f : α →𝒄 β) :
    Admissible fun (a : α) => p (f a)

    Continuous inverse images of admissible predicates are admissible.

    theorem OmegaCompletePartialOrder.admissible_graph {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] (f : α →𝒄 β) :
    Admissible fun (p : α × β) => f p.1 = p.2

    The graph of a continuous map is admissible.

    theorem OmegaCompletePartialOrder.Admissible.forall {α : Type u_1} [OmegaCompletePartialOrder α] {ι : Sort u_3} {p : ι → α → Prop} (h : ∀ (i : ι), Admissible (p i)) :
    Admissible fun (a : α) => ∀ (i : ι), p i a

    Admissibility is preserved by universal quantification.

    Every predicate on an equality-ordered type is admissible.

    theorem OmegaCompletePartialOrder.Admissible.sum {α : Type u_1} {β : Type u_2} [OmegaCompletePartialOrder α] [OmegaCompletePartialOrder β] {p : α → Prop} {q : β → Prop} (hp : Admissible p) (hq : Admissible q) :

    Disjoint case analysis preserves admissibility.

    An admissible predicate on values remains admissible when bottom is accepted in the lifted domain.