changeset 9941 | fe05af7ec816 |
parent 9906 | 5c027cca6262 |
child 10851 | 31ac62e3a0ed |
9940:102f2430cef9 | 9941:fe05af7ec816 |
---|---|
118 |
118 |
119 lemma subst_lt [simp]: "j < i ==> (Var j)[u/i] = Var j" |
119 lemma subst_lt [simp]: "j < i ==> (Var j)[u/i] = Var j" |
120 apply (simp add: subst_Var) |
120 apply (simp add: subst_Var) |
121 done |
121 done |
122 |
122 |
123 lemma lift_lift [rulified]: |
123 lemma lift_lift [rule_format]: |
124 "\<forall>i k. i < k + 1 --> lift (lift t i) (Suc k) = lift (lift t k) i" |
124 "\<forall>i k. i < k + 1 --> lift (lift t i) (Suc k) = lift (lift t k) i" |
125 apply (induct_tac t) |
125 apply (induct_tac t) |
126 apply auto |
126 apply auto |
127 done |
127 done |
128 |
128 |
142 "\<forall>k s. (lift t k)[s/k] = t" |
142 "\<forall>k s. (lift t k)[s/k] = t" |
143 apply (induct_tac t) |
143 apply (induct_tac t) |
144 apply simp_all |
144 apply simp_all |
145 done |
145 done |
146 |
146 |
147 lemma subst_subst [rulified]: |
147 lemma subst_subst [rule_format]: |
148 "\<forall>i j u v. i < j + 1 --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]" |
148 "\<forall>i j u v. i < j + 1 --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]" |
149 apply (induct_tac t) |
149 apply (induct_tac t) |
150 apply (simp_all |
150 apply (simp_all |
151 add: diff_Suc subst_Var lift_lift [symmetric] lift_subst_lt |
151 add: diff_Suc subst_Var lift_lift [symmetric] lift_subst_lt |
152 split: nat.split) |
152 split: nat.split) |
181 subsection {* Preservation theorems *} |
181 subsection {* Preservation theorems *} |
182 |
182 |
183 text {* Not used in Church-Rosser proof, but in Strong |
183 text {* Not used in Church-Rosser proof, but in Strong |
184 Normalization. \medskip *} |
184 Normalization. \medskip *} |
185 |
185 |
186 theorem subst_preserves_beta [rulified, simp]: |
186 theorem subst_preserves_beta [rule_format, simp]: |
187 "r -> s ==> \<forall>t i. r[t/i] -> s[t/i]" |
187 "r -> s ==> \<forall>t i. r[t/i] -> s[t/i]" |
188 apply (erule beta.induct) |
188 apply (erule beta.induct) |
189 apply (simp_all add: subst_subst [symmetric]) |
189 apply (simp_all add: subst_subst [symmetric]) |
190 done |
190 done |
191 |
191 |
192 theorem lift_preserves_beta [rulified, simp]: |
192 theorem lift_preserves_beta [rule_format, simp]: |
193 "r -> s ==> \<forall>i. lift r i -> lift s i" |
193 "r -> s ==> \<forall>i. lift r i -> lift s i" |
194 apply (erule beta.induct) |
194 apply (erule beta.induct) |
195 apply auto |
195 apply auto |
196 done |
196 done |
197 |
197 |
198 theorem subst_preserves_beta2 [rulified, simp]: |
198 theorem subst_preserves_beta2 [rule_format, simp]: |
199 "\<forall>r s i. r -> s --> t[r/i] ->> t[s/i]" |
199 "\<forall>r s i. r -> s --> t[r/i] ->> t[s/i]" |
200 apply (induct_tac t) |
200 apply (induct_tac t) |
201 apply (simp add: subst_Var r_into_rtrancl) |
201 apply (simp add: subst_Var r_into_rtrancl) |
202 apply (simp add: rtrancl_beta_App) |
202 apply (simp add: rtrancl_beta_App) |
203 apply (simp add: rtrancl_beta_Abs) |
203 apply (simp add: rtrancl_beta_Abs) |