src/HOL/Nominal/Nominal.thy
changeset 32960 69916a850301
parent 32638 d9bd7e01a681
child 35353 1391f82da5a4
child 35416 d8d7d1b785af
equal deleted inserted replaced
32959:23a8c5ac35f8 32960:69916a850301
  2657     have d3: "({x} \<union> Xs) \<subseteq> As" using insert(4) by simp
  2657     have d3: "({x} \<union> Xs) \<subseteq> As" using insert(4) by simp
  2658     from d d1 d2
  2658     from d d1 d2
  2659     obtain y::"'a" where fr: "y\<sharp>(c,pi\<bullet>Xs,As)" 
  2659     obtain y::"'a" where fr: "y\<sharp>(c,pi\<bullet>Xs,As)" 
  2660       apply(rule_tac at_exists_fresh[OF at, where x="(c,pi\<bullet>Xs,As)"])
  2660       apply(rule_tac at_exists_fresh[OF at, where x="(c,pi\<bullet>Xs,As)"])
  2661       apply(auto simp add: supp_prod at_supp[OF at] at_fin_set_supp[OF at]
  2661       apply(auto simp add: supp_prod at_supp[OF at] at_fin_set_supp[OF at]
  2662 	pt_supp_finite_pi[OF pt_fun_inst[OF at_pt_inst[OF at] pt_bool_inst at] at])
  2662         pt_supp_finite_pi[OF pt_fun_inst[OF at_pt_inst[OF at] pt_bool_inst at] at])
  2663       done
  2663       done
  2664     have "({y}\<union>(pi\<bullet>Xs))\<sharp>*c" using a1 fr by (simp add: fresh_star_def)
  2664     have "({y}\<union>(pi\<bullet>Xs))\<sharp>*c" using a1 fr by (simp add: fresh_star_def)
  2665     moreover
  2665     moreover
  2666     have "({y}\<union>(pi\<bullet>Xs))\<inter>As = {}" using a2 d1 fr 
  2666     have "({y}\<union>(pi\<bullet>Xs))\<inter>As = {}" using a2 d1 fr 
  2667       by (simp add: fresh_prod at_fin_set_fresh[OF at])
  2667       by (simp add: fresh_prod at_fin_set_fresh[OF at])
  2672     moreover
  2672     moreover
  2673     have "(((pi\<bullet>x,y)#pi)\<bullet>({x} \<union> Xs)) = {y}\<union>(pi\<bullet>Xs)"
  2673     have "(((pi\<bullet>x,y)#pi)\<bullet>({x} \<union> Xs)) = {y}\<union>(pi\<bullet>Xs)"
  2674     proof -
  2674     proof -
  2675       have eq: "[(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs) = (pi\<bullet>Xs)" 
  2675       have eq: "[(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs) = (pi\<bullet>Xs)" 
  2676       proof -
  2676       proof -
  2677 	have "(pi\<bullet>x)\<sharp>(pi\<bullet>Xs)" using b d2 
  2677         have "(pi\<bullet>x)\<sharp>(pi\<bullet>Xs)" using b d2 
  2678 	  by(simp add: pt_fresh_bij[OF pt_fun_inst, OF at_pt_inst[OF at], 
  2678           by(simp add: pt_fresh_bij[OF pt_fun_inst, OF at_pt_inst[OF at], 
  2679             OF pt_bool_inst, OF at, OF at]
  2679             OF pt_bool_inst, OF at, OF at]
  2680             at_fin_set_fresh[OF at])
  2680             at_fin_set_fresh[OF at])
  2681 	moreover
  2681         moreover
  2682 	have "y\<sharp>(pi\<bullet>Xs)" using fr by simp
  2682         have "y\<sharp>(pi\<bullet>Xs)" using fr by simp
  2683 	ultimately show "[(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs) = (pi\<bullet>Xs)" 
  2683         ultimately show "[(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs) = (pi\<bullet>Xs)" 
  2684 	  by (simp add: pt_fresh_fresh[OF pt_fun_inst, 
  2684           by (simp add: pt_fresh_fresh[OF pt_fun_inst, 
  2685             OF at_pt_inst[OF at], OF pt_bool_inst, OF at, OF at])
  2685             OF at_pt_inst[OF at], OF pt_bool_inst, OF at, OF at])
  2686       qed
  2686       qed
  2687       have "(((pi\<bullet>x,y)#pi)\<bullet>({x}\<union>Xs)) = ([(pi\<bullet>x,y)]\<bullet>(pi\<bullet>({x}\<union>Xs)))"
  2687       have "(((pi\<bullet>x,y)#pi)\<bullet>({x}\<union>Xs)) = ([(pi\<bullet>x,y)]\<bullet>(pi\<bullet>({x}\<union>Xs)))"
  2688 	by (simp add: pt2[symmetric, OF pt_fun_inst, OF at_pt_inst[OF at], 
  2688         by (simp add: pt2[symmetric, OF pt_fun_inst, OF at_pt_inst[OF at], 
  2689           OF pt_bool_inst, OF at])
  2689           OF pt_bool_inst, OF at])
  2690       also have "\<dots> = {y}\<union>([(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs))" 
  2690       also have "\<dots> = {y}\<union>([(pi\<bullet>x,y)]\<bullet>(pi\<bullet>Xs))" 
  2691 	by (simp only: union_eqvt perm_set_eq[OF at_pt_inst[OF at], OF at] at_calc[OF at])(auto)
  2691         by (simp only: union_eqvt perm_set_eq[OF at_pt_inst[OF at], OF at] at_calc[OF at])(auto)
  2692       finally show "(((pi\<bullet>x,y)#pi)\<bullet>({x} \<union> Xs)) = {y}\<union>(pi\<bullet>Xs)" using eq by simp
  2692       finally show "(((pi\<bullet>x,y)#pi)\<bullet>({x} \<union> Xs)) = {y}\<union>(pi\<bullet>Xs)" using eq by simp
  2693     qed
  2693     qed
  2694     ultimately 
  2694     ultimately 
  2695     show ?case by (rule_tac x="(pi\<bullet>x,y)#pi" in exI) (auto)
  2695     show ?case by (rule_tac x="(pi\<bullet>x,y)#pi" in exI) (auto)
  2696   qed
  2696   qed
  2793     proof (intro strip)
  2793     proof (intro strip)
  2794       fix a
  2794       fix a
  2795       assume a3: "(a::'x)\<sharp>h"
  2795       assume a3: "(a::'x)\<sharp>h"
  2796       show "h (a::'x) = h a0"
  2796       show "h (a::'x) = h a0"
  2797       proof (cases "a=a0")
  2797       proof (cases "a=a0")
  2798 	case True thus "h (a::'x) = h a0" by simp
  2798         case True thus "h (a::'x) = h a0" by simp
  2799       next
  2799       next
  2800 	case False 
  2800         case False 
  2801 	assume "a\<noteq>a0"
  2801         assume "a\<noteq>a0"
  2802 	hence c1: "a\<notin>((supp a0)::'x set)" by  (simp add: fresh_def[symmetric] at_fresh[OF at])
  2802         hence c1: "a\<notin>((supp a0)::'x set)" by  (simp add: fresh_def[symmetric] at_fresh[OF at])
  2803 	have c2: "a\<notin>((supp h)::'x set)" using a3 by (simp add: fresh_def)
  2803         have c2: "a\<notin>((supp h)::'x set)" using a3 by (simp add: fresh_def)
  2804 	from c1 c2 have c3: "a\<notin>((supp h)\<union>((supp a0)::'x set))" by force
  2804         from c1 c2 have c3: "a\<notin>((supp h)\<union>((supp a0)::'x set))" by force
  2805 	have f2: "finite ((supp a0)::'x set)" by (simp add: at_supp[OF at])
  2805         have f2: "finite ((supp a0)::'x set)" by (simp add: at_supp[OF at])
  2806 	from f1 f2 have "((supp (h a0))::'x set)\<subseteq>((supp h)\<union>(supp a0))"
  2806         from f1 f2 have "((supp (h a0))::'x set)\<subseteq>((supp h)\<union>(supp a0))"
  2807 	  by (simp add: pt_supp_fun_subset[OF ptb, OF pta, OF at])
  2807           by (simp add: pt_supp_fun_subset[OF ptb, OF pta, OF at])
  2808 	hence "a\<notin>((supp (h a0))::'x set)" using c3 by force
  2808         hence "a\<notin>((supp (h a0))::'x set)" using c3 by force
  2809 	hence "a\<sharp>(h a0)" by (simp add: fresh_def) 
  2809         hence "a\<sharp>(h a0)" by (simp add: fresh_def) 
  2810 	with a2 have d1: "[(a0,a)]\<bullet>(h a0) = (h a0)" by (rule pt_fresh_fresh[OF pta, OF at])
  2810         with a2 have d1: "[(a0,a)]\<bullet>(h a0) = (h a0)" by (rule pt_fresh_fresh[OF pta, OF at])
  2811 	from a1 a3 have d2: "[(a0,a)]\<bullet>h = h" by (rule pt_fresh_fresh[OF ptc, OF at])
  2811         from a1 a3 have d2: "[(a0,a)]\<bullet>h = h" by (rule pt_fresh_fresh[OF ptc, OF at])
  2812 	from d1 have "h a0 = [(a0,a)]\<bullet>(h a0)" by simp
  2812         from d1 have "h a0 = [(a0,a)]\<bullet>(h a0)" by simp
  2813 	also have "\<dots>= ([(a0,a)]\<bullet>h)([(a0,a)]\<bullet>a0)" by (simp add: pt_fun_app_eq[OF ptb, OF at])
  2813         also have "\<dots>= ([(a0,a)]\<bullet>h)([(a0,a)]\<bullet>a0)" by (simp add: pt_fun_app_eq[OF ptb, OF at])
  2814 	also have "\<dots> = h ([(a0,a)]\<bullet>a0)" using d2 by simp
  2814         also have "\<dots> = h ([(a0,a)]\<bullet>a0)" using d2 by simp
  2815 	also have "\<dots> = h a" by (simp add: at_calc[OF at])
  2815         also have "\<dots> = h a" by (simp add: at_calc[OF at])
  2816 	finally show "h a = h a0" by simp
  2816         finally show "h a = h a0" by simp
  2817       qed
  2817       qed
  2818     qed
  2818     qed
  2819   qed
  2819   qed
  2820 qed
  2820 qed
  2821 	    
  2821 
  2822 lemma freshness_lemma_unique:
  2822 lemma freshness_lemma_unique:
  2823   fixes h :: "'x\<Rightarrow>'a"
  2823   fixes h :: "'x\<Rightarrow>'a"
  2824   assumes pt: "pt TYPE('a) TYPE('x)"
  2824   assumes pt: "pt TYPE('a) TYPE('x)"
  2825   and     at: "at TYPE('x)" 
  2825   and     at: "at TYPE('x)" 
  2826   and     f1: "finite ((supp h)::'x set)"
  2826   and     f1: "finite ((supp h)::'x set)"
  3088     show "?LHS=?RHS"
  3088     show "?LHS=?RHS"
  3089     proof -
  3089     proof -
  3090       have "(c=a) \<or> (c=b) \<or> (c\<noteq>a \<and> c\<noteq>b)" by blast
  3090       have "(c=a) \<or> (c=b) \<or> (c\<noteq>a \<and> c\<noteq>b)" by blast
  3091       moreover  --"case c=a"
  3091       moreover  --"case c=a"
  3092       { have "nSome(x) = nSome([(a,b)]\<bullet>y)" using a2 by simp
  3092       { have "nSome(x) = nSome([(a,b)]\<bullet>y)" using a2 by simp
  3093 	also have "\<dots> = nSome([(b,a)]\<bullet>y)" by (simp, rule pt3[OF pt], rule at_ds5[OF at])
  3093         also have "\<dots> = nSome([(b,a)]\<bullet>y)" by (simp, rule pt3[OF pt], rule at_ds5[OF at])
  3094 	finally have "nSome(x) = nSome([(b,a)]\<bullet>y)" by simp
  3094         finally have "nSome(x) = nSome([(b,a)]\<bullet>y)" by simp
  3095 	moreover
  3095         moreover
  3096 	assume "c=a"
  3096         assume "c=a"
  3097 	ultimately have "?LHS=?RHS" using a1 a3 by simp
  3097         ultimately have "?LHS=?RHS" using a1 a3 by simp
  3098       }
  3098       }
  3099       moreover  -- "case c=b"
  3099       moreover  -- "case c=b"
  3100       { have a4: "y=[(a,b)]\<bullet>x" using a2 by (simp only: pt_swap_bij[OF pt, OF at])
  3100       { have a4: "y=[(a,b)]\<bullet>x" using a2 by (simp only: pt_swap_bij[OF pt, OF at])
  3101 	hence "a\<sharp>([(a,b)]\<bullet>x)" using a3 by simp
  3101         hence "a\<sharp>([(a,b)]\<bullet>x)" using a3 by simp
  3102 	hence "b\<sharp>x" by (simp add: at_calc[OF at] pt_fresh_left[OF pt, OF at])
  3102         hence "b\<sharp>x" by (simp add: at_calc[OF at] pt_fresh_left[OF pt, OF at])
  3103 	moreover
  3103         moreover
  3104 	assume "c=b"
  3104         assume "c=b"
  3105 	ultimately have "?LHS=?RHS" using a1 a4 by simp
  3105         ultimately have "?LHS=?RHS" using a1 a4 by simp
  3106       }
  3106       }
  3107       moreover  -- "case c\<noteq>a \<and> c\<noteq>b"
  3107       moreover  -- "case c\<noteq>a \<and> c\<noteq>b"
  3108       { assume a5: "c\<noteq>a \<and> c\<noteq>b"
  3108       { assume a5: "c\<noteq>a \<and> c\<noteq>b"
  3109 	moreover 
  3109         moreover 
  3110 	have "c\<sharp>x = c\<sharp>y" using a2 a5 by (force simp add: at_calc[OF at] pt_fresh_left[OF pt, OF at])
  3110         have "c\<sharp>x = c\<sharp>y" using a2 a5 by (force simp add: at_calc[OF at] pt_fresh_left[OF pt, OF at])
  3111 	moreover 
  3111         moreover 
  3112 	have "c\<sharp>y \<longrightarrow> [(a,c)]\<bullet>x = [(b,c)]\<bullet>y" 
  3112         have "c\<sharp>y \<longrightarrow> [(a,c)]\<bullet>x = [(b,c)]\<bullet>y" 
  3113 	proof (intro strip)
  3113         proof (intro strip)
  3114 	  assume a6: "c\<sharp>y"
  3114           assume a6: "c\<sharp>y"
  3115 	  have "[(a,c),(b,c),(a,c)] \<triangleq> [(a,b)]" using a1 a5 by (force intro: at_ds3[OF at])
  3115           have "[(a,c),(b,c),(a,c)] \<triangleq> [(a,b)]" using a1 a5 by (force intro: at_ds3[OF at])
  3116 	  hence "[(a,c)]\<bullet>([(b,c)]\<bullet>([(a,c)]\<bullet>y)) = [(a,b)]\<bullet>y" 
  3116           hence "[(a,c)]\<bullet>([(b,c)]\<bullet>([(a,c)]\<bullet>y)) = [(a,b)]\<bullet>y" 
  3117 	    by (simp add: pt2[OF pt, symmetric] pt3[OF pt])
  3117             by (simp add: pt2[OF pt, symmetric] pt3[OF pt])
  3118  	  hence "[(a,c)]\<bullet>([(b,c)]\<bullet>y) = [(a,b)]\<bullet>y" using a3 a6 
  3118           hence "[(a,c)]\<bullet>([(b,c)]\<bullet>y) = [(a,b)]\<bullet>y" using a3 a6 
  3119 	    by (simp add: pt_fresh_fresh[OF pt, OF at])
  3119             by (simp add: pt_fresh_fresh[OF pt, OF at])
  3120 	  hence "[(a,c)]\<bullet>([(b,c)]\<bullet>y) = x" using a2 by simp
  3120           hence "[(a,c)]\<bullet>([(b,c)]\<bullet>y) = x" using a2 by simp
  3121 	  hence "[(b,c)]\<bullet>y = [(a,c)]\<bullet>x" by (drule_tac pt_bij1[OF pt, OF at], simp)
  3121           hence "[(b,c)]\<bullet>y = [(a,c)]\<bullet>x" by (drule_tac pt_bij1[OF pt, OF at], simp)
  3122 	  thus "[(a,c)]\<bullet>x = [(b,c)]\<bullet>y" by simp
  3122           thus "[(a,c)]\<bullet>x = [(b,c)]\<bullet>y" by simp
  3123 	qed
  3123         qed
  3124 	ultimately have "?LHS=?RHS" by simp
  3124         ultimately have "?LHS=?RHS" by simp
  3125       }
  3125       }
  3126       ultimately show "?LHS = ?RHS" by blast
  3126       ultimately show "?LHS = ?RHS" by blast
  3127     qed
  3127     qed
  3128   qed
  3128   qed
  3129 qed
  3129 qed
  3130 	
  3130         
  3131 (* alpha equivalence *)
  3131 (* alpha equivalence *)
  3132 lemma abs_fun_eq: 
  3132 lemma abs_fun_eq: 
  3133   fixes x  :: "'a"
  3133   fixes x  :: "'a"
  3134   and   y  :: "'a"
  3134   and   y  :: "'a"
  3135   and   a  :: "'x"
  3135   and   a  :: "'x"
  3276   shows "b\<sharp>([a].x)"
  3276   shows "b\<sharp>([a].x)"
  3277   proof -
  3277   proof -
  3278     have "\<exists>c::'x. c\<sharp>(b,a,x,[a].x)" 
  3278     have "\<exists>c::'x. c\<sharp>(b,a,x,[a].x)" 
  3279     proof (rule at_exists_fresh'[OF at], auto simp add: supp_prod at_supp[OF at] f)
  3279     proof (rule at_exists_fresh'[OF at], auto simp add: supp_prod at_supp[OF at] f)
  3280       show "finite ((supp ([a].x))::'x set)" using f
  3280       show "finite ((supp ([a].x))::'x set)" using f
  3281 	by (simp add: abs_fun_finite_supp[OF pt, OF at])	
  3281         by (simp add: abs_fun_finite_supp[OF pt, OF at])        
  3282     qed
  3282     qed
  3283     then obtain c where fr1: "c\<noteq>b"
  3283     then obtain c where fr1: "c\<noteq>b"
  3284                   and   fr2: "c\<noteq>a"
  3284                   and   fr2: "c\<noteq>a"
  3285                   and   fr3: "c\<sharp>x"
  3285                   and   fr3: "c\<sharp>x"
  3286                   and   fr4: "c\<sharp>([a].x)"
  3286                   and   fr4: "c\<sharp>([a].x)"
  3307   shows "b\<sharp>x"
  3307   shows "b\<sharp>x"
  3308 proof -
  3308 proof -
  3309   have "\<exists>c::'x. c\<sharp>(b,a,x,[a].x)"
  3309   have "\<exists>c::'x. c\<sharp>(b,a,x,[a].x)"
  3310   proof (rule at_exists_fresh'[OF at], auto simp add: supp_prod at_supp[OF at] f)
  3310   proof (rule at_exists_fresh'[OF at], auto simp add: supp_prod at_supp[OF at] f)
  3311     show "finite ((supp ([a].x))::'x set)" using f
  3311     show "finite ((supp ([a].x))::'x set)" using f
  3312       by (simp add: abs_fun_finite_supp[OF pt, OF at])	
  3312       by (simp add: abs_fun_finite_supp[OF pt, OF at])  
  3313   qed
  3313   qed
  3314   then obtain c where fr1: "b\<noteq>c"
  3314   then obtain c where fr1: "b\<noteq>c"
  3315                 and   fr2: "c\<noteq>a"
  3315                 and   fr2: "c\<noteq>a"
  3316                 and   fr3: "c\<sharp>x"
  3316                 and   fr3: "c\<sharp>x"
  3317                 and   fr4: "c\<sharp>([a].x)" by (force simp add: fresh_prod at_fresh[OF at])
  3317                 and   fr4: "c\<sharp>([a].x)" by (force simp add: fresh_prod at_fresh[OF at])