equal
deleted
inserted
replaced
1 (* Title: HOL/Lambda/NormalForm.thy |
1 (* Title: HOL/Lambda/NormalForm.thy |
2 ID: $Id$ |
|
3 Author: Stefan Berghofer, TU Muenchen, 2003 |
2 Author: Stefan Berghofer, TU Muenchen, 2003 |
4 *) |
3 *) |
5 |
4 |
6 header {* Inductive characterization of lambda terms in normal form *} |
5 header {* Inductive characterization of lambda terms in normal form *} |
7 |
6 |
198 case (App ts t) |
197 case (App ts t) |
199 show ?case |
198 show ?case |
200 proof |
199 proof |
201 assume "Var t \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> t'" |
200 assume "Var t \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> t'" |
202 then obtain rs where "ts => rs" |
201 then obtain rs where "ts => rs" |
203 by (iprover dest: head_Var_reduction) |
202 by (iprover dest: head_Var_reduction) |
204 with App show False |
203 with App show False |
205 by (induct rs arbitrary: ts) auto |
204 by (induct rs arbitrary: ts) auto |
206 qed |
205 qed |
207 next |
206 next |
208 case (Abs t) |
207 case (Abs t) |
209 show ?case |
208 show ?case |
210 proof |
209 proof |
227 case (2 u ts) |
226 case (2 u ts) |
228 show ?case |
227 show ?case |
229 proof (cases ts) |
228 proof (cases ts) |
230 case Nil |
229 case Nil |
231 from 2 have "\<forall>u'. \<not> u \<rightarrow>\<^sub>\<beta> u'" |
230 from 2 have "\<forall>u'. \<not> u \<rightarrow>\<^sub>\<beta> u'" |
232 by (auto intro: apps_preserves_beta) |
231 by (auto intro: apps_preserves_beta) |
233 then have "NF u" by (rule 2) |
232 then have "NF u" by (rule 2) |
234 then have "NF (Abs u)" by (rule NF.Abs) |
233 then have "NF (Abs u)" by (rule NF.Abs) |
235 with Nil show ?thesis by simp |
234 with Nil show ?thesis by simp |
236 next |
235 next |
237 case (Cons r rs) |
236 case (Cons r rs) |
238 have "Abs u \<degree> r \<rightarrow>\<^sub>\<beta> u[r/0]" .. |
237 have "Abs u \<degree> r \<rightarrow>\<^sub>\<beta> u[r/0]" .. |
239 then have "Abs u \<degree> r \<degree>\<degree> rs \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs" |
238 then have "Abs u \<degree> r \<degree>\<degree> rs \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs" |
240 by (rule apps_preserves_beta) |
239 by (rule apps_preserves_beta) |
241 with Cons have "Abs u \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs" |
240 with Cons have "Abs u \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs" |
242 by simp |
241 by simp |
243 with 2 show ?thesis by iprover |
242 with 2 show ?thesis by iprover |
244 qed |
243 qed |
245 qed |
244 qed |
246 qed |
245 qed |
247 |
246 |