diff options
Diffstat (limited to 'theories/ZArith/Zmisc.v')
| -rw-r--r-- | theories/ZArith/Zmisc.v | 25 |
1 files changed, 16 insertions, 9 deletions
diff --git a/theories/ZArith/Zmisc.v b/theories/ZArith/Zmisc.v index 0634096e..178ae5f1 100644 --- a/theories/ZArith/Zmisc.v +++ b/theories/ZArith/Zmisc.v @@ -6,7 +6,7 @@ (* * GNU Lesser General Public License Version 2.1 *) (************************************************************************) -(*i $Id: Zmisc.v 11072 2008-06-08 16:13:37Z herbelin $ i*) +(*i $Id$ i*) Require Import Wf_nat. Require Import BinInt. @@ -20,7 +20,7 @@ Open Local Scope Z_scope. (** [n]th iteration of the function [f] *) -Fixpoint iter_pos (n:positive) (A:Type) (f:A -> A) (x:A) {struct n} : A := +Fixpoint iter_pos (n:positive) (A:Type) (f:A -> A) (x:A) : A := match n with | xH => f x | xO n' => iter_pos n' A f (iter_pos n' A f x) @@ -37,22 +37,29 @@ Definition iter (n:Z) (A:Type) (f:A -> A) (x:A) := Theorem iter_nat_of_P : forall (p:positive) (A:Type) (f:A -> A) (x:A), iter_pos p A f x = iter_nat (nat_of_P p) A f x. -Proof. +Proof. intro n; induction n as [p H| p H| ]; [ intros; simpl in |- *; rewrite (H A f x); - rewrite (H A f (iter_nat (nat_of_P p) A f x)); + rewrite (H A f (iter_nat (nat_of_P p) A f x)); rewrite (ZL6 p); symmetry in |- *; apply f_equal with (f := f); apply iter_nat_plus | intros; unfold nat_of_P in |- *; simpl in |- *; rewrite (H A f x); - rewrite (H A f (iter_nat (nat_of_P p) A f x)); + rewrite (H A f (iter_nat (nat_of_P p) A f x)); rewrite (ZL6 p); symmetry in |- *; apply iter_nat_plus | simpl in |- *; auto with arith ]. Qed. +Lemma iter_nat_of_Z : forall n A f x, 0 <= n -> + iter n A f x = iter_nat (Zabs_nat n) A f x. +intros n A f x; case n; auto. +intros p _; unfold iter, Zabs_nat; apply iter_nat_of_P. +intros p abs; case abs; trivial. +Qed. + Theorem iter_pos_plus : forall (p q:positive) (A:Type) (f:A -> A) (x:A), iter_pos (p + q) A f x = iter_pos p A f (iter_pos q A f x). -Proof. +Proof. intros n m; intros. rewrite (iter_nat_of_P m A f x). rewrite (iter_nat_of_P n A f (iter_nat (nat_of_P m) A f x)). @@ -61,14 +68,14 @@ Proof. apply iter_nat_plus. Qed. -(** Preservation of invariants : if [f : A->A] preserves the invariant [Inv], +(** Preservation of invariants : if [f : A->A] preserves the invariant [Inv], then the iterates of [f] also preserve it. *) Theorem iter_nat_invariant : forall (n:nat) (A:Type) (f:A -> A) (Inv:A -> Prop), (forall x:A, Inv x -> Inv (f x)) -> forall x:A, Inv x -> Inv (iter_nat n A f x). -Proof. +Proof. simple induction n; intros; [ trivial with arith | simpl in |- *; apply H0 with (x := iter_nat n0 A f x); apply H; @@ -79,6 +86,6 @@ Theorem iter_pos_invariant : forall (p:positive) (A:Type) (f:A -> A) (Inv:A -> Prop), (forall x:A, Inv x -> Inv (f x)) -> forall x:A, Inv x -> Inv (iter_pos p A f x). -Proof. +Proof. intros; rewrite iter_nat_of_P; apply iter_nat_invariant; trivial with arith. Qed. |