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]) |