1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "ground/notation/functions/exp_3.ma".
16 include "ground/lib/exteq.ma".
17 include "ground/arith/pnat.ma".
19 (* ITERATED FUNCTION FOR POSITIVE INTEGERS **********************************)
21 (* Note: see also: lib/arithemetics/bigops.ma *)
22 rec definition piter (p:pnat) (A:Type[0]) (f:A→A) (a:A) ≝
25 | psucc q ⇒ f (piter q A f a)
29 "iterated function (positive integers)"
30 'Exp A f p = (piter p A f).
32 (* Basic constructions ******************************************************)
34 lemma piter_unit (A) (f): f ⊜ f^{A}𝟏.
37 lemma piter_succ (A) (f) (p): f ∘ f^p ⊜ f^{A}(↑p).
40 (* Advanced constructions ***************************************************)
42 lemma piter_appl (A) (f) (p): f ∘ f^p ⊜ f^{A}p ∘ f.
45 /3 width=5 by compose_repl_fwd_dx, compose_repl_fwd_sn, exteq_canc_dx/
48 lemma piter_compose (A) (B) (f) (g) (h) (p):
49 h ∘ f ⊜ g ∘ h → h ∘ (f^{A}p) ⊜ (g^{B}p) ∘ h.
50 #A #B #f #g #h #p elim p -p
52 /2 width=5 by compose_repl_fwd_sn, compose_repl_fwd_dx/
53 | #p #IH #H @exteq_repl
54 [4: @compose_repl_fwd_dx [| @piter_succ ]
55 |5: @compose_repl_fwd_sn [| @piter_succ ]
58 @exteq_trans [2: @compose_assoc |1: skip ]
59 @exteq_trans [2: @(compose_repl_fwd_sn … H) | 1:skip ]
60 @exteq_canc_sn [2: @compose_assoc |1: skip ]
61 /3 width=1 by compose_repl_fwd_dx/