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 "lambda/ext.ma".
16 include "lambda/subst.ma".
18 (* MATTER CONCERNING STRONG NORMALIZATION TO BE PUT ELSEWHERE *****************)
20 (* terms **********************************************************************)
22 (* FG: not needed for now
24 inductive neutral: T → Prop ≝
25 | neutral_sort: ∀n.neutral (Sort n)
26 | neutral_rel: ∀i.neutral (Rel i)
27 | neutral_app: ∀M,N.neutral (App M N)
31 (* substitution ***************************************************************)
33 (* FG: do we need this?
34 definition lift0 ≝ λp,k,M . lift M p k. (**) (* remove definition *)
36 lemma lift_appl: ∀p,k,l,F. lift (Appl F l) p k =
37 Appl (lift F p k) (map … (lift0 p k) l).
38 #p #k #l (elim l) -l /2/ #A #D #IHl #F >IHl //
42 lemma lift_rel_lt: ∀i,p,k. (S i) ≤ k → lift (Rel i) k p = Rel i.
43 #i #p #k #Hik normalize >(le_to_leb_true … Hik) //
46 lemma lift_rel_ge: ∀i,p,k. (S i) ≰ k → lift (Rel i) k p = Rel (i+p).
47 #i #p #k #Hik normalize >(lt_to_leb_false (S i) k) /2/
50 lemma lift_app: ∀M,N,k,p.
51 lift (App M N) k p = App (lift M k p) (lift N k p).
54 lemma lift_lambda: ∀N,M,k,p. lift (Lambda N M) k p =
55 Lambda (lift N k p) (lift M (k + 1) p).
58 lemma lift_prod: ∀N,M,k,p.
59 lift (Prod N M) k p = Prod (lift N k p) (lift M (k + 1) p).
62 lemma subst_app: ∀M,N,k,L. (App M N)[k≝L] = App M[k≝L] N[k≝L].
65 lemma subst_lambda: ∀N,M,k,L. (Lambda N M)[k≝L] = Lambda N[k≝L] M[k+1≝L].
68 lemma subst_prod: ∀N,M,k,L. (Prod N M)[k≝L] = Prod N[k≝L] M[k+1≝L].
72 axiom lift_subst_lt: ∀A,B,i,j,k. lift (B[j≝A]) (j+k) i =
73 (lift B (j+k+1) i)[j≝lift A k i].
75 (* telescopic delifting substitution of l in M.
76 * Rel 0 is replaced with the head of l
78 let rec tsubst M l on l ≝ match l with
80 | cons A D ⇒ (tsubst M[0≝A] D)
83 interpretation "telescopic substitution" 'Subst M l = (tsubst M l).
85 lemma tsubst_refl: ∀l,t. (lift t 0 (|l|))[/l] = t.
86 #l elim l -l; normalize // #hd #tl #IHl #t cut (S (|tl|) = |tl| + 1) // (**) (* eliminate cut *)
89 lemma tsubst_sort: ∀n,l. (Sort n)[/l] = Sort n.