diff options
Diffstat (limited to 'theories/Arith')
| -rw-r--r-- | theories/Arith/Wf_nat.v | 17 |
1 files changed, 14 insertions, 3 deletions
diff --git a/theories/Arith/Wf_nat.v b/theories/Arith/Wf_nat.v index c16a13dfb..d3d7b5835 100644 --- a/theories/Arith/Wf_nat.v +++ b/theories/Arith/Wf_nat.v @@ -270,7 +270,18 @@ Theorem iter_nat_plus : forall (n m:nat) (A:Type) (f:A -> A) (x:A), iter_nat (n + m) A f x = iter_nat n A f (iter_nat m A f x). Proof. - simple induction n; - [ simpl in |- *; auto with arith - | intros; simpl in |- *; apply f_equal with (f := f); apply H ]. + induction n; simpl; trivial. + intros. now f_equal. +Qed. + +(** 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. + induction n; simpl; trivial. + intros A f Inv Hf x Hx. apply Hf, IHn; trivial. Qed. |