src/HOL/Nominal/Examples/SN.thy
changeset 32960 69916a850301
parent 29097 68245155eb58
child 35416 d8d7d1b785af
equal deleted inserted replaced
32959:23a8c5ac35f8 32960:69916a850301
   200     have "SN b" by fact
   200     have "SN b" by fact
   201     thus ?case
   201     thus ?case
   202     proof (induct b rule: SN.SN.induct)
   202     proof (induct b rule: SN.SN.induct)
   203       case (SN_intro y)
   203       case (SN_intro y)
   204       show ?case
   204       show ?case
   205 	apply (rule hyp)
   205         apply (rule hyp)
   206 	apply (erule SNI')
   206         apply (erule SNI')
   207 	apply (erule SNI')
   207         apply (erule SNI')
   208 	apply (rule SN.SN_intro)
   208         apply (rule SN.SN_intro)
   209 	apply (erule SN_intro)+
   209         apply (erule SN_intro)+
   210 	done
   210         done
   211     qed
   211     qed
   212   qed
   212   qed
   213   from b show ?thesis by (rule r)
   213   from b show ?thesis by (rule r)
   214 qed
   214 qed
   215 
   215 
   430       assume ih2: "\<And>u'.  \<lbrakk>u \<longrightarrow>\<^isub>\<beta> u'; u'\<in>RED \<tau>; \<forall>s\<in>RED \<tau>. t[x::=s]\<in>RED \<sigma>\<rbrakk> \<Longrightarrow> App (Lam [x].t) u' \<in> RED \<sigma>"
   430       assume ih2: "\<And>u'.  \<lbrakk>u \<longrightarrow>\<^isub>\<beta> u'; u'\<in>RED \<tau>; \<forall>s\<in>RED \<tau>. t[x::=s]\<in>RED \<sigma>\<rbrakk> \<Longrightarrow> App (Lam [x].t) u' \<in> RED \<sigma>"
   431       assume as1: "u \<in> RED \<tau>"
   431       assume as1: "u \<in> RED \<tau>"
   432       assume as2: "\<forall>s\<in>RED \<tau>. t[x::=s]\<in>RED \<sigma>"
   432       assume as2: "\<forall>s\<in>RED \<tau>. t[x::=s]\<in>RED \<sigma>"
   433       have "CR3_RED (App (Lam [x].t) u) \<sigma>" unfolding CR3_RED_def
   433       have "CR3_RED (App (Lam [x].t) u) \<sigma>" unfolding CR3_RED_def
   434       proof(intro strip)
   434       proof(intro strip)
   435 	fix r
   435         fix r
   436 	assume red: "App (Lam [x].t) u \<longrightarrow>\<^isub>\<beta> r"
   436         assume red: "App (Lam [x].t) u \<longrightarrow>\<^isub>\<beta> r"
   437 	moreover
   437         moreover
   438 	{ assume "\<exists>t'. t \<longrightarrow>\<^isub>\<beta> t' \<and> r = App (Lam [x].t') u"
   438         { assume "\<exists>t'. t \<longrightarrow>\<^isub>\<beta> t' \<and> r = App (Lam [x].t') u"
   439 	  then obtain t' where a1: "t \<longrightarrow>\<^isub>\<beta> t'" and a2: "r = App (Lam [x].t') u" by blast
   439           then obtain t' where a1: "t \<longrightarrow>\<^isub>\<beta> t'" and a2: "r = App (Lam [x].t') u" by blast
   440 	  have "App (Lam [x].t') u\<in>RED \<sigma>" using ih1 a1 as1 as2
   440           have "App (Lam [x].t') u\<in>RED \<sigma>" using ih1 a1 as1 as2
   441 	    apply(auto)
   441             apply(auto)
   442 	    apply(drule_tac x="t'" in meta_spec)
   442             apply(drule_tac x="t'" in meta_spec)
   443 	    apply(simp)
   443             apply(simp)
   444 	    apply(drule meta_mp)
   444             apply(drule meta_mp)
   445 	    prefer 2
   445             prefer 2
   446 	    apply(auto)[1]
   446             apply(auto)[1]
   447 	    apply(rule ballI)
   447             apply(rule ballI)
   448 	    apply(drule_tac x="s" in bspec)
   448             apply(drule_tac x="s" in bspec)
   449 	    apply(simp)
   449             apply(simp)
   450 	    apply(subgoal_tac "CR2 \<sigma>")(*A*)
   450             apply(subgoal_tac "CR2 \<sigma>")(*A*)
   451 	    apply(unfold CR2_def)[1]
   451             apply(unfold CR2_def)[1]
   452 	    apply(drule_tac x="t[x::=s]" in spec)
   452             apply(drule_tac x="t[x::=s]" in spec)
   453 	    apply(drule_tac x="t'[x::=s]" in spec)
   453             apply(drule_tac x="t'[x::=s]" in spec)
   454 	    apply(simp add: beta_subst)
   454             apply(simp add: beta_subst)
   455 	    (*A*)
   455             (*A*)
   456 	    apply(simp add: RED_props)
   456             apply(simp add: RED_props)
   457 	    done
   457             done
   458 	  then have "r\<in>RED \<sigma>" using a2 by simp
   458           then have "r\<in>RED \<sigma>" using a2 by simp
   459 	}
   459         }
   460 	moreover
   460         moreover
   461 	{ assume "\<exists>u'. u \<longrightarrow>\<^isub>\<beta> u' \<and> r = App (Lam [x].t) u'"
   461         { assume "\<exists>u'. u \<longrightarrow>\<^isub>\<beta> u' \<and> r = App (Lam [x].t) u'"
   462 	  then obtain u' where b1: "u \<longrightarrow>\<^isub>\<beta> u'" and b2: "r = App (Lam [x].t) u'" by blast
   462           then obtain u' where b1: "u \<longrightarrow>\<^isub>\<beta> u'" and b2: "r = App (Lam [x].t) u'" by blast
   463 	  have "App (Lam [x].t) u'\<in>RED \<sigma>" using ih2 b1 as1 as2
   463           have "App (Lam [x].t) u'\<in>RED \<sigma>" using ih2 b1 as1 as2
   464 	    apply(auto)
   464             apply(auto)
   465 	    apply(drule_tac x="u'" in meta_spec)
   465             apply(drule_tac x="u'" in meta_spec)
   466 	    apply(simp)
   466             apply(simp)
   467 	    apply(drule meta_mp)
   467             apply(drule meta_mp)
   468 	    apply(subgoal_tac "CR2 \<tau>")
   468             apply(subgoal_tac "CR2 \<tau>")
   469 	    apply(unfold CR2_def)[1]
   469             apply(unfold CR2_def)[1]
   470 	    apply(drule_tac x="u" in spec)
   470             apply(drule_tac x="u" in spec)
   471 	    apply(drule_tac x="u'" in spec)
   471             apply(drule_tac x="u'" in spec)
   472 	    apply(simp)
   472             apply(simp)
   473 	    apply(simp add: RED_props)
   473             apply(simp add: RED_props)
   474 	    apply(simp)
   474             apply(simp)
   475 	    done
   475             done
   476 	  then have "r\<in>RED \<sigma>" using b2 by simp
   476           then have "r\<in>RED \<sigma>" using b2 by simp
   477 	}
   477         }
   478 	moreover
   478         moreover
   479 	{ assume "r = t[x::=u]"
   479         { assume "r = t[x::=u]"
   480 	  then have "r\<in>RED \<sigma>" using as1 as2 by auto
   480           then have "r\<in>RED \<sigma>" using as1 as2 by auto
   481 	}
   481         }
   482 	ultimately show "r \<in> RED \<sigma>" 
   482         ultimately show "r \<in> RED \<sigma>" 
   483 	  (* one wants to use the strong elimination principle; for this one 
   483           (* one wants to use the strong elimination principle; for this one 
   484 	     has to know that x\<sharp>u *)
   484              has to know that x\<sharp>u *)
   485 	apply(cases) 
   485         apply(cases) 
   486 	apply(auto simp add: lam.inject)
   486         apply(auto simp add: lam.inject)
   487 	apply(drule beta_abs)
   487         apply(drule beta_abs)
   488 	apply(auto)[1]
   488         apply(auto)[1]
   489 	apply(auto simp add: alpha subst_rename)
   489         apply(auto simp add: alpha subst_rename)
   490 	done
   490         done
   491     qed
   491     qed
   492     moreover 
   492     moreover 
   493     have "NEUT (App (Lam [x].t) u)" unfolding NEUT_def by (auto)
   493     have "NEUT (App (Lam [x].t) u)" unfolding NEUT_def by (auto)
   494     ultimately show "App (Lam [x].t) u \<in> RED \<sigma>"  using RED_props by (simp add: CR3_def)
   494     ultimately show "App (Lam [x].t) u \<in> RED \<sigma>"  using RED_props by (simp add: CR3_def)
   495   qed
   495   qed