src/HOL/Nominal/Examples/Class2.thy
changeset 63167 0909deb8059b
parent 60585 48fdff264eb2
child 80609 4b5d3d0abb69
equal deleted inserted replaced
63166:143f58bb34f9 63167:0909deb8059b
     1 theory Class2
     1 theory Class2
     2 imports Class1
     2 imports Class1
     3 begin
     3 begin
     4 
     4 
     5 text {* Reduction *}
     5 text \<open>Reduction\<close>
     6 
     6 
     7 lemma fin_not_Cut:
     7 lemma fin_not_Cut:
     8   assumes a: "fin M x"
     8   assumes a: "fin M x"
     9   shows "\<not>(\<exists>a M' x N'. M = Cut <a>.M' (x).N')"
     9   shows "\<not>(\<exists>a M' x N'. M = Cut <a>.M' (x).N')"
    10 using a
    10 using a
  1819 apply(blast)
  1819 apply(blast)
  1820 apply(drule_tac y="y" and c="c" and P="P" in a_redu_subst2)
  1820 apply(drule_tac y="y" and c="c" and P="P" in a_redu_subst2)
  1821 apply(auto)
  1821 apply(auto)
  1822 done
  1822 done
  1823 
  1823 
  1824 text {* Candidates and SN *}
  1824 text \<open>Candidates and SN\<close>
  1825 
  1825 
  1826 text {* SNa *}
  1826 text \<open>SNa\<close>
  1827 
  1827 
  1828 inductive 
  1828 inductive 
  1829   SNa :: "trm \<Rightarrow> bool"
  1829   SNa :: "trm \<Rightarrow> bool"
  1830 where
  1830 where
  1831   SNaI: "(\<And>M'. M \<longrightarrow>\<^sub>a M' \<Longrightarrow> SNa M') \<Longrightarrow> SNa M"
  1831   SNaI: "(\<And>M'. M \<longrightarrow>\<^sub>a M' \<Longrightarrow> SNa M') \<Longrightarrow> SNa M"
  2089 apply(rotate_tac 1)
  2089 apply(rotate_tac 1)
  2090 apply(drule_tac x="(rev pi2)\<bullet>M'" in meta_spec)
  2090 apply(drule_tac x="(rev pi2)\<bullet>M'" in meta_spec)
  2091 apply(perm_simp)
  2091 apply(perm_simp)
  2092 done
  2092 done
  2093 
  2093 
  2094 text {* set operators *}
  2094 text \<open>set operators\<close>
  2095 
  2095 
  2096 definition AXIOMSn :: "ty \<Rightarrow> ntrm set" where
  2096 definition AXIOMSn :: "ty \<Rightarrow> ntrm set" where
  2097   "AXIOMSn B \<equiv> { (x):(Ax y b) | x y b. True }"
  2097   "AXIOMSn B \<equiv> { (x):(Ax y b) | x y b. True }"
  2098 
  2098 
  2099 definition AXIOMSc::"ty \<Rightarrow> ctrm set" where
  2099 definition AXIOMSc::"ty \<Rightarrow> ctrm set" where
  2871 termination
  2871 termination
  2872 apply(relation "measure (case_sum (size\<circ>fst) (size\<circ>fst))")
  2872 apply(relation "measure (case_sum (size\<circ>fst) (size\<circ>fst))")
  2873 apply(simp_all)
  2873 apply(simp_all)
  2874 done
  2874 done
  2875 
  2875 
  2876 text {* Candidates *}
  2876 text \<open>Candidates\<close>
  2877 
  2877 
  2878 lemma test1:
  2878 lemma test1:
  2879   shows "x\<in>(X\<union>Y) = (x\<in>X \<or> x\<in>Y)"
  2879   shows "x\<in>(X\<union>Y) = (x\<in>X \<or> x\<in>Y)"
  2880 by blast
  2880 by blast
  2881 
  2881 
  3445       by (simp only: NEGc_simps union_eqvt AXIOMS_eqvt_coname BINDING_eqvt_coname 
  3445       by (simp only: NEGc_simps union_eqvt AXIOMS_eqvt_coname BINDING_eqvt_coname 
  3446                      IMPRIGHT_eqvt_coname IMPLEFT_eqvt_coname ih1 ih2 ih3 ih4 g)
  3446                      IMPRIGHT_eqvt_coname IMPLEFT_eqvt_coname ih1 ih2 ih3 ih4 g)
  3447   }
  3447   }
  3448 qed
  3448 qed
  3449 
  3449 
  3450 text {* Elimination rules for the set-operators *}
  3450 text \<open>Elimination rules for the set-operators\<close>
  3451 
  3451 
  3452 lemma BINDINGc_elim:
  3452 lemma BINDINGc_elim:
  3453   assumes a: "<a>:M \<in> BINDINGc B (\<parallel>(B)\<parallel>)"
  3453   assumes a: "<a>:M \<in> BINDINGc B (\<parallel>(B)\<parallel>)"
  3454   shows "\<forall>x P. ((x):P)\<in>(\<parallel>(B)\<parallel>) \<longrightarrow> SNa (M{a:=(x).P})"
  3454   shows "\<forall>x P. ((x):P)\<in>(\<parallel>(B)\<parallel>) \<longrightarrow> SNa (M{a:=(x).P})"
  3455 using a
  3455 using a
  5176 apply(simp add: CAND_eqvt_name CAND_eqvt_coname)
  5176 apply(simp add: CAND_eqvt_name CAND_eqvt_coname)
  5177 apply(drule_tac pi="[(x,ca)]" and X="\<parallel><ty2>\<parallel>" in pt_set_bij2[OF pt_name_inst, OF at_name_inst])
  5177 apply(drule_tac pi="[(x,ca)]" and X="\<parallel><ty2>\<parallel>" in pt_set_bij2[OF pt_name_inst, OF at_name_inst])
  5178 apply(perm_simp add: CAND_eqvt_name CAND_eqvt_coname csubst_eqvt nsubst_eqvt)
  5178 apply(perm_simp add: CAND_eqvt_name CAND_eqvt_coname csubst_eqvt nsubst_eqvt)
  5179 done
  5179 done
  5180 
  5180 
  5181 text {* Main lemma 1 *}
  5181 text \<open>Main lemma 1\<close>
  5182 
  5182 
  5183 lemma AXIOMS_imply_SNa:
  5183 lemma AXIOMS_imply_SNa:
  5184   shows "<a>:M \<in> AXIOMSc B \<Longrightarrow> SNa M"
  5184   shows "<a>:M \<in> AXIOMSc B \<Longrightarrow> SNa M"
  5185   and   "(x):M \<in> AXIOMSn B \<Longrightarrow> SNa M"
  5185   and   "(x):M \<in> AXIOMSn B \<Longrightarrow> SNa M"
  5186 apply -
  5186 apply -
  5482     }
  5482     }
  5483     ultimately show "SNa M" by blast
  5483     ultimately show "SNa M" by blast
  5484   }
  5484   }
  5485 qed 
  5485 qed 
  5486 
  5486 
  5487 text {* Main lemma 2 *}
  5487 text \<open>Main lemma 2\<close>
  5488 
  5488 
  5489 lemma AXIOMS_preserved:
  5489 lemma AXIOMS_preserved:
  5490   shows "<a>:M \<in> AXIOMSc B \<Longrightarrow> M \<longrightarrow>\<^sub>a* M' \<Longrightarrow> <a>:M' \<in> AXIOMSc B"
  5490   shows "<a>:M \<in> AXIOMSc B \<Longrightarrow> M \<longrightarrow>\<^sub>a* M' \<Longrightarrow> <a>:M' \<in> AXIOMSc B"
  5491   and   "(x):M \<in> AXIOMSn B \<Longrightarrow> M \<longrightarrow>\<^sub>a* M' \<Longrightarrow> (x):M' \<in> AXIOMSn B"
  5491   and   "(x):M \<in> AXIOMSn B \<Longrightarrow> M \<longrightarrow>\<^sub>a* M' \<Longrightarrow> (x):M' \<in> AXIOMSn B"
  5492   apply(simp_all add: AXIOMSc_def AXIOMSn_def)
  5492   apply(simp_all add: AXIOMSc_def AXIOMSn_def)