src/HOL/Lambda/WeakNorm.thy
changeset 18513 791b53bf4073
parent 18331 eb3a7d3d874b
child 19086 1b3780be6cc2
equal deleted inserted replaced
18512:f8df49d4af35 18513:791b53bf4073
   107   apply (rule NF.App)
   107   apply (rule NF.App)
   108   apply simp
   108   apply simp
   109   done
   109   done
   110 
   110 
   111 lemma subst_terms_NF: "listall (\<lambda>t. t \<in> NF) ts \<Longrightarrow>
   111 lemma subst_terms_NF: "listall (\<lambda>t. t \<in> NF) ts \<Longrightarrow>
   112   listall (\<lambda>t. \<forall>i j. t[Var i/j] \<in> NF) ts \<Longrightarrow>
   112     listall (\<lambda>t. \<forall>i j. t[Var i/j] \<in> NF) ts \<Longrightarrow>
   113   listall (\<lambda>t. t \<in> NF) (map (\<lambda>t. t[Var i/j]) ts)"
   113     listall (\<lambda>t. t \<in> NF) (map (\<lambda>t. t[Var i/j]) ts)"
   114   by (induct ts) simp+
   114   by (induct ts) simp_all
   115 
   115 
   116 lemma subst_Var_NF: "t \<in> NF \<Longrightarrow> t[Var i/j] \<in> NF"
   116 lemma subst_Var_NF: "t \<in> NF \<Longrightarrow> t[Var i/j] \<in> NF"
   117   apply (induct fixing: i j set: NF)
   117   apply (induct fixing: i j set: NF)
   118   apply simp
   118   apply simp
   119   apply (frule listall_conj1)
   119   apply (frule listall_conj1)
   149   apply (rule beta)
   149   apply (rule beta)
   150   apply (erule subst_Var_NF)
   150   apply (erule subst_Var_NF)
   151   done
   151   done
   152 
   152 
   153 lemma lift_terms_NF: "listall (\<lambda>t. t \<in> NF) ts \<Longrightarrow>
   153 lemma lift_terms_NF: "listall (\<lambda>t. t \<in> NF) ts \<Longrightarrow>
   154   listall (\<lambda>t. \<forall>i. lift t i \<in> NF) ts \<Longrightarrow>
   154     listall (\<lambda>t. \<forall>i. lift t i \<in> NF) ts \<Longrightarrow>
   155   listall (\<lambda>t. t \<in> NF) (map (\<lambda>t. lift t i) ts)"
   155     listall (\<lambda>t. t \<in> NF) (map (\<lambda>t. lift t i) ts)"
   156   by (induct ts) simp_all
   156   by (induct ts) simp_all
   157 
   157 
   158 lemma lift_NF: "t \<in> NF \<Longrightarrow> lift t i \<in> NF"
   158 lemma lift_NF: "t \<in> NF \<Longrightarrow> lift t i \<in> NF"
   159   apply (induct fixing: i set: NF)
   159   apply (induct fixing: i set: NF)
   160   apply (frule listall_conj1)
   160   apply (frule listall_conj1)
   381   apply (erule typing.App)
   381   apply (erule typing.App)
   382   apply assumption
   382   apply assumption
   383   done
   383   done
   384 
   384 
   385 
   385 
   386 theorem type_NF: assumes T: "e \<turnstile>\<^sub>R t : T"
   386 theorem type_NF:
   387   shows "\<exists>t'. t \<rightarrow>\<^sub>\<beta>\<^sup>* t' \<and> t' \<in> NF" using T
   387   assumes "e \<turnstile>\<^sub>R t : T"
       
   388   shows "\<exists>t'. t \<rightarrow>\<^sub>\<beta>\<^sup>* t' \<and> t' \<in> NF" using prems
   388 proof induct
   389 proof induct
   389   case Var
   390   case Var
   390   show ?case by (iprover intro: Var_NF)
   391   show ?case by (iprover intro: Var_NF)
   391 next
   392 next
   392   case Abs
   393   case Abs