fixpoint.v 2.85 KB
 Ralf Jung committed Aug 22, 2017 1 2 3 4 5 ``````From iris.base_logic Require Import base_logic. From iris.proofmode Require Import tactics. Set Default Proof Using "Type*". Import uPred. `````` Ralf Jung committed Aug 23, 2017 6 7 ``````(** Least and greatest fixpoint of a monotone function, defined entirely inside the logic. *) `````` Robbert Krebbers committed Sep 19, 2017 8 9 10 ``````Class BIMonoPred {M A} (F : (A → uPred M) → (A → uPred M)) := bi_mono_pred Φ Ψ : ((□ ∀ x, Φ x -∗ Ψ x) → ∀ x, F Φ x -∗ F Ψ x)%I. Arguments bi_mono_pred {_ _ _ _} _ _. `````` Ralf Jung committed Aug 22, 2017 11 `````` `````` Robbert Krebbers committed Aug 28, 2017 12 13 14 ``````Definition uPred_least_fixpoint {M A} (F : (A → uPred M) → (A → uPred M)) (x : A) : uPred M := (∀ Φ, □ (∀ x, F Φ x → Φ x) → Φ x)%I. `````` Ralf Jung committed Aug 23, 2017 15 `````` `````` Robbert Krebbers committed Aug 28, 2017 16 17 18 ``````Definition uPred_greatest_fixpoint {M A} (F : (A → uPred M) → (A → uPred M)) (x : A) : uPred M := (∃ Φ, □ (∀ x, Φ x → F Φ x) ∧ Φ x)%I. `````` Ralf Jung committed Aug 22, 2017 19 `````` `````` Ralf Jung committed Aug 23, 2017 20 ``````Section least. `````` Robbert Krebbers committed Sep 19, 2017 21 `````` Context {M A} (F : (A → uPred M) → (A → uPred M)) `{!BIMonoPred F}. `````` Ralf Jung committed Aug 23, 2017 22 `````` `````` Robbert Krebbers committed Aug 28, 2017 23 `````` Lemma least_fixpoint_unfold_2 x : F (uPred_least_fixpoint F) x ⊢ uPred_least_fixpoint F x. `````` Ralf Jung committed Aug 23, 2017 24 `````` Proof. `````` Robbert Krebbers committed Aug 28, 2017 25 `````` iIntros "HF" (Φ) "#Hincl". `````` Robbert Krebbers committed Sep 19, 2017 26 `````` iApply "Hincl". iApply (bi_mono_pred _ Φ); last done. `````` Ralf Jung committed Aug 23, 2017 27 28 29 `````` iIntros "!#" (y) "Hy". iApply "Hy". done. Qed. `````` Robbert Krebbers committed Aug 28, 2017 30 `````` Lemma least_fixpoint_unfold_1 x : `````` Ralf Jung committed Aug 23, 2017 31 32 33 `````` uPred_least_fixpoint F x ⊢ F (uPred_least_fixpoint F) x. Proof. iIntros "HF". iApply "HF". iIntros "!#" (y) "Hy". `````` Robbert Krebbers committed Sep 19, 2017 34 `````` iApply bi_mono_pred; last done. iIntros "!#" (z) "?". `````` Robbert Krebbers committed Aug 28, 2017 35 `````` by iApply least_fixpoint_unfold_2. `````` Ralf Jung committed Aug 23, 2017 36 37 `````` Qed. `````` Robbert Krebbers committed Aug 28, 2017 38 `````` Corollary least_fixpoint_unfold x : `````` Ralf Jung committed Aug 23, 2017 39 40 `````` uPred_least_fixpoint F x ≡ F (uPred_least_fixpoint F) x. Proof. `````` Robbert Krebbers committed Aug 28, 2017 41 `````` apply (anti_symm _); auto using least_fixpoint_unfold_1, least_fixpoint_unfold_2. `````` Ralf Jung committed Aug 23, 2017 42 43 `````` Qed. `````` Robbert Krebbers committed Aug 28, 2017 44 45 46 `````` Lemma least_fixpoint_ind (Φ : A → uPred M) : □ (∀ y, F Φ y → Φ y) ⊢ ∀ x, uPred_least_fixpoint F x → Φ x. Proof. iIntros "#HΦ" (x) "HF". iApply "HF". done. Qed. `````` Ralf Jung committed Aug 23, 2017 47 48 49 ``````End least. Section greatest. `````` Robbert Krebbers committed Sep 19, 2017 50 `````` Context {M A} (F : (A → uPred M) → (A → uPred M)) `{!BIMonoPred F}. `````` Ralf Jung committed Aug 22, 2017 51 `````` `````` Robbert Krebbers committed Aug 28, 2017 52 `````` Lemma greatest_fixpoint_unfold_1 x : `````` Ralf Jung committed Aug 23, 2017 53 `````` uPred_greatest_fixpoint F x ⊢ F (uPred_greatest_fixpoint F) x. `````` Ralf Jung committed Aug 22, 2017 54 `````` Proof. `````` Robbert Krebbers committed Aug 28, 2017 55 `````` iDestruct 1 as (Φ) "[#Hincl HΦ]". `````` Robbert Krebbers committed Sep 19, 2017 56 `````` iApply (bi_mono_pred Φ (uPred_greatest_fixpoint F)). `````` Robbert Krebbers committed Aug 28, 2017 57 `````` - iIntros "!#" (y) "Hy". iExists Φ. auto. `````` Ralf Jung committed Aug 22, 2017 58 59 60 `````` - by iApply "Hincl". Qed. `````` Robbert Krebbers committed Aug 28, 2017 61 `````` Lemma greatest_fixpoint_unfold_2 x : `````` Ralf Jung committed Aug 23, 2017 62 `````` F (uPred_greatest_fixpoint F) x ⊢ uPred_greatest_fixpoint F x. `````` Ralf Jung committed Aug 22, 2017 63 `````` Proof. `````` Ralf Jung committed Aug 23, 2017 64 `````` iIntros "HF". iExists (F (uPred_greatest_fixpoint F)). `````` Robbert Krebbers committed Sep 19, 2017 65 `````` iIntros "{\$HF} !#" (y) "Hy". iApply (bi_mono_pred with "[] Hy"). `````` Robbert Krebbers committed Aug 28, 2017 66 `````` iIntros "!#" (z) "?". by iApply greatest_fixpoint_unfold_1. `````` Ralf Jung committed Aug 22, 2017 67 68 `````` Qed. `````` Robbert Krebbers committed Aug 28, 2017 69 `````` Corollary greatest_fixpoint_unfold x : `````` Ralf Jung committed Aug 23, 2017 70 `````` uPred_greatest_fixpoint F x ≡ F (uPred_greatest_fixpoint F) x. `````` Ralf Jung committed Aug 22, 2017 71 `````` Proof. `````` Robbert Krebbers committed Aug 28, 2017 72 `````` apply (anti_symm _); auto using greatest_fixpoint_unfold_1, greatest_fixpoint_unfold_2. `````` Ralf Jung committed Aug 22, 2017 73 74 `````` Qed. `````` Robbert Krebbers committed Aug 28, 2017 75 76 77 `````` Lemma greatest_fixpoint_coind (Φ : A → uPred M) : □ (∀ y, Φ y → F Φ y) ⊢ ∀ x, Φ x → uPred_greatest_fixpoint F x. Proof. iIntros "#HΦ" (x) "Hx". iExists Φ. by iIntros "{\$Hx} !#". Qed. `````` Ralf Jung committed Aug 23, 2017 78 ``End greatest.``