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 (* This file was automatically generated: do not edit *********************)
19 include "subst1/fwd.ma".
21 include "subst0/subst0.ma".
23 theorem subst1_subst1:
24 \forall (t1: T).(\forall (t2: T).(\forall (u2: T).(\forall (j: nat).((subst1
25 j u2 t1 t2) \to (\forall (u1: T).(\forall (u: T).(\forall (i: nat).((subst1 i
26 u u1 u2) \to (ex2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t:
27 T).(subst1 (S (plus i j)) u t t2)))))))))))
29 \lambda (t1: T).(\lambda (t2: T).(\lambda (u2: T).(\lambda (j: nat).(\lambda
30 (H: (subst1 j u2 t1 t2)).(subst1_ind j u2 t1 (\lambda (t: T).(\forall (u1:
31 T).(\forall (u: T).(\forall (i: nat).((subst1 i u u1 u2) \to (ex2 T (\lambda
32 (t0: T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t0
33 t)))))))) (\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (_:
34 (subst1 i u u1 u2)).(ex_intro2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda
35 (t: T).(subst1 (S (plus i j)) u t t1)) t1 (subst1_refl j u1 t1) (subst1_refl
36 (S (plus i j)) u t1)))))) (\lambda (t3: T).(\lambda (H0: (subst0 j u2 t1
37 t3)).(\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (H1: (subst1
38 i u u1 u2)).(insert_eq T u2 (\lambda (t: T).(subst1 i u u1 t)) (ex2 T
39 (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u
40 t t3))) (\lambda (y: T).(\lambda (H2: (subst1 i u u1 y)).(subst1_ind i u u1
41 (\lambda (t: T).((eq T t u2) \to (ex2 T (\lambda (t0: T).(subst1 j u1 t1 t0))
42 (\lambda (t0: T).(subst1 (S (plus i j)) u t0 t3))))) (\lambda (H3: (eq T u1
43 u2)).(eq_ind_r T u2 (\lambda (t: T).(ex2 T (\lambda (t0: T).(subst1 j t t1
44 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t0 t3)))) (ex_intro2 T
45 (\lambda (t: T).(subst1 j u2 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u
46 t t3)) t3 (subst1_single j u2 t1 t3 H0) (subst1_refl (S (plus i j)) u t3)) u1
47 H3)) (\lambda (t0: T).(\lambda (H3: (subst0 i u u1 t0)).(\lambda (H4: (eq T
48 t0 u2)).(let H5 \def (eq_ind T t0 (\lambda (t: T).(subst0 i u u1 t)) H3 u2
49 H4) in (ex2_ind T (\lambda (t: T).(subst0 j u1 t1 t)) (\lambda (t: T).(subst0
50 (S (plus i j)) u t t3)) (ex2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda
51 (t: T).(subst1 (S (plus i j)) u t t3))) (\lambda (x: T).(\lambda (H6: (subst0
52 j u1 t1 x)).(\lambda (H7: (subst0 (S (plus i j)) u x t3)).(ex_intro2 T
53 (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u
54 t t3)) x (subst1_single j u1 t1 x H6) (subst1_single (S (plus i j)) u x t3
55 H7))))) (subst0_subst0 t1 t3 u2 j H0 u1 u i H5)))))) y H2))) H1))))))) t2
58 theorem subst1_subst1_back:
59 \forall (t1: T).(\forall (t2: T).(\forall (u2: T).(\forall (j: nat).((subst1
60 j u2 t1 t2) \to (\forall (u1: T).(\forall (u: T).(\forall (i: nat).((subst1 i
61 u u2 u1) \to (ex2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t:
62 T).(subst1 (S (plus i j)) u t2 t)))))))))))
64 \lambda (t1: T).(\lambda (t2: T).(\lambda (u2: T).(\lambda (j: nat).(\lambda
65 (H: (subst1 j u2 t1 t2)).(subst1_ind j u2 t1 (\lambda (t: T).(\forall (u1:
66 T).(\forall (u: T).(\forall (i: nat).((subst1 i u u2 u1) \to (ex2 T (\lambda
67 (t0: T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t
68 t0)))))))) (\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (_:
69 (subst1 i u u2 u1)).(ex_intro2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda
70 (t: T).(subst1 (S (plus i j)) u t1 t)) t1 (subst1_refl j u1 t1) (subst1_refl
71 (S (plus i j)) u t1)))))) (\lambda (t3: T).(\lambda (H0: (subst0 j u2 t1
72 t3)).(\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (H1: (subst1
73 i u u2 u1)).(subst1_ind i u u2 (\lambda (t: T).(ex2 T (\lambda (t0:
74 T).(subst1 j t t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t3 t0))))
75 (ex_intro2 T (\lambda (t: T).(subst1 j u2 t1 t)) (\lambda (t: T).(subst1 (S
76 (plus i j)) u t3 t)) t3 (subst1_single j u2 t1 t3 H0) (subst1_refl (S (plus i
77 j)) u t3)) (\lambda (t0: T).(\lambda (H2: (subst0 i u u2 t0)).(ex2_ind T
78 (\lambda (t: T).(subst0 j t0 t1 t)) (\lambda (t: T).(subst0 (S (plus i j)) u
79 t3 t)) (ex2 T (\lambda (t: T).(subst1 j t0 t1 t)) (\lambda (t: T).(subst1 (S
80 (plus i j)) u t3 t))) (\lambda (x: T).(\lambda (H3: (subst0 j t0 t1
81 x)).(\lambda (H4: (subst0 (S (plus i j)) u t3 x)).(ex_intro2 T (\lambda (t:
82 T).(subst1 j t0 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u t3 t)) x
83 (subst1_single j t0 t1 x H3) (subst1_single (S (plus i j)) u t3 x H4)))))
84 (subst0_subst0_back t1 t3 u2 j H0 t0 u i H2)))) u1 H1))))))) t2 H))))).
87 \forall (t2: T).(\forall (t1: T).(\forall (v: T).(\forall (i: nat).((subst1
88 i v t1 t2) \to (\forall (t3: T).((subst1 i v t2 t3) \to (subst1 i v t1
91 \lambda (t2: T).(\lambda (t1: T).(\lambda (v: T).(\lambda (i: nat).(\lambda
92 (H: (subst1 i v t1 t2)).(subst1_ind i v t1 (\lambda (t: T).(\forall (t3:
93 T).((subst1 i v t t3) \to (subst1 i v t1 t3)))) (\lambda (t3: T).(\lambda
94 (H0: (subst1 i v t1 t3)).H0)) (\lambda (t3: T).(\lambda (H0: (subst0 i v t1
95 t3)).(\lambda (t4: T).(\lambda (H1: (subst1 i v t3 t4)).(subst1_ind i v t3
96 (\lambda (t: T).(subst1 i v t1 t)) (subst1_single i v t1 t3 H0) (\lambda (t0:
97 T).(\lambda (H2: (subst0 i v t3 t0)).(subst1_single i v t1 t0 (subst0_trans
98 t3 t1 v i H0 t0 H2)))) t4 H1))))) t2 H))))).
100 theorem subst1_confluence_neq:
101 \forall (t0: T).(\forall (t1: T).(\forall (u1: T).(\forall (i1:
102 nat).((subst1 i1 u1 t0 t1) \to (\forall (t2: T).(\forall (u2: T).(\forall
103 (i2: nat).((subst1 i2 u2 t0 t2) \to ((not (eq nat i1 i2)) \to (ex2 T (\lambda
104 (t: T).(subst1 i2 u2 t1 t)) (\lambda (t: T).(subst1 i1 u1 t2 t))))))))))))
106 \lambda (t0: T).(\lambda (t1: T).(\lambda (u1: T).(\lambda (i1:
107 nat).(\lambda (H: (subst1 i1 u1 t0 t1)).(subst1_ind i1 u1 t0 (\lambda (t:
108 T).(\forall (t2: T).(\forall (u2: T).(\forall (i2: nat).((subst1 i2 u2 t0 t2)
109 \to ((not (eq nat i1 i2)) \to (ex2 T (\lambda (t3: T).(subst1 i2 u2 t t3))
110 (\lambda (t3: T).(subst1 i1 u1 t2 t3))))))))) (\lambda (t2: T).(\lambda (u2:
111 T).(\lambda (i2: nat).(\lambda (H0: (subst1 i2 u2 t0 t2)).(\lambda (_: (not
112 (eq nat i1 i2))).(ex_intro2 T (\lambda (t: T).(subst1 i2 u2 t0 t)) (\lambda
113 (t: T).(subst1 i1 u1 t2 t)) t2 H0 (subst1_refl i1 u1 t2))))))) (\lambda (t2:
114 T).(\lambda (H0: (subst0 i1 u1 t0 t2)).(\lambda (t3: T).(\lambda (u2:
115 T).(\lambda (i2: nat).(\lambda (H1: (subst1 i2 u2 t0 t3)).(\lambda (H2: (not
116 (eq nat i1 i2))).(subst1_ind i2 u2 t0 (\lambda (t: T).(ex2 T (\lambda (t4:
117 T).(subst1 i2 u2 t2 t4)) (\lambda (t4: T).(subst1 i1 u1 t t4)))) (ex_intro2 T
118 (\lambda (t: T).(subst1 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t0 t)) t2
119 (subst1_refl i2 u2 t2) (subst1_single i1 u1 t0 t2 H0)) (\lambda (t4:
120 T).(\lambda (H3: (subst0 i2 u2 t0 t4)).(ex2_ind T (\lambda (t: T).(subst0 i1
121 u1 t4 t)) (\lambda (t: T).(subst0 i2 u2 t2 t)) (ex2 T (\lambda (t: T).(subst1
122 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t4 t))) (\lambda (x: T).(\lambda
123 (H4: (subst0 i1 u1 t4 x)).(\lambda (H5: (subst0 i2 u2 t2 x)).(ex_intro2 T
124 (\lambda (t: T).(subst1 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t4 t)) x
125 (subst1_single i2 u2 t2 x H5) (subst1_single i1 u1 t4 x H4)))))
126 (subst0_confluence_neq t0 t4 u2 i2 H3 t2 u1 i1 H0 (sym_not_eq nat i1 i2
127 H2))))) t3 H1)))))))) t1 H))))).
129 theorem subst1_confluence_eq:
130 \forall (t0: T).(\forall (t1: T).(\forall (u: T).(\forall (i: nat).((subst1
131 i u t0 t1) \to (\forall (t2: T).((subst1 i u t0 t2) \to (ex2 T (\lambda (t:
132 T).(subst1 i u t1 t)) (\lambda (t: T).(subst1 i u t2 t)))))))))
134 \lambda (t0: T).(\lambda (t1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda
135 (H: (subst1 i u t0 t1)).(subst1_ind i u t0 (\lambda (t: T).(\forall (t2:
136 T).((subst1 i u t0 t2) \to (ex2 T (\lambda (t3: T).(subst1 i u t t3))
137 (\lambda (t3: T).(subst1 i u t2 t3)))))) (\lambda (t2: T).(\lambda (H0:
138 (subst1 i u t0 t2)).(ex_intro2 T (\lambda (t: T).(subst1 i u t0 t)) (\lambda
139 (t: T).(subst1 i u t2 t)) t2 H0 (subst1_refl i u t2)))) (\lambda (t2:
140 T).(\lambda (H0: (subst0 i u t0 t2)).(\lambda (t3: T).(\lambda (H1: (subst1 i
141 u t0 t3)).(subst1_ind i u t0 (\lambda (t: T).(ex2 T (\lambda (t4: T).(subst1
142 i u t2 t4)) (\lambda (t4: T).(subst1 i u t t4)))) (ex_intro2 T (\lambda (t:
143 T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t0 t)) t2 (subst1_refl i u
144 t2) (subst1_single i u t0 t2 H0)) (\lambda (t4: T).(\lambda (H2: (subst0 i u
145 t0 t4)).(or4_ind (eq T t4 t2) (ex2 T (\lambda (t: T).(subst0 i u t4 t))
146 (\lambda (t: T).(subst0 i u t2 t))) (subst0 i u t4 t2) (subst0 i u t2 t4)
147 (ex2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t4 t)))
148 (\lambda (H3: (eq T t4 t2)).(eq_ind_r T t2 (\lambda (t: T).(ex2 T (\lambda
149 (t5: T).(subst1 i u t2 t5)) (\lambda (t5: T).(subst1 i u t t5)))) (ex_intro2
150 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t2 t)) t2
151 (subst1_refl i u t2) (subst1_refl i u t2)) t4 H3)) (\lambda (H3: (ex2 T
152 (\lambda (t: T).(subst0 i u t4 t)) (\lambda (t: T).(subst0 i u t2
153 t)))).(ex2_ind T (\lambda (t: T).(subst0 i u t4 t)) (\lambda (t: T).(subst0 i
154 u t2 t)) (ex2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i
155 u t4 t))) (\lambda (x: T).(\lambda (H4: (subst0 i u t4 x)).(\lambda (H5:
156 (subst0 i u t2 x)).(ex_intro2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda
157 (t: T).(subst1 i u t4 t)) x (subst1_single i u t2 x H5) (subst1_single i u t4
158 x H4))))) H3)) (\lambda (H3: (subst0 i u t4 t2)).(ex_intro2 T (\lambda (t:
159 T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t4 t)) t2 (subst1_refl i u
160 t2) (subst1_single i u t4 t2 H3))) (\lambda (H3: (subst0 i u t2
161 t4)).(ex_intro2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1
162 i u t4 t)) t4 (subst1_single i u t2 t4 H3) (subst1_refl i u t4)))
163 (subst0_confluence_eq t0 t4 u i H2 t2 H0)))) t3 H1))))) t1 H))))).
165 theorem subst1_confluence_lift:
166 \forall (t0: T).(\forall (t1: T).(\forall (u: T).(\forall (i: nat).((subst1
167 i u t0 (lift (S O) i t1)) \to (\forall (t2: T).((subst1 i u t0 (lift (S O) i
168 t2)) \to (eq T t1 t2)))))))
170 \lambda (t0: T).(\lambda (t1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda
171 (H: (subst1 i u t0 (lift (S O) i t1))).(insert_eq T (lift (S O) i t1)
172 (\lambda (t: T).(subst1 i u t0 t)) (\forall (t2: T).((subst1 i u t0 (lift (S
173 O) i t2)) \to (eq T t1 t2))) (\lambda (y: T).(\lambda (H0: (subst1 i u t0
174 y)).(subst1_ind i u t0 (\lambda (t: T).((eq T t (lift (S O) i t1)) \to
175 (\forall (t2: T).((subst1 i u t0 (lift (S O) i t2)) \to (eq T t1 t2)))))
176 (\lambda (H1: (eq T t0 (lift (S O) i t1))).(\lambda (t2: T).(\lambda (H2:
177 (subst1 i u t0 (lift (S O) i t2))).(let H3 \def (eq_ind T t0 (\lambda (t:
178 T).(subst1 i u t (lift (S O) i t2))) H2 (lift (S O) i t1) H1) in (let H4 \def
179 (sym_eq T (lift (S O) i t2) (lift (S O) i t1) (subst1_gen_lift_eq t1 u (lift
180 (S O) i t2) (S O) i i (le_n i) (eq_ind_r nat (plus (S O) i) (\lambda (n:
181 nat).(lt i n)) (le_n (plus (S O) i)) (plus i (S O)) (plus_comm i (S O))) H3))
182 in (lift_inj t1 t2 (S O) i H4)))))) (\lambda (t2: T).(\lambda (H1: (subst0 i
183 u t0 t2)).(\lambda (H2: (eq T t2 (lift (S O) i t1))).(\lambda (t3:
184 T).(\lambda (H3: (subst1 i u t0 (lift (S O) i t3))).(let H4 \def (eq_ind T t2
185 (\lambda (t: T).(subst0 i u t0 t)) H1 (lift (S O) i t1) H2) in (insert_eq T
186 (lift (S O) i t3) (\lambda (t: T).(subst1 i u t0 t)) (eq T t1 t3) (\lambda
187 (y0: T).(\lambda (H5: (subst1 i u t0 y0)).(subst1_ind i u t0 (\lambda (t:
188 T).((eq T t (lift (S O) i t3)) \to (eq T t1 t3))) (\lambda (H6: (eq T t0
189 (lift (S O) i t3))).(let H7 \def (eq_ind T t0 (\lambda (t: T).(subst0 i u t
190 (lift (S O) i t1))) H4 (lift (S O) i t3) H6) in (subst0_gen_lift_false t3 u
191 (lift (S O) i t1) (S O) i i (le_n i) (eq_ind_r nat (plus (S O) i) (\lambda
192 (n: nat).(lt i n)) (le_n (plus (S O) i)) (plus i (S O)) (plus_comm i (S O)))
193 H7 (eq T t1 t3)))) (\lambda (t4: T).(\lambda (H6: (subst0 i u t0
194 t4)).(\lambda (H7: (eq T t4 (lift (S O) i t3))).(let H8 \def (eq_ind T t4
195 (\lambda (t: T).(subst0 i u t0 t)) H6 (lift (S O) i t3) H7) in (sym_eq T t3
196 t1 (subst0_confluence_lift t0 t3 u i H8 t1 H4)))))) y0 H5))) H3))))))) y