diff options
Diffstat (limited to 'theories/Init/Wf.v')
| -rw-r--r-- | theories/Init/Wf.v | 17 |
1 files changed, 8 insertions, 9 deletions
diff --git a/theories/Init/Wf.v b/theories/Init/Wf.v index d3f8f1ab..3209860f 100644 --- a/theories/Init/Wf.v +++ b/theories/Init/Wf.v @@ -6,7 +6,7 @@ (* * GNU Lesser General Public License Version 2.1 *) (************************************************************************) -(*i $Id: Wf.v 11251 2008-07-24 08:28:40Z herbelin $ i*) +(*i $Id$ i*) (** * This module proves the validity of - well-founded recursion (also known as course of values) @@ -65,14 +65,14 @@ Section Well_founded. exact (fun P:A -> Prop => well_founded_induction_type P). Defined. -(** Well-founded fixpoints *) +(** Well-founded fixpoints *) Section FixPoint. Variable P : A -> Type. Variable F : forall x:A, (forall y:A, R y x -> P y) -> P x. - Fixpoint Fix_F (x:A) (a:Acc x) {struct a} : P x := + Fixpoint Fix_F (x:A) (a:Acc x) : P x := F (fun (y:A) (h:R y x) => Fix_F (Acc_inv a h)). Scheme Acc_inv_dep := Induction for Acc Sort Prop. @@ -80,13 +80,13 @@ Section Well_founded. Lemma Fix_F_eq : forall (x:A) (r:Acc x), F (fun (y:A) (p:R y x) => Fix_F (x:=y) (Acc_inv r p)) = Fix_F (x:=x) r. - Proof. + Proof. destruct r using Acc_inv_dep; auto. Qed. Definition Fix (x:A) := Fix_F (Rwf x). - (** Proof that [well_founded_induction] satisfies the fixpoint equation. + (** Proof that [well_founded_induction] satisfies the fixpoint equation. It requires an extra property of the functional *) Hypothesis @@ -111,7 +111,7 @@ Section Well_founded. End FixPoint. -End Well_founded. +End Well_founded. (** Well-founded fixpoints over pairs *) @@ -120,7 +120,7 @@ Section Well_founded_2. Variables A B : Type. Variable R : A * B -> A * B -> Prop. - Variable P : A -> B -> Type. + Variable P : A -> B -> Type. Section FixPoint_2. @@ -129,8 +129,7 @@ Section Well_founded_2. forall (x:A) (x':B), (forall (y:A) (y':B), R (y, y') (x, x') -> P y y') -> P x x'. - Fixpoint Fix_F_2 (x:A) (x':B) (a:Acc R (x, x')) {struct a} : - P x x' := + Fixpoint Fix_F_2 (x:A) (x':B) (a:Acc R (x, x')) : P x x' := F (fun (y:A) (y':B) (h:R (y, y') (x, x')) => Fix_F_2 (x:=y) (x':=y') (Acc_inv a (y,y') h)). |