| /- | |
| Copyright (c) 2024 Lean FRO, LLC. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Joachim Breitner | |
| -/ | |
| module | |
| prelude | |
| public import Init.System.IO -- for `MonoBind` instance | |
| import all Init.Control.Except -- for `MonoBind` instance | |
| import all Init.Control.StateRef -- for `MonoBind` instance | |
| import all Init.Control.Option -- for `MonoBind` instance | |
| import all Init.System.ST -- for `MonoBind` instance | |
| import Init.ByCases | |
| public section | |
| /-! | |
| This module contains some basic definitions and results from domain theory, intended to be used as | |
| the underlying construction of the `partial_fixpoint` feature. It is not meant to be used as a | |
| general purpose library for domain theory, but can be of interest to users who want to extend | |
| the `partial_fixpoint` machinery (e.g. mark more functions as monotone or register more monads). | |
| This follows the corresponding | |
| [Isabelle development](https://isabelle.in.tum.de/library/HOL/HOL/Partial_Function.html), as also | |
| described in [Alexander Krauss: Recursive Definitions of Monadic Functions](https://www21.in.tum.de/~krauss/papers/mrec.pdf). | |
| -/ | |
| universe u v w | |
| namespace Lean.Order | |
| /-- | |
| A partial order is a reflexive, transitive and antisymmetric relation. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| class PartialOrder (α : Sort u) where | |
| /-- | |
| A “less-or-equal-to” or “approximates” relation. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| rel : α → α → Prop | |
| /-- The “less-or-equal-to” or “approximates” relation is reflexive. -/ | |
| rel_refl : ∀ {x}, rel x x | |
| /-- The “less-or-equal-to” or “approximates” relation is transitive. -/ | |
| rel_trans : ∀ {x y z}, rel x y → rel y z → rel x z | |
| /-- The “less-or-equal-to” or “approximates” relation is antisymmetric. -/ | |
| rel_antisymm : ∀ {x y}, rel x y → rel y x → x = y | |
| @[inherit_doc] scoped infix:50 " ⊑ " => PartialOrder.rel | |
| section PartialOrder | |
| variable {α : Sort u} [PartialOrder α] | |
| theorem PartialOrder.rel_of_eq {x y : α} (h : x = y) : x ⊑ y := by cases h; apply rel_refl | |
| /-- | |
| A chain is a totally ordered set (representing a set as a predicate). | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| @[expose] def chain (c : α → Prop) : Prop := ∀ x y , c x → c y → x ⊑ y ∨ y ⊑ x | |
| @[expose] def is_sup {α : Sort u} [PartialOrder α] (c : α → Prop) (s : α) : Prop := | |
| ∀ x, s ⊑ x ↔ (∀ y, c y → y ⊑ x) | |
| theorem is_sup_unique {α} [PartialOrder α] {c : α → Prop} {s₁ s₂ : α} | |
| (h₁ : is_sup c s₁) (h₂ : is_sup c s₂) : s₁ = s₂ := by | |
| apply PartialOrder.rel_antisymm | |
| · apply (h₁ s₂).mpr | |
| intro y hy | |
| apply (h₂ s₂).mp PartialOrder.rel_refl y hy | |
| · apply (h₂ s₁).mpr | |
| intro y hy | |
| apply (h₁ s₁).mp PartialOrder.rel_refl y hy | |
| end PartialOrder | |
| section CCPO | |
| open PartialOrder | |
| /-- | |
| A chain-complete partial order (CCPO) is a partial order where every chain has a least upper bound. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used | |
| otherwise. | |
| -/ | |
| class CCPO (α : Sort u) extends PartialOrder α where | |
| /-- | |
| The least upper bound of chains exists. | |
| -/ | |
| has_csup {c : α → Prop} (hc : chain c) : Exists (is_sup c) | |
| open CCPO | |
| variable {α : Sort u} [CCPO α] | |
| noncomputable def CCPO.csup {c : α → Prop} (hc : chain c) : α := | |
| Classical.choose (CCPO.has_csup hc) | |
| theorem CCPO.csup_spec {c : α → Prop} (hc : chain c) : is_sup c (csup hc) := | |
| @fun x => Classical.choose_spec (CCPO.has_csup hc) x | |
| theorem csup_le {c : α → Prop} (hc : chain c) : (∀ y, c y → y ⊑ x) → csup hc ⊑ x := | |
| (csup_spec hc x).mpr | |
| theorem le_csup {c : α → Prop} (hc : chain c) {y : α} (hy : c y) : y ⊑ csup hc := | |
| (csup_spec hc (csup hc)).mp rel_refl y hy | |
| def empty_chain (α) : α → Prop := fun _ => False | |
| def chain_empty (α : Sort u) [PartialOrder α] : chain (empty_chain α) := by | |
| intro x y hx hy; contradiction | |
| /-- | |
| The bottom element is the least upper bound of the empty chain. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| noncomputable def bot : α := csup (chain_empty α) | |
| scoped notation "⊥" => bot | |
| theorem bot_le (x : α) : ⊥ ⊑ x := by | |
| apply csup_le | |
| intro x y; contradiction | |
| end CCPO | |
| section CompleteLattice | |
| /-- | |
| A complete lattice is a partial order where every subset has a least upper bound. | |
| -/ | |
| class CompleteLattice (α : Sort u) extends PartialOrder α where | |
| /-- | |
| The least upper bound of an arbitrary subset exists. | |
| -/ | |
| has_sup (c : α → Prop) : Exists (is_sup c) | |
| open PartialOrder CompleteLattice | |
| variable {α : Sort u} [CompleteLattice α] | |
| noncomputable def CompleteLattice.sup (c : α → Prop) : α := | |
| Classical.choose (CompleteLattice.has_sup c) | |
| theorem CompleteLattice.sup_spec (c : α → Prop) : is_sup c (sup c) := | |
| @fun x => Classical.choose_spec (CompleteLattice.has_sup c) x | |
| theorem sup_le (c : α → Prop) : (∀ y, c y → y ⊑ x) → sup c ⊑ x := | |
| Iff.mpr (sup_spec c x) | |
| theorem le_sup (c : α → Prop) {y : α} (hy : c y) : y ⊑ sup c := | |
| Iff.mp (sup_spec c (sup c)) rel_refl y hy | |
| noncomputable def inf (c : α → Prop) : α := sup (∀ y, c y → · ⊑ y) | |
| theorem inf_spec {c : α → Prop} : x ⊑ inf c ↔ (∀ y, c y → x ⊑ y) where | |
| mp := by | |
| unfold inf | |
| intro h | |
| intro y cy | |
| suffices g : (sup fun x => ∀ (y : α), c y → x ⊑ y) ⊑ y from | |
| by | |
| apply rel_trans h g | |
| apply sup_le | |
| intro z | |
| intro i | |
| exact i y cy | |
| mpr := by | |
| unfold inf | |
| intro h | |
| apply le_sup | |
| apply h | |
| theorem le_inf {c : α → Prop} : (∀ y, c y → x ⊑ y) → x ⊑ inf c := inf_spec.mpr | |
| theorem inf_le {c : α → Prop} {y : α} (hy : c y) : inf c ⊑ y := inf_spec.mp (rel_refl) y hy | |
| end CompleteLattice | |
| section monotone | |
| variable {α : Sort u} [PartialOrder α] | |
| variable {β : Sort v} [PartialOrder β] | |
| /-- | |
| A function is monotone if it maps related elements to related elements. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| @[expose] def monotone (f : α → β) : Prop := ∀ x y, x ⊑ y → f x ⊑ f y | |
| theorem monotone_const (c : β) : monotone (fun (_ : α) => c) := | |
| fun _ _ _ => PartialOrder.rel_refl | |
| theorem monotone_id : monotone (fun (x : α) => x) := | |
| fun _ _ hxy => hxy | |
| theorem monotone_compose | |
| {γ : Sort w} [PartialOrder γ] | |
| {f : α → β} {g : β → γ} | |
| (hf : monotone f) (hg : monotone g) : | |
| monotone (fun x => g (f x)) := fun _ _ hxy => hg _ _ (hf _ _ hxy) | |
| end monotone | |
| section admissibility | |
| variable {α : Sort u} [CCPO α] | |
| open PartialOrder CCPO | |
| /-- | |
| A predicate is admissible if it can be transferred from the elements of a chain to the chains least | |
| upper bound. Such predicates can be used in fixpoint induction. | |
| This definition implies `P ⊥`. Sometimes (e.g. in Isabelle) the empty chain is excluded | |
| from this definition, and `P ⊥` is a separate condition of the induction predicate. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| def admissible (P : α → Prop) := | |
| ∀ (c : α → Prop) (hc : chain c), (∀ x, c x → P x) → P (csup hc) | |
| theorem admissible_const_true : admissible (fun (_ : α) => True) := | |
| fun _ _ _ => trivial | |
| theorem admissible_and (P Q : α → Prop) | |
| (hadm₁ : admissible P) (hadm₂ : admissible Q) : admissible (fun x => P x ∧ Q x) := | |
| fun c hchain h => | |
| ⟨ hadm₁ c hchain fun x hx => (h x hx).1, | |
| hadm₂ c hchain fun x hx => (h x hx).2⟩ | |
| theorem chain_conj (c P : α → Prop) (hchain : chain c) : chain (fun x => c x ∧ P x) := by | |
| intro x y ⟨hcx, _⟩ ⟨hcy, _⟩ | |
| exact hchain x y hcx hcy | |
| theorem csup_conj (c P : α → Prop) (hchain : chain c) (h : ∀ x, c x → ∃ y, c y ∧ x ⊑ y ∧ P y) : | |
| csup hchain = csup (chain_conj c P hchain) := by | |
| apply rel_antisymm | |
| · apply csup_le hchain | |
| intro x hcx | |
| obtain ⟨y, hcy, hxy, hPy⟩ := h x hcx | |
| apply rel_trans hxy; clear x hcx hxy | |
| apply le_csup (chain_conj _ _ hchain) ⟨hcy, hPy⟩ | |
| · apply csup_le (chain_conj _ _ hchain) | |
| intro x ⟨hcx, hPx⟩ | |
| apply le_csup hchain hcx | |
| theorem admissible_or (P Q : α → Prop) | |
| (hadm₁ : admissible P) (hadm₂ : admissible Q) : admissible (fun x => P x ∨ Q x) := by | |
| intro c hchain h | |
| have : (∀ x, c x → ∃ y, c y ∧ x ⊑ y ∧ P y) ∨ (∀ x, c x → ∃ y, c y ∧ x ⊑ y ∧ Q y) := by | |
| open Classical in | |
| apply Decidable.or_iff_not_imp_left.mpr | |
| intro h' | |
| simp only [not_forall, not_exists, not_and] at h' | |
| obtain ⟨x, hcx, hx⟩ := h' | |
| intro y hcy | |
| cases hchain x y hcx hcy with | |
| | inl hxy => | |
| refine ⟨y, hcy, rel_refl, ?_⟩ | |
| cases h y hcy with | |
| | inl hPy => exfalso; apply hx y hcy hxy hPy | |
| | inr hQy => assumption | |
| | inr hyx => | |
| refine ⟨x, hcx, hyx , ?_⟩ | |
| cases h x hcx with | |
| | inl hPx => exfalso; apply hx x hcx rel_refl hPx | |
| | inr hQx => assumption | |
| cases this with | |
| | inl hP => | |
| left | |
| rw [csup_conj (h := hP) (hchain := hchain)] | |
| apply hadm₁ _ (chain_conj _ _ hchain) | |
| intro x ⟨hcx, hPx⟩ | |
| exact hPx | |
| | inr hQ => | |
| right | |
| rw [csup_conj (h := hQ) (hchain := hchain)] | |
| apply hadm₂ _ (chain_conj _ _ hchain) | |
| intro x ⟨hcx, hQx⟩ | |
| exact hQx | |
| def admissible_pi (P : α → β → Prop) | |
| (hadm₁ : ∀ y, admissible (fun x => P x y)) : admissible (fun x => ∀ y, P x y) := | |
| fun c hchain h y => hadm₁ y c hchain fun x hx => h x hx y | |
| end admissibility | |
| section lattice_fix | |
| open PartialOrder CompleteLattice | |
| variable {α : Sort u} [CompleteLattice α] | |
| variable {c : α → Prop} | |
| -- Note that monotonicity is not required for the definition of `lfp` | |
| -- but it is required to show that `lfp` is a fixpoint of `f`. | |
| noncomputable def lfp (f : α → α) : α := | |
| inf (fun c => f c ⊑ c) | |
| set_option linter.unusedVariables false in | |
| -- The following definition takes a witness that a function is monotone | |
| noncomputable def lfp_monotone (f : α → α) (hm : monotone f) : α := | |
| lfp f | |
| -- Showing that `lfp` is a prefixed point makes use of monotonicity | |
| theorem lfp_prefixed {f : α → α} {hm : monotone f} : | |
| f (lfp f) ⊑ (lfp f) := by | |
| apply le_inf | |
| intro y hy | |
| suffices h : f (lfp f) ⊑ f y from by | |
| apply rel_trans h hy | |
| apply hm | |
| apply inf_le | |
| exact hy | |
| -- So does showing that `lfp` is a postfixed point | |
| theorem lfp_postfixed {f : α → α} {hm : monotone f} : lfp f ⊑ f (lfp f) := by | |
| apply inf_le | |
| apply hm | |
| apply lfp_prefixed | |
| exact hm | |
| -- `lfp` being a fixpoint now follows as an easy corollary | |
| theorem lfp_fix {f : α → α} (hm : monotone f) : | |
| lfp f = f (lfp f) := by | |
| apply rel_antisymm | |
| . apply lfp_postfixed | |
| exact hm | |
| . apply lfp_prefixed | |
| exact hm | |
| -- Same as above, but uses the version of `lfp` that takes a witness of monotonicity | |
| theorem lfp_monotone_fix {f : α → α} {hm : monotone f} : | |
| lfp_monotone f hm = f (lfp_monotone f hm) := lfp_fix hm | |
| /-- | |
| Park induction principle for least fixpoint. | |
| In general, this construction does not require monotonicity of `f`. | |
| Monotonicity is required to show that `lfp f` is indeed a fixpoint of `f`. | |
| -/ | |
| theorem lfp_le_of_le {f : α → α} : | |
| f x ⊑ x → lfp f ⊑ x := fun hx => inf_le hx | |
| /-- | |
| Park induction for least fixpoint of a monotone function `f`. | |
| Takes an explicit witness of `f` being monotone. | |
| -/ | |
| theorem lfp_le_of_le_monotone (f : α → α) {hm : monotone f} (x : α): | |
| f x ⊑ x → lfp_monotone f hm ⊑ x := by | |
| unfold lfp_monotone | |
| apply lfp_le_of_le | |
| end lattice_fix | |
| section fix | |
| open PartialOrder CCPO | |
| variable {α : Sort u} [CCPO α] | |
| variable {c : α → Prop} (hchain : chain c) | |
| /-- | |
| The transfinite iteration of a function `f` is a set that is `⊥ ` and is closed under application | |
| of `f` and `csup`. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| inductive iterates (f : α → α) : α → Prop where | |
| | step : iterates f x → iterates f (f x) | |
| | sup {c : α → Prop} (hc : chain c) (hi : ∀ x, c x → iterates f x) : iterates f (csup hc) | |
| theorem chain_iterates {f : α → α} (hf : monotone f) : chain (iterates f) := by | |
| intro x y hx hy | |
| induction hx generalizing y | |
| case step x hx ih => | |
| induction hy | |
| case step y hy _ => | |
| cases ih y hy | |
| · left; apply hf; assumption | |
| · right; apply hf; assumption | |
| case sup c hchain hi ih2 => | |
| change f x ⊑ csup hchain ∨ csup hchain ⊑ f x | |
| by_cases h : ∃ z, c z ∧ f x ⊑ z | |
| · left | |
| obtain ⟨z, hz, hfz⟩ := h | |
| apply rel_trans hfz | |
| apply le_csup hchain hz | |
| · right | |
| apply csup_le hchain _ | |
| intro z hz | |
| rw [not_exists] at h | |
| specialize h z | |
| rw [not_and] at h | |
| specialize h hz | |
| cases ih2 z hz | |
| next => contradiction | |
| next => assumption | |
| case sup c hchain hi ih => | |
| change rel (csup hchain) y ∨ rel y (csup hchain) | |
| by_cases h : ∃ z, c z ∧ rel y z | |
| · right | |
| obtain ⟨z, hz, hfz⟩ := h | |
| apply rel_trans hfz | |
| apply le_csup hchain hz | |
| · left | |
| apply csup_le hchain _ | |
| intro z hz | |
| rw [not_exists] at h | |
| specialize h z | |
| rw [not_and] at h | |
| specialize h hz | |
| cases ih z hz y hy | |
| next => assumption | |
| next => contradiction | |
| theorem rel_f_of_iterates {f : α → α} (hf : monotone f) {x : α} (hx : iterates f x) : x ⊑ f x := by | |
| induction hx | |
| case step ih => | |
| apply hf | |
| assumption | |
| case sup c hchain hi ih => | |
| apply csup_le hchain | |
| intro y hy | |
| apply rel_trans (ih y hy) | |
| apply hf | |
| apply le_csup hchain hy | |
| set_option linter.unusedVariables false in | |
| /-- | |
| The least fixpoint of a monotone function is the least upper bound of its transfinite iteration. | |
| The `monotone f` assumption is not strictly necessarily for the definition, but without this the | |
| definition is not very meaningful and it simplifies applying theorems like `fix_eq` if every use of | |
| `fix` already has the monotonicity requirement. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| noncomputable def fix (f : α → α) (hmono : monotone f) := csup (chain_iterates hmono) | |
| /-- | |
| The main fixpoint theorem for fixed points of monotone functions in chain-complete partial orders. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| theorem fix_eq {f : α → α} (hf : monotone f) : fix f hf = f (fix f hf) := by | |
| apply rel_antisymm | |
| · apply rel_f_of_iterates hf | |
| apply iterates.sup (chain_iterates hf) | |
| exact fun _ h => h | |
| · apply le_csup (chain_iterates hf) | |
| apply iterates.step | |
| apply iterates.sup (chain_iterates hf) | |
| intro y hy | |
| exact hy | |
| /-- | |
| The fixpoint induction theme: An admissible predicate holds for a least fixpoint if it is preserved | |
| by the fixpoint's function. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| theorem fix_induct {f : α → α} (hf : monotone f) | |
| (motive : α → Prop) (hadm: admissible motive) | |
| (h : ∀ x, motive x → motive (f x)) : motive (fix f hf) := by | |
| apply hadm _ (chain_iterates hf) | |
| intro x hiterates | |
| induction hiterates with | |
| | @step x hiter ih => apply h x ih | |
| | @sup c hchain hiter ih => apply hadm c hchain ih | |
| end fix | |
| section fun_order | |
| open PartialOrder | |
| variable {α : Sort u} | |
| variable {β : α → Sort v} | |
| variable {γ : Sort w} | |
| instance instOrderPi [∀ x, PartialOrder (β x)] : PartialOrder (∀ x, β x) where | |
| rel f g := ∀ x, f x ⊑ g x | |
| rel_refl _ := rel_refl | |
| rel_trans hf hg x := rel_trans (hf x) (hg x) | |
| rel_antisymm hf hg := funext (fun x => rel_antisymm (hf x) (hg x)) | |
| theorem monotone_of_monotone_apply [PartialOrder γ] [∀ x, PartialOrder (β x)] (f : γ → (∀ x, β x)) | |
| (h : ∀ y, monotone (fun x => f x y)) : monotone f := | |
| fun x y hxy z => h z x y hxy | |
| theorem monotone_apply [PartialOrder γ] [∀ x, PartialOrder (β x)] (a : α) (f : γ → ∀ x, β x) | |
| (h : monotone f) : | |
| monotone (fun x => f x a) := fun _ _ hfg => h _ _ hfg a | |
| theorem chain_apply [∀ x, PartialOrder (β x)] {c : (∀ x, β x) → Prop} (hc : chain c) (x : α) : | |
| chain (fun y => ∃ f, c f ∧ f x = y) := by | |
| intro _ _ ⟨f, hf, hfeq⟩ ⟨g, hg, hgeq⟩ | |
| subst hfeq; subst hgeq | |
| cases hc f g hf hg | |
| next h => left; apply h x | |
| next h => right; apply h x | |
| noncomputable def fun_csup [∀ x, CCPO (β x)] (c : (∀ x, β x) → Prop) (hc : chain c) (x : α) := | |
| CCPO.csup (chain_apply hc x) | |
| theorem fun_csup_is_sup [∀ x, CCPO (β x)] (c : (∀ x, β x) → Prop) (hc : chain c) : | |
| is_sup c (fun_csup c hc) := by | |
| intro f | |
| constructor | |
| next => | |
| intro hf g hg x | |
| apply rel_trans _ (hf x); clear hf | |
| apply le_csup (chain_apply hc x) | |
| exact ⟨g, hg, rfl⟩ | |
| next => | |
| intro h x | |
| apply csup_le (chain_apply hc x) | |
| intro y ⟨z, hz, hyz⟩ | |
| subst y | |
| apply h z hz | |
| instance instCCPOPi [∀ x, CCPO (β x)] : CCPO (∀ x, β x) where | |
| has_csup hc := ⟨fun_csup _ hc, fun_csup_is_sup _ hc⟩ | |
| theorem fun_csup_eq [∀ x, CCPO (β x)] (c : (∀ x, β x) → Prop) (hc : chain c) : | |
| fun_csup c hc = CCPO.csup hc := by | |
| apply is_sup_unique (c := c) | |
| · apply fun_csup_is_sup | |
| · apply CCPO.csup_spec | |
| noncomputable def fun_sup [∀ x, CompleteLattice (β x)] (c : (∀ x, β x) → Prop) (x : α) := | |
| CompleteLattice.sup (fun y => ∃ f, c f ∧ f x = y) | |
| theorem fun_sup_is_sup [∀ x, CompleteLattice (β x)] (c : (∀ x, β x) → Prop) : | |
| is_sup c (fun_sup c) := by | |
| intro f | |
| constructor | |
| case mp => | |
| intro hf g hg x | |
| apply rel_trans _ (hf x) | |
| apply le_sup | |
| exact ⟨g, hg, rfl⟩ | |
| case mpr => | |
| intro h x | |
| apply sup_le | |
| intro y ⟨z, hz, hyz⟩ | |
| subst y | |
| apply h z hz | |
| instance instCompleteLatticePi [∀ x, CompleteLattice (β x)] : CompleteLattice (∀ x, β x) where | |
| has_sup c := ⟨fun_sup c, fun_sup_is_sup c⟩ | |
| theorem fun_sup_eq [∀ x, CompleteLattice (β x)] (c : (∀ x, β x) → Prop) : | |
| fun_sup c = CompleteLattice.sup c := by | |
| apply is_sup_unique (c := c) | |
| · apply fun_sup_is_sup | |
| · apply CompleteLattice.sup_spec | |
| def admissible_apply [∀ x, CCPO (β x)] (P : ∀ x, β x → Prop) (x : α) | |
| (hadm : admissible (P x)) : admissible (fun (f : ∀ x, β x) => P x (f x)) := by | |
| intro c hchain h | |
| rw [← fun_csup_eq] | |
| apply hadm _ (chain_apply hchain x) | |
| rintro _ ⟨f, hcf, rfl⟩ | |
| apply h _ hcf | |
| def admissible_pi_apply [∀ x, CCPO (β x)] (P : ∀ x, β x → Prop) (hadm : ∀ x, admissible (P x)) : | |
| admissible (fun (f : ∀ x, β x) => ∀ x, P x (f x)) := by | |
| apply admissible_pi | |
| intro | |
| apply admissible_apply | |
| apply hadm | |
| end fun_order | |
| section monotone_lemmas | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_ite | |
| {α : Sort u} {β : Sort v} [PartialOrder α] [PartialOrder β] | |
| (c : Prop) [Decidable c] | |
| (k₁ : α → β) (k₂ : α → β) | |
| (hmono₁ : monotone k₁) (hmono₂ : monotone k₂) : | |
| monotone fun x => if c then k₁ x else k₂ x := by | |
| split | |
| · apply hmono₁ | |
| · apply hmono₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_dite | |
| {α : Sort u} {β : Sort v} [PartialOrder α] [PartialOrder β] | |
| (c : Prop) [Decidable c] | |
| (k₁ : α → c → β) (k₂ : α → ¬ c → β) | |
| (hmono₁ : monotone k₁) (hmono₂ : monotone k₂) : | |
| monotone fun x => dite c (k₁ x) (k₂ x) := by | |
| split | |
| · apply monotone_apply _ _ hmono₁ | |
| · apply monotone_apply _ _ hmono₂ | |
| end monotone_lemmas | |
| section pprod_order | |
| open PartialOrder | |
| variable {α : Sort u} | |
| variable {β : Sort v} | |
| variable {γ : Sort w} | |
| instance [PartialOrder α] [PartialOrder β] : PartialOrder (α ×' β) where | |
| rel a b := a.1 ⊑ b.1 ∧ a.2 ⊑ b.2 | |
| rel_refl := ⟨rel_refl, rel_refl⟩ | |
| rel_trans ha hb := ⟨rel_trans ha.1 hb.1, rel_trans ha.2 hb.2⟩ | |
| rel_antisymm := fun {a} {b} ha hb => by | |
| cases a; cases b; | |
| dsimp at * | |
| rw [rel_antisymm ha.1 hb.1, rel_antisymm ha.2 hb.2] | |
| @[partial_fixpoint_monotone] | |
| theorem PProd.monotone_mk [PartialOrder α] [PartialOrder β] [PartialOrder γ] | |
| {f : γ → α} {g : γ → β} (hf : monotone f) (hg : monotone g) : | |
| monotone (fun x => PProd.mk (f x) (g x)) := | |
| fun _ _ h12 => ⟨hf _ _ h12, hg _ _ h12⟩ | |
| @[partial_fixpoint_monotone] | |
| theorem PProd.monotone_fst [PartialOrder α] [PartialOrder β] [PartialOrder γ] | |
| {f : γ → α ×' β} (hf : monotone f) : monotone (fun x => (f x).1) := | |
| fun _ _ h12 => (hf _ _ h12).1 | |
| @[partial_fixpoint_monotone] | |
| theorem PProd.monotone_snd [PartialOrder α] [PartialOrder β] [PartialOrder γ] | |
| {f : γ → α ×' β} (hf : monotone f) : monotone (fun x => (f x).2) := | |
| fun _ _ h12 => (hf _ _ h12).2 | |
| def PProd.chain.fst [CCPO α] [CCPO β] (c : α ×' β → Prop) : α → Prop := fun a => ∃ b, c ⟨a, b⟩ | |
| def PProd.chain.snd [CCPO α] [CCPO β] (c : α ×' β → Prop) : β → Prop := fun b => ∃ a, c ⟨a, b⟩ | |
| def PProd.fst [CompleteLattice α] [CompleteLattice β] (c : α ×' β → Prop) : α → Prop := fun a => ∃ b, c ⟨a, b⟩ | |
| def PProd.snd [CompleteLattice α] [CompleteLattice β] (c : α ×' β → Prop) : β → Prop := fun b => ∃ a, c ⟨a, b⟩ | |
| theorem PProd.chain.chain_fst [CCPO α] [CCPO β] {c : α ×' β → Prop} (hchain : chain c) : | |
| chain (chain.fst c) := by | |
| intro a₁ a₂ ⟨b₁, h₁⟩ ⟨b₂, h₂⟩ | |
| cases hchain ⟨a₁, b₁⟩ ⟨a₂, b₂⟩ h₁ h₂ | |
| case inl h => left; exact h.1 | |
| case inr h => right; exact h.1 | |
| theorem PProd.chain.chain_snd [CCPO α] [CCPO β] {c : α ×' β → Prop} (hchain : chain c) : | |
| chain (chain.snd c) := by | |
| intro b₁ b₂ ⟨a₁, h₁⟩ ⟨a₂, h₂⟩ | |
| cases hchain ⟨a₁, b₁⟩ ⟨a₂, b₂⟩ h₁ h₂ | |
| case inl h => left; exact h.2 | |
| case inr h => right; exact h.2 | |
| noncomputable def prod_csup [CCPO α] [CCPO β] (c : α ×' β → Prop) (hchain : chain c) : α ×' β := | |
| ⟨CCPO.csup (PProd.chain.chain_fst hchain), CCPO.csup (PProd.chain.chain_snd hchain)⟩ | |
| theorem prod_csup_is_sup [CCPO α] [CCPO β] (c : α ×' β → Prop) (hchain : chain c) : | |
| is_sup c (prod_csup c hchain) := by | |
| intro ⟨a, b⟩ | |
| constructor | |
| next => | |
| intro ⟨h₁, h₂⟩ ⟨a', b'⟩ cab | |
| constructor <;> dsimp at * | |
| · apply rel_trans ?_ h₁ | |
| apply le_csup (PProd.chain.chain_fst hchain) | |
| exact ⟨b', cab⟩ | |
| · apply rel_trans ?_ h₂ | |
| apply le_csup (PProd.chain.chain_snd hchain) | |
| exact ⟨a', cab⟩ | |
| next => | |
| intro h | |
| constructor <;> dsimp | |
| · apply csup_le (PProd.chain.chain_fst hchain) | |
| intro a' ⟨b', hcab⟩ | |
| apply (h _ hcab).1 | |
| · apply csup_le (PProd.chain.chain_snd hchain) | |
| intro b' ⟨a', hcab⟩ | |
| apply (h _ hcab).2 | |
| instance instCCPOPProd [CCPO α] [CCPO β] : CCPO (α ×' β) where | |
| has_csup hchain := ⟨prod_csup _ hchain, prod_csup_is_sup _ hchain⟩ | |
| theorem prod_csup_eq [CCPO α] [CCPO β] (c : α ×' β → Prop) (hchain : chain c) : | |
| prod_csup c hchain = CCPO.csup hchain := by | |
| apply is_sup_unique (c := c) | |
| · apply prod_csup_is_sup | |
| · apply CCPO.csup_spec | |
| noncomputable def prod_sup [CompleteLattice α] [CompleteLattice β] (c : α ×' β → Prop) : α ×' β := | |
| ⟨CompleteLattice.sup (PProd.fst c), CompleteLattice.sup (PProd.snd c)⟩ | |
| theorem prod_sup_is_sup [CompleteLattice α] [CompleteLattice β] (c : α ×' β → Prop) : | |
| is_sup c (prod_sup c) := by | |
| intro ⟨a, b⟩ | |
| constructor | |
| case mp => | |
| intro ⟨h₁, h₂⟩ ⟨a', b'⟩ cab | |
| constructor <;> dsimp only at * | |
| · apply rel_trans ?_ h₁ | |
| unfold prod_sup PProd.fst at * | |
| apply le_sup | |
| apply Exists.intro b' | |
| exact cab | |
| . apply rel_trans ?_ h₂ | |
| apply le_sup | |
| unfold PProd.snd at * | |
| apply Exists.intro a' | |
| exact cab | |
| case mpr => | |
| intro h | |
| constructor <;> dsimp only | |
| . apply sup_le | |
| unfold PProd.fst | |
| intro y' ex | |
| apply Exists.elim ex | |
| intro b' hc | |
| apply (h ⟨y', b' ⟩ hc).1 | |
| . apply sup_le | |
| unfold PProd.snd | |
| intro b' ex | |
| apply Exists.elim ex | |
| intro y' hc | |
| apply (h ⟨y', b' ⟩ hc).2 | |
| instance instCompleteLatticePProd [CompleteLattice α] [CompleteLattice β] : CompleteLattice (α ×' β) where | |
| has_sup c := ⟨prod_sup c, prod_sup_is_sup c⟩ | |
| theorem admissible_pprod_fst {α : Sort u} {β : Sort v} [CCPO α] [CCPO β] (P : α → Prop) | |
| (hadm : admissible P) : admissible (fun (x : α ×' β) => P x.1) := by | |
| intro c hchain h | |
| rw [<- prod_csup_eq] | |
| apply hadm _ (PProd.chain.chain_fst hchain) | |
| intro x ⟨y, hxy⟩ | |
| apply h ⟨x,y⟩ hxy | |
| theorem admissible_pprod_snd {α : Sort u} {β : Sort v} [CCPO α] [CCPO β] (P : β → Prop) | |
| (hadm : admissible P) : admissible (fun (x : α ×' β) => P x.2) := by | |
| intro c hchain h | |
| rw [<- prod_csup_eq] | |
| apply hadm _ (PProd.chain.chain_snd hchain) | |
| intro y ⟨x, hxy⟩ | |
| apply h ⟨x,y⟩ hxy | |
| end pprod_order | |
| section flat_order | |
| variable {α : Sort u} | |
| set_option linter.unusedVariables false in | |
| /-- | |
| `FlatOrder b` wraps the type `α` with the flat partial order generated by `∀ x, b ⊑ x`. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| @[expose] def FlatOrder {α : Sort u} (b : α) := α | |
| variable {b : α} | |
| /-- | |
| The flat partial order generated by `∀ x, b ⊑ x`. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| inductive FlatOrder.rel : (x y : FlatOrder b) → Prop where | |
| | bot : rel b x | |
| | refl : rel x x | |
| instance FlatOrder.instOrder : PartialOrder (FlatOrder b) where | |
| rel := rel | |
| rel_refl := .refl | |
| rel_trans {x y z : α} (hxy : rel x y) (hyz : rel y z) := by | |
| cases hxy <;> cases hyz <;> constructor | |
| rel_antisymm {x y : α} (hxy : rel x y) (hyz : rel y x) : x = y := by | |
| cases hxy <;> cases hyz <;> constructor | |
| open Classical in | |
| private theorem Classical.some_spec₂ {α : Sort _} {p : α → Prop} {h : ∃ a, p a} (q : α → Prop) | |
| (hpq : ∀ a, p a → q a) : q (choose h) := hpq _ <| choose_spec _ | |
| noncomputable def flat_csup (c : FlatOrder b → Prop) : FlatOrder b := by | |
| by_cases h : ∃ (x : FlatOrder b), c x ∧ x ≠ b | |
| · exact Classical.choose h | |
| · exact b | |
| theorem flat_csup_is_sup (c : FlatOrder b → Prop) (hc : chain c) : | |
| is_sup c (flat_csup c) := by | |
| intro x | |
| unfold flat_csup | |
| split | |
| next hex => | |
| apply Classical.some_spec₂ (q := (· ⊑ x ↔ (∀ y, c y → y ⊑ x))) | |
| clear hex | |
| intro z ⟨hz, hnb⟩ | |
| constructor | |
| · intro h y hy | |
| apply PartialOrder.rel_trans _ h; clear h | |
| cases hc y z hy hz | |
| next => assumption | |
| next h => | |
| cases h | |
| · contradiction | |
| · constructor | |
| · intro h | |
| cases h z hz | |
| · contradiction | |
| · constructor | |
| next hnotex => | |
| constructor | |
| · intro h y hy; clear h | |
| suffices y = b by rw [this]; exact FlatOrder.rel.bot | |
| rw [not_exists] at hnotex | |
| specialize hnotex y | |
| rw [not_and] at hnotex | |
| specialize hnotex hy | |
| rw [@Classical.not_not] at hnotex | |
| assumption | |
| · intro; exact FlatOrder.rel.bot | |
| instance FlatOrder.instCCPO : CCPO (FlatOrder b) where | |
| has_csup hchain := ⟨flat_csup _ , flat_csup_is_sup _ hchain⟩ | |
| theorem flat_csup_eq (c : FlatOrder b → Prop) (hchain : chain c) : | |
| flat_csup c = CCPO.csup hchain := by | |
| apply is_sup_unique (c := c) | |
| · apply flat_csup_is_sup _ hchain | |
| · apply CCPO.csup_spec | |
| theorem admissible_flatOrder (P : FlatOrder b → Prop) (hnot : P b) : admissible P := by | |
| intro c hchain h | |
| by_cases h' : ∃ (x : FlatOrder b), c x ∧ x ≠ b | |
| · simp [← flat_csup_eq, flat_csup, h'] | |
| apply Classical.some_spec₂ (q := (P ·)) | |
| intro x ⟨hcx, hneb⟩ | |
| apply h x hcx | |
| · simp [← flat_csup_eq, flat_csup, h', hnot] | |
| end flat_order | |
| section mono_bind | |
| /-- | |
| The class `MonoBind m` indicates that every `m α` has a `PartialOrder`, and that the bind operation | |
| on `m` is monotone in both arguments with regard to that order. | |
| This is intended to be used in the construction of `partial_fixpoint`, and not meant to be used otherwise. | |
| -/ | |
| class MonoBind (m : Type u → Type v) [Bind m] [∀ α, PartialOrder (m α)] where | |
| bind_mono_left {a₁ a₂ : m α} {f : α → m β} (h : a₁ ⊑ a₂) : a₁ >>= f ⊑ a₂ >>= f | |
| bind_mono_right {a : m α} {f₁ f₂ : α → m β} (h : ∀ x, f₁ x ⊑ f₂ x) : a >>= f₁ ⊑ a >>= f₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_bind | |
| (m : Type u → Type v) [Bind m] [∀ α, PartialOrder (m α)] [MonoBind m] | |
| {α β : Type u} | |
| {γ : Sort w} [PartialOrder γ] | |
| (f : γ → m α) (g : γ → α → m β) | |
| (hmono₁ : monotone f) | |
| (hmono₂ : monotone g) : | |
| monotone (fun (x : γ) => f x >>= g x) := by | |
| intro x₁ x₂ hx₁₂ | |
| apply PartialOrder.rel_trans | |
| · apply MonoBind.bind_mono_left (hmono₁ _ _ hx₁₂) | |
| · apply MonoBind.bind_mono_right (fun y => monotone_apply y _ hmono₂ _ _ hx₁₂) | |
| instance : PartialOrder (Option α) := inferInstanceAs (PartialOrder (FlatOrder none)) | |
| instance : CCPO (Option α) := inferInstanceAs (CCPO (FlatOrder none)) | |
| instance : MonoBind Option where | |
| bind_mono_left h := by | |
| cases h | |
| · exact FlatOrder.rel.bot | |
| · exact FlatOrder.rel.refl | |
| bind_mono_right h := by | |
| cases ‹Option _› | |
| · exact FlatOrder.rel.refl | |
| · exact h _ | |
| theorem Option.admissible_eq_some (P : Prop) (y : α) : | |
| admissible (fun (x : Option α) => x = some y → P) := by | |
| apply admissible_flatOrder; simp | |
| instance [inst : ∀ α, PartialOrder (m α)] : PartialOrder (ExceptT ε m α) := inst _ | |
| instance [inst : ∀ α, CCPO (m α)] : CCPO (ExceptT ε m α) := inst _ | |
| instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (ExceptT ε m) where | |
| bind_mono_left h₁₂ := by | |
| apply MonoBind.bind_mono_left (m := m) | |
| exact h₁₂ | |
| bind_mono_right h₁₂ := by | |
| apply MonoBind.bind_mono_right (m := m) | |
| intro x | |
| cases x | |
| · apply PartialOrder.rel_refl | |
| · apply h₁₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_exceptTRun [PartialOrder γ] | |
| [Monad m] [∀ α, PartialOrder (m α)] | |
| (f : γ → ExceptT ε m α) (hmono : monotone f) : | |
| monotone (fun (x : γ) => ExceptT.run (f x)) := | |
| hmono | |
| instance [inst : ∀ α, PartialOrder (m α)] : PartialOrder (OptionT m α) := inst _ | |
| instance [inst : ∀ α, CCPO (m α)] : CCPO (OptionT m α) := inst _ | |
| instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (OptionT m) where | |
| bind_mono_left h₁₂ := by | |
| apply MonoBind.bind_mono_left (m := m) | |
| exact h₁₂ | |
| bind_mono_right h₁₂ := by | |
| apply MonoBind.bind_mono_right (m := m) | |
| intro x | |
| cases x | |
| · apply PartialOrder.rel_refl | |
| · apply h₁₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_optionTRun [PartialOrder γ] | |
| [Monad m] [∀ α, PartialOrder (m α)] | |
| (f : γ → OptionT m α) (hmono : monotone f) : | |
| monotone (fun (x : γ) => OptionT.run (f x)) := | |
| hmono | |
| instance [inst : PartialOrder (m α)] : PartialOrder (ReaderT ρ m α) := instOrderPi | |
| instance [inst : CCPO (m α)] : CCPO (ReaderT ρ m α) := instCCPOPi | |
| instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (ReaderT ρ m) where | |
| bind_mono_left h₁₂ := by | |
| intro x | |
| apply MonoBind.bind_mono_left (m := m) | |
| exact h₁₂ x | |
| bind_mono_right h₁₂ := by | |
| intro x | |
| apply MonoBind.bind_mono_right (m := m) | |
| intro y | |
| apply h₁₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_readerTRun [PartialOrder γ] | |
| [Monad m] [PartialOrder (m α)] | |
| (f : γ → ReaderT σ m α) (hmono : monotone f) (s : σ) : | |
| monotone (fun (x : γ) => ReaderT.run (f x) s) := | |
| monotone_apply s _ hmono | |
| instance [inst : PartialOrder (m α)] : PartialOrder (StateRefT' ω σ m α) := instOrderPi | |
| instance [inst : CCPO (m α)] : CCPO (StateRefT' ω σ m α) := instCCPOPi | |
| instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (StateRefT' ω σ m) := | |
| inferInstanceAs (MonoBind (ReaderT _ _)) | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_stateRefT'Run [PartialOrder γ] | |
| [Monad m] [MonadLiftT (ST ω) m] [∀ α, PartialOrder (m α)] [MonoBind m] | |
| (f : γ → StateRefT' ω σ m α) (hmono : monotone f) (s : σ) : | |
| monotone (fun (x : γ) => StateRefT'.run (f x) s) := by | |
| apply monotone_bind | |
| · apply monotone_const | |
| · refine monotone_of_monotone_apply _ fun ref => ?_ | |
| apply monotone_bind | |
| · exact monotone_apply _ _ hmono | |
| · apply monotone_const | |
| instance [inst : ∀ α, PartialOrder (m α)] : PartialOrder (StateT σ m α) := instOrderPi | |
| instance [inst : ∀ α, CCPO (m α)] : CCPO (StateT σ m α) := instCCPOPi | |
| instance [Monad m] [∀ α, PartialOrder (m α)] [MonoBind m] : MonoBind (StateT ρ m) where | |
| bind_mono_left h₁₂ := by | |
| intro x | |
| apply MonoBind.bind_mono_left (m := m) | |
| exact h₁₂ x | |
| bind_mono_right h₁₂ := by | |
| intro x | |
| apply MonoBind.bind_mono_right (m := m) | |
| intro y | |
| apply h₁₂ | |
| @[partial_fixpoint_monotone] | |
| theorem monotone_stateTRun [PartialOrder γ] | |
| [Monad m] [∀ α, PartialOrder (m α)] | |
| (f : γ → StateT σ m α) (hmono : monotone f) (s : σ) : | |
| monotone (fun (x : γ) => StateT.run (f x) s) := | |
| monotone_apply s _ hmono | |
| noncomputable def EST.bot [Nonempty ε] : EST ε σ α := | |
| fun s => .error Classical.ofNonempty (Classical.choice ⟨s⟩) | |
| -- Essentially | |
| -- instance [Nonempty ε] : CCPO (EST ε σ α) := | |
| -- inferInstanceAs (CCPO ((s : _) → FlatOrder (EST.bot s))) | |
| -- but hat would incur a noncomputable on the instance | |
| instance [Nonempty ε] : CCPO (EST ε σ α) where | |
| rel := PartialOrder.rel (α := ∀ s, FlatOrder (EST.bot s)) | |
| rel_refl := PartialOrder.rel_refl | |
| rel_antisymm := PartialOrder.rel_antisymm | |
| rel_trans := PartialOrder.rel_trans | |
| has_csup hchain := CCPO.has_csup (α := ∀ s, FlatOrder (EST.bot s)) hchain | |
| instance [Nonempty ε] : MonoBind (EST ε σ) where | |
| bind_mono_left {_ _ a₁ a₂ f} h₁₂ := by | |
| intro s | |
| specialize h₁₂ s | |
| change FlatOrder.rel (a₁.bind f s) (a₂.bind f s) | |
| simp only [EST.bind] | |
| generalize a₁ s = a₁ at h₁₂; generalize a₂ s = a₂ at h₁₂ | |
| cases h₁₂ | |
| · exact .bot | |
| · exact .refl | |
| bind_mono_right {_ _ a f₁ f₂} h₁₂ := by | |
| intro w | |
| change FlatOrder.rel (a.bind f₁ w) (a.bind f₂ w) | |
| simp only [EST.bind] | |
| split | |
| · apply h₁₂ | |
| · exact .refl | |
| instance [Nonempty ε] : CCPO (EIO ε α) := | |
| inferInstanceAs (CCPO (EST ε IO.RealWorld α)) | |
| instance [Nonempty ε] : MonoBind (EIO ε) := | |
| inferInstanceAs (MonoBind (EST ε IO.RealWorld)) | |
| instance : CCPO (IO α) := | |
| inferInstanceAs (CCPO (EIO IO.Error α)) | |
| instance : MonoBind IO := | |
| inferInstanceAs (MonoBind (EIO IO.Error)) | |
| end mono_bind | |
| section implication_order | |
| -- Partial order on `Prop` given by implication | |
| @[expose] def ImplicationOrder := Prop | |
| instance ImplicationOrder.instOrder : PartialOrder ImplicationOrder where | |
| rel x y := x → y | |
| rel_refl := fun x => x | |
| rel_trans h₁ h₂ := fun x => h₂ (h₁ x) | |
| rel_antisymm h₁ h₂ := propext ⟨h₁, h₂⟩ | |
| -- This defines a complete lattice on `Prop`, used to define inductive predicates | |
| instance ImplicationOrder.instCompleteLattice : CompleteLattice ImplicationOrder where | |
| has_sup c := by | |
| exists ∃ p, c p ∧ p | |
| intro x | |
| constructor | |
| case mp => | |
| intro h y cy hy | |
| apply h | |
| apply Exists.intro y | |
| exact ⟨cy, hy⟩ | |
| case mpr => | |
| intro h | |
| intro e | |
| apply Exists.elim e | |
| intro a | |
| intro caa | |
| exact h a caa.1 caa.2 | |
| -- Monotonicity lemmas for inductive predicates | |
| @[partial_fixpoint_monotone] theorem implication_order_monotone_exists | |
| {α} [PartialOrder α] {β} (f : α → β → ImplicationOrder) | |
| (h : monotone f) : | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => (Exists (f x))) := | |
| fun x y hxy ⟨w, hw⟩ => ⟨w, monotone_apply w f h x y hxy hw⟩ | |
| @[partial_fixpoint_monotone] theorem implication_order_monotone_forall | |
| {α} [PartialOrder α] {β} (f : α → β → ImplicationOrder) | |
| (h : monotone f) : | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => ∀ y, f x y) := | |
| fun x y hxy h₂ y₁ => monotone_apply y₁ f h x y hxy (h₂ y₁) | |
| @[partial_fixpoint_monotone] theorem implication_order_monotone_and | |
| {α} [PartialOrder α] (f₁ : α → ImplicationOrder) (f₂ : α → ImplicationOrder) | |
| (h₁ : @monotone _ _ _ ImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ImplicationOrder.instOrder f₂) : | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => f₁ x ∧ f₂ x) := | |
| fun x y hxy ⟨hfx₁, hfx₂⟩ => ⟨h₁ x y hxy hfx₁, h₂ x y hxy hfx₂⟩ | |
| @[partial_fixpoint_monotone] theorem implication_order_monotone_or | |
| {α} [PartialOrder α] (f₁ : α → ImplicationOrder) (f₂ : α → ImplicationOrder) | |
| (h₁ : @monotone _ _ _ ImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ImplicationOrder.instOrder f₂) : | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => f₁ x ∨ f₂ x) := | |
| fun x y hxy h => | |
| match h with | |
| | Or.inl hfx₁ => Or.inl (h₁ x y hxy hfx₁) | |
| | Or.inr hfx₂ => Or.inr (h₂ x y hxy hfx₂) | |
| end implication_order | |
| section reverse_implication_order | |
| @[expose] def ReverseImplicationOrder := Prop | |
| -- Partial order on `Prop` given by reverse implication | |
| instance ReverseImplicationOrder.instOrder : PartialOrder ReverseImplicationOrder where | |
| rel x y := y → x | |
| rel_refl := fun x => x | |
| rel_trans := fun h₁ h₂ => fun x => h₁ (h₂ x) | |
| rel_antisymm h₁ h₂ := propext ⟨h₂, h₁⟩ | |
| -- This defines a complete lattice on `Prop`, used to define coinductive predicates | |
| instance ReverseImplicationOrder.instCompleteLattice : CompleteLattice ReverseImplicationOrder where | |
| has_sup c := by | |
| exists ∀ p, c p → p | |
| intro x | |
| constructor | |
| case mp => | |
| intro h y cy l | |
| apply h | |
| exact l | |
| exact cy | |
| case mpr => | |
| intro h y cy ccy | |
| apply h | |
| exact ccy | |
| exact y | |
| -- Monotonicity lemmas for coinductive predicates | |
| @[partial_fixpoint_monotone] theorem coind_monotone_exists | |
| {α} [PartialOrder α] {β} (f : α → β → ReverseImplicationOrder) | |
| (h : monotone f) : | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => Exists (f x)) := | |
| fun x y hxy ⟨w, hw⟩ => ⟨w, monotone_apply w f h x y hxy hw⟩ | |
| @[partial_fixpoint_monotone] theorem coind_monotone_forall | |
| {α} [PartialOrder α] {β} (f : α → β → ReverseImplicationOrder) | |
| (h : monotone f) : | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => ∀ y, f x y) := | |
| fun x y hxy h₂ y₁ => monotone_apply y₁ f h x y hxy (h₂ y₁) | |
| @[partial_fixpoint_monotone] theorem coind_monotone_and | |
| {α} [PartialOrder α] (f₁ : α → Prop) (f₂ : α → Prop) | |
| (h₁ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₂) : | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => f₁ x ∧ f₂ x) := | |
| fun x y hxy ⟨hfx₁, hfx₂⟩ => ⟨h₁ x y hxy hfx₁, h₂ x y hxy hfx₂⟩ | |
| @[partial_fixpoint_monotone] theorem coind_monotone_or | |
| {α} [PartialOrder α] (f₁ : α → Prop) (f₂ : α → Prop) | |
| (h₁ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₂) : | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => f₁ x ∨ f₂ x) := | |
| fun x y hxy h => | |
| match h with | |
| | Or.inl hfx₁ => Or.inl (h₁ x y hxy hfx₁) | |
| | Or.inr hfx₂ => Or.inr (h₂ x y hxy hfx₂) | |
| end reverse_implication_order | |
| section antitone | |
| @[partial_fixpoint_monotone] theorem coind_not | |
| {α} [PartialOrder α] (f₁ : α → Prop) | |
| (h₁ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₁) : | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => ¬f₁ x) := by | |
| intro x y hxy hfx h | |
| exact hfx (h₁ x y hxy h) | |
| @[partial_fixpoint_monotone] theorem ind_not | |
| {α} [PartialOrder α] (f₁ : α → Prop) | |
| (h₁ : @monotone _ _ _ ImplicationOrder.instOrder f₁) : | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => ¬f₁ x) := by | |
| intro x y hxy hfx h | |
| exact hfx (h₁ x y hxy h) | |
| @[partial_fixpoint_monotone] theorem ind_impl | |
| {α} [PartialOrder α] (f₁ : α → Prop) (f₂ : α → Prop) | |
| (h₁ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ImplicationOrder.instOrder f₂): | |
| @monotone _ _ _ ImplicationOrder.instOrder (fun x => f₁ x → f₂ x) := by | |
| intro x y hxy himp hf1 | |
| specialize h₁ x y hxy hf1 | |
| specialize h₂ x y hxy | |
| apply h₂ | |
| apply himp | |
| exact h₁ | |
| @[partial_fixpoint_monotone] theorem coind_impl | |
| {α} [PartialOrder α] (f₁ : α → Prop) (f₂ : α → Prop) | |
| (h₁ : @monotone _ _ _ ImplicationOrder.instOrder f₁) | |
| (h₂ : @monotone _ _ _ ReverseImplicationOrder.instOrder f₂): | |
| @monotone _ _ _ ReverseImplicationOrder.instOrder (fun x => f₁ x → f₂ x) := by | |
| intro x y hxy himp hf1 | |
| specialize h₁ x y hxy hf1 | |
| specialize h₂ x y hxy | |
| apply h₂ | |
| apply himp | |
| exact h₁ | |
| end antitone | |
| namespace Example | |
| def findF (P : Nat → Bool) (rec : Nat → Option Nat) (x : Nat) : Option Nat := | |
| if P x then | |
| some x | |
| else | |
| rec (x + 1) | |
| noncomputable def find (P : Nat → Bool) : Nat → Option Nat := fix (findF P) <| by | |
| unfold findF | |
| apply monotone_of_monotone_apply | |
| intro n | |
| split | |
| · apply monotone_const | |
| · apply monotone_apply | |
| apply monotone_id | |
| theorem find_eq : find P = findF P (find P) := fix_eq .. | |
| theorem find_spec : ∀ n m, find P n = some m → n ≤ m ∧ P m := by | |
| unfold find | |
| refine fix_induct (motive := fun (f : Nat → Option Nat) => ∀ n m, f n = some m → n ≤ m ∧ P m) _ ?hadm ?hstep | |
| case hadm => | |
| -- apply admissible_pi_apply does not work well, hard to infer everything | |
| exact admissible_pi_apply _ (fun n => admissible_pi _ (fun m => Option.admissible_eq_some _ m)) | |
| case hstep => | |
| intro f ih n m heq | |
| simp only [findF] at heq | |
| split at heq | |
| · simp_all | |
| · obtain ⟨ih1, ih2⟩ := ih _ _ heq | |
| constructor | |
| · exact Nat.le_trans (Nat.le_add_right _ _ ) ih1 | |
| · exact ih2 | |
| end Example | |
| end Lean.Order |