Nominal/Test.thy
changeset 1515 76fa21f27f22
parent 1510 be911e869fde
child 1517 62d6f7acc110
equal deleted inserted replaced
1514:b52b72676e20 1515:76fa21f27f22
    20 | Ap "lm" "lm"
    20 | Ap "lm" "lm"
    21 | Lm x::"name" l::"lm"  bind x in l
    21 | Lm x::"name" l::"lm"  bind x in l
    22 
    22 
    23 lemma finite_fv:
    23 lemma finite_fv:
    24   shows "finite (fv_lm t)"
    24   shows "finite (fv_lm t)"
    25 apply(induct t rule: lm_induct)
    25 apply(induct t rule: lm.induct)
    26 apply(simp_all)
    26 apply(simp_all)
    27 done
    27 done
    28 
    28 
    29 lemma supp_fn:
    29 lemma supp_fn:
    30   shows "supp t = fv_lm t"
    30   shows "supp t = fv_lm t"
    31 apply(induct t rule: lm_induct)
    31 apply(induct t rule: lm.induct)
    32 apply(simp_all)
    32 apply(simp_all)
    33 apply(simp only: supp_def)
    33 apply(simp only: supp_def)
    34 apply(simp only: lm_perm)
    34 apply(simp only: lm.perm)
    35 apply(simp only: lm_eq_iff)
    35 apply(simp only: lm.eq_iff)
    36 apply(simp only: supp_def[symmetric])
    36 apply(simp only: supp_def[symmetric])
    37 apply(simp only: supp_at_base)
    37 apply(simp only: supp_at_base)
    38 apply(simp (no_asm) only: supp_def)
    38 apply(simp (no_asm) only: supp_def)
    39 apply(simp only: lm_perm)
    39 apply(simp only: lm.perm)
    40 apply(simp only: lm_eq_iff)
    40 apply(simp only: lm.eq_iff)
    41 apply(simp only: de_Morgan_conj)
    41 apply(simp only: de_Morgan_conj)
    42 apply(simp only: Collect_disj_eq)
    42 apply(simp only: Collect_disj_eq)
    43 apply(simp only: infinite_Un)
    43 apply(simp only: infinite_Un)
    44 apply(simp only: Collect_disj_eq)
    44 apply(simp only: Collect_disj_eq)
    45 apply(simp only: supp_def[symmetric])
    45 apply(simp only: supp_def[symmetric])
    46 apply(rule_tac t="supp (Lm name lm)" and s="supp (Abs {atom name} lm)" in subst)
    46 apply(rule_tac t="supp (Lm name lm)" and s="supp (Abs {atom name} lm)" in subst)
    47 apply(simp (no_asm) only: supp_def)
    47 apply(simp (no_asm) only: supp_def)
    48 apply(simp only: lm_perm)
    48 apply(simp only: lm.perm)
    49 apply(simp only: permute_ABS)
    49 apply(simp only: permute_ABS)
    50 apply(simp only: lm_eq_iff)
    50 apply(simp only: lm.eq_iff)
    51 apply(simp only: Abs_eq_iff)
    51 apply(simp only: Abs_eq_iff)
    52 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
    52 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
    53 apply(simp only: alpha_gen)
    53 apply(simp only: alpha_gen)
    54 apply(simp only: supp_eqvt[symmetric])
    54 apply(simp only: supp_eqvt[symmetric])
    55 apply(simp only: eqvts)
    55 apply(simp only: eqvts)
    56 apply(simp only: supp_Abs)
    56 apply(simp only: supp_Abs)
    57 done
    57 done
    58 
    58 
    59 lemmas supp_fn' = lm_fv[simplified supp_fn[symmetric]]
    59 lemmas supp_fn' = lm.fv[simplified supp_fn[symmetric]]
    60 
    60 
    61 lemma
    61 lemma
    62   fixes c::"'a::fs"
    62   fixes c::"'a::fs"
    63   assumes a1: "\<And>name c. P c (Vr name)"
    63   assumes a1: "\<And>name c. P c (Vr name)"
    64   and     a2: "\<And>lm1 lm2 c. \<lbrakk>\<And>d. P d lm1; \<And>d. P d lm2\<rbrakk> \<Longrightarrow> P c (Ap lm1 lm2)"
    64   and     a2: "\<And>lm1 lm2 c. \<lbrakk>\<And>d. P d lm1; \<And>d. P d lm2\<rbrakk> \<Longrightarrow> P c (Ap lm1 lm2)"
    65   and     a3: "\<And>name lm c. \<lbrakk>\<And>d. P d lm\<rbrakk> \<Longrightarrow> P c (Lm name lm)"
    65   and     a3: "\<And>name lm c. \<lbrakk>\<And>d. P d lm\<rbrakk> \<Longrightarrow> P c (Lm name lm)"
    66   shows "P c lm"
    66   shows "P c lm"
    67 proof -
    67 proof -
    68   have "\<And>p. P c (p \<bullet> lm)"
    68   have "\<And>p. P c (p \<bullet> lm)"
    69     apply(induct lm arbitrary: c rule: lm_induct)
    69     apply(induct lm arbitrary: c rule: lm.induct)
    70     apply(simp only: lm_perm)
    70     apply(simp only: lm.perm)
    71     apply(rule a1)
    71     apply(rule a1)
    72     apply(simp only: lm_perm)
    72     apply(simp only: lm.perm)
    73     apply(rule a2)
    73     apply(rule a2)
    74     apply(blast)[1]
    74     apply(blast)[1]
    75     apply(assumption)
    75     apply(assumption)
    76     apply(subgoal_tac "\<exists>new::name. (atom new) \<sharp> (c, Lm (p \<bullet> name) (p \<bullet> lm))")
    76     apply(subgoal_tac "\<exists>new::name. (atom new) \<sharp> (c, Lm (p \<bullet> name) (p \<bullet> lm))")
    77     apply(erule exE)
    77     apply(erule exE)
    78     apply(rule_tac t="p \<bullet> Lm name lm" and 
    78     apply(rule_tac t="p \<bullet> Lm name lm" and 
    79                    s="(((p \<bullet> name) \<leftrightarrow> new) + p) \<bullet> Lm name lm" in subst)
    79                    s="(((p \<bullet> name) \<leftrightarrow> new) + p) \<bullet> Lm name lm" in subst)
    80     apply(simp del: lm_perm)
    80     apply(simp del: lm.perm)
    81     apply(subst lm_perm)
    81     apply(subst lm.perm)
    82     apply(subst (2) lm_perm)
    82     apply(subst (2) lm.perm)
    83     apply(rule flip_fresh_fresh)
    83     apply(rule flip_fresh_fresh)
    84     apply(simp add: fresh_def)
    84     apply(simp add: fresh_def)
    85     apply(simp only: supp_fn')
    85     apply(simp only: supp_fn')
    86     apply(simp)
    86     apply(simp)
    87     apply(simp add: fresh_Pair)
    87     apply(simp add: fresh_Pair)
   109 binder
   109 binder
   110   bi::"bp \<Rightarrow> atom set"
   110   bi::"bp \<Rightarrow> atom set"
   111 where
   111 where
   112   "bi (BP x t) = {atom x}"
   112   "bi (BP x t) = {atom x}"
   113 
   113 
   114 thm lam_bp_fv
   114 thm lam_bp.fv
   115 thm lam_bp_eq_iff
   115 thm lam_bp.eq_iff
   116 thm lam_bp_bn
   116 thm lam_bp.bn
   117 thm lam_bp_perm
   117 thm lam_bp.perm
   118 thm lam_bp_induct
   118 thm lam_bp.induct
   119 thm lam_bp_inducts
   119 thm lam_bp.inducts
   120 thm lam_bp_distinct
   120 thm lam_bp.distinct
   121 ML {* Sign.of_sort @{theory} (@{typ lam}, @{sort fs}) *}
   121 ML {* Sign.of_sort @{theory} (@{typ lam}, @{sort fs}) *}
   122 
   122 
   123 term "supp (x :: lam)"
   123 term "supp (x :: lam)"
   124 
   124 
   125 lemma bi_eqvt:
   125 lemma bi_eqvt:
   127   by (rule eqvts)
   127   by (rule eqvts)
   128 
   128 
   129 lemma supp_fv:
   129 lemma supp_fv:
   130   shows "supp t = fv_lam t" 
   130   shows "supp t = fv_lam t" 
   131   and "supp bp = fv_bp bp \<and> fv_bi bp = {a. infinite {b. \<not>alpha_bi ((a \<rightleftharpoons> b) \<bullet> bp) bp}}"
   131   and "supp bp = fv_bp bp \<and> fv_bi bp = {a. infinite {b. \<not>alpha_bi ((a \<rightleftharpoons> b) \<bullet> bp) bp}}"
   132 apply(induct t and bp rule: lam_bp_inducts)
   132 apply(induct t and bp rule: lam_bp.inducts)
   133 apply(simp_all)
   133 apply(simp_all)
   134 (* VAR case *)
   134 (* VAR case *)
   135 apply(simp only: supp_def)
   135 apply(simp only: supp_def)
   136 apply(simp only: lam_bp_perm)
   136 apply(simp only: lam_bp.perm)
   137 apply(simp only: lam_bp_eq_iff)
   137 apply(simp only: lam_bp.eq_iff)
   138 apply(simp only: supp_def[symmetric])
   138 apply(simp only: supp_def[symmetric])
   139 apply(simp only: supp_at_base)
   139 apply(simp only: supp_at_base)
   140 (* APP case *)
   140 (* APP case *)
   141 apply(simp only: supp_def)
   141 apply(simp only: supp_def)
   142 apply(simp only: lam_bp_perm)
   142 apply(simp only: lam_bp.perm)
   143 apply(simp only: lam_bp_eq_iff)
   143 apply(simp only: lam_bp.eq_iff)
   144 apply(simp only: de_Morgan_conj)
   144 apply(simp only: de_Morgan_conj)
   145 apply(simp only: Collect_disj_eq)
   145 apply(simp only: Collect_disj_eq)
   146 apply(simp only: infinite_Un)
   146 apply(simp only: infinite_Un)
   147 apply(simp only: Collect_disj_eq)
   147 apply(simp only: Collect_disj_eq)
   148 (* LAM case *)
   148 (* LAM case *)
   149 apply(rule_tac t="supp (LAM name lam)" and s="supp (Abs {atom name} lam)" in subst)
   149 apply(rule_tac t="supp (LAM name lam)" and s="supp (Abs {atom name} lam)" in subst)
   150 apply(simp (no_asm) only: supp_def)
   150 apply(simp (no_asm) only: supp_def)
   151 apply(simp only: lam_bp_perm)
   151 apply(simp only: lam_bp.perm)
   152 apply(simp only: permute_ABS)
   152 apply(simp only: permute_ABS)
   153 apply(simp only: lam_bp_eq_iff)
   153 apply(simp only: lam_bp.eq_iff)
   154 apply(simp only: Abs_eq_iff)
   154 apply(simp only: Abs_eq_iff)
   155 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   155 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   156 apply(simp only: alpha_gen)
   156 apply(simp only: alpha_gen)
   157 apply(simp only: supp_eqvt[symmetric])
   157 apply(simp only: supp_eqvt[symmetric])
   158 apply(simp only: eqvts)
   158 apply(simp only: eqvts)
   159 apply(simp only: supp_Abs)
   159 apply(simp only: supp_Abs)
   160 (* LET case *)
   160 (* LET case *)
   161 apply(rule_tac t="supp (LET bp lam)" and s="supp (Abs (bi bp) lam) \<union> fv_bi bp" in subst)
   161 apply(rule_tac t="supp (LET bp lam)" and s="supp (Abs (bi bp) lam) \<union> fv_bi bp" in subst)
   162 apply(simp (no_asm) only: supp_def)
   162 apply(simp (no_asm) only: supp_def)
   163 apply(simp only: lam_bp_perm)
   163 apply(simp only: lam_bp.perm)
   164 apply(simp only: permute_ABS)
   164 apply(simp only: permute_ABS)
   165 apply(simp only: lam_bp_eq_iff)
   165 apply(simp only: lam_bp.eq_iff)
   166 apply(simp only: eqvts)
   166 apply(simp only: eqvts)
   167 apply(simp only: Abs_eq_iff)
   167 apply(simp only: Abs_eq_iff)
   168 apply(simp only: ex_simps)
   168 apply(simp only: ex_simps)
   169 apply(simp only: de_Morgan_conj)
   169 apply(simp only: de_Morgan_conj)
   170 apply(simp only: Collect_disj_eq)
   170 apply(simp only: Collect_disj_eq)
   176 apply(blast)
   176 apply(blast)
   177 apply(simp add: supp_Abs)
   177 apply(simp add: supp_Abs)
   178 apply(blast)
   178 apply(blast)
   179 (* BP case *)
   179 (* BP case *)
   180 apply(simp only: supp_def)
   180 apply(simp only: supp_def)
   181 apply(simp only: lam_bp_perm)
   181 apply(simp only: lam_bp.perm)
   182 apply(simp only: lam_bp_eq_iff)
   182 apply(simp only: lam_bp.eq_iff)
   183 apply(simp only: de_Morgan_conj)
   183 apply(simp only: de_Morgan_conj)
   184 apply(simp only: Collect_disj_eq)
   184 apply(simp only: Collect_disj_eq)
   185 apply(simp only: infinite_Un)
   185 apply(simp only: infinite_Un)
   186 apply(simp only: Collect_disj_eq)
   186 apply(simp only: Collect_disj_eq)
   187 apply(simp only: supp_def[symmetric])
   187 apply(simp only: supp_def[symmetric])
   188 apply(simp only: supp_at_base)
   188 apply(simp only: supp_at_base)
   189 apply(simp)
   189 apply(simp)
   190 done
   190 done
   191 
   191 
   192 thm lam_bp_fv[simplified supp_fv(1)[symmetric] supp_fv(2)[THEN conjunct1, symmetric]]
   192 thm lam_bp.fv[simplified supp_fv(1)[symmetric] supp_fv(2)[THEN conjunct1, symmetric]]
   193 
   193 
   194 ML {* val _ = recursive := true *}
   194 ML {* val _ = recursive := true *}
   195 
   195 
   196 nominal_datatype lam' =
   196 nominal_datatype lam' =
   197   VAR' "name"
   197   VAR' "name"
   203 binder
   203 binder
   204   bi'::"bp' \<Rightarrow> atom set"
   204   bi'::"bp' \<Rightarrow> atom set"
   205 where
   205 where
   206   "bi' (BP' x t) = {atom x}"
   206   "bi' (BP' x t) = {atom x}"
   207 
   207 
   208 thm lam'_bp'_fv
   208 thm lam'_bp'.fv
   209 thm lam'_bp'_eq_iff[no_vars]
   209 thm lam'_bp'.eq_iff[no_vars]
   210 thm lam'_bp'_bn
   210 thm lam'_bp'.bn
   211 thm lam'_bp'_perm
   211 thm lam'_bp'.perm
   212 thm lam'_bp'_induct
   212 thm lam'_bp'.induct
   213 thm lam'_bp'_inducts
   213 thm lam'_bp'.inducts
   214 thm lam'_bp'_distinct
   214 thm lam'_bp'.distinct
   215 ML {* Sign.of_sort @{theory} (@{typ lam'}, @{sort fs}) *}
   215 ML {* Sign.of_sort @{theory} (@{typ lam'}, @{sort fs}) *}
   216 
   216 
   217 lemma supp_fv':
   217 lemma supp_fv':
   218   shows "supp t = fv_lam' t" 
   218   shows "supp t = fv_lam' t" 
   219   and "supp bp = fv_bp' bp"
   219   and "supp bp = fv_bp' bp"
   220 apply(induct t and bp rule: lam'_bp'_inducts)
   220 apply(induct t and bp rule: lam'_bp'.inducts)
   221 apply(simp_all)
   221 apply(simp_all)
   222 (* VAR case *)
   222 (* VAR case *)
   223 apply(simp only: supp_def)
   223 apply(simp only: supp_def)
   224 apply(simp only: lam'_bp'_perm)
   224 apply(simp only: lam'_bp'.perm)
   225 apply(simp only: lam'_bp'_eq_iff)
   225 apply(simp only: lam'_bp'.eq_iff)
   226 apply(simp only: supp_def[symmetric])
   226 apply(simp only: supp_def[symmetric])
   227 apply(simp only: supp_at_base)
   227 apply(simp only: supp_at_base)
   228 (* APP case *)
   228 (* APP case *)
   229 apply(simp only: supp_def)
   229 apply(simp only: supp_def)
   230 apply(simp only: lam'_bp'_perm)
   230 apply(simp only: lam'_bp'.perm)
   231 apply(simp only: lam'_bp'_eq_iff)
   231 apply(simp only: lam'_bp'.eq_iff)
   232 apply(simp only: de_Morgan_conj)
   232 apply(simp only: de_Morgan_conj)
   233 apply(simp only: Collect_disj_eq)
   233 apply(simp only: Collect_disj_eq)
   234 apply(simp only: infinite_Un)
   234 apply(simp only: infinite_Un)
   235 apply(simp only: Collect_disj_eq)
   235 apply(simp only: Collect_disj_eq)
   236 (* LAM case *)
   236 (* LAM case *)
   237 apply(rule_tac t="supp (LAM' name lam')" and s="supp (Abs {atom name} lam')" in subst)
   237 apply(rule_tac t="supp (LAM' name lam')" and s="supp (Abs {atom name} lam')" in subst)
   238 apply(simp (no_asm) only: supp_def)
   238 apply(simp (no_asm) only: supp_def)
   239 apply(simp only: lam'_bp'_perm)
   239 apply(simp only: lam'_bp'.perm)
   240 apply(simp only: permute_ABS)
   240 apply(simp only: permute_ABS)
   241 apply(simp only: lam'_bp'_eq_iff)
   241 apply(simp only: lam'_bp'.eq_iff)
   242 apply(simp only: Abs_eq_iff)
   242 apply(simp only: Abs_eq_iff)
   243 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   243 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   244 apply(simp only: alpha_gen)
   244 apply(simp only: alpha_gen)
   245 apply(simp only: supp_eqvt[symmetric])
   245 apply(simp only: supp_eqvt[symmetric])
   246 apply(simp only: eqvts)
   246 apply(simp only: eqvts)
   247 apply(simp only: supp_Abs)
   247 apply(simp only: supp_Abs)
   248 (* LET case *)
   248 (* LET case *)
   249 apply(rule_tac t="supp (LET' bp' lam')" and 
   249 apply(rule_tac t="supp (LET' bp' lam')" and 
   250                s="supp (Abs (bi' bp') (bp', lam'))" in subst)
   250                s="supp (Abs (bi' bp') (bp', lam'))" in subst)
   251 apply(simp (no_asm) only: supp_def)
   251 apply(simp (no_asm) only: supp_def)
   252 apply(simp only: lam'_bp'_perm)
   252 apply(simp only: lam'_bp'.perm)
   253 apply(simp only: permute_ABS)
   253 apply(simp only: permute_ABS)
   254 apply(simp only: lam'_bp'_eq_iff)
   254 apply(simp only: lam'_bp'.eq_iff)
   255 apply(simp only: Abs_eq_iff)
   255 apply(simp only: Abs_eq_iff)
   256 apply(simp only: alpha_gen)
   256 apply(simp only: alpha_gen)
   257 apply(simp only: eqvts split_def fst_conv snd_conv)
   257 apply(simp only: eqvts split_def fst_conv snd_conv)
   258 apply(simp only: eqvts[symmetric] supp_Pair)
   258 apply(simp only: eqvts[symmetric] supp_Pair)
   259 apply(simp only: eqvts Pair_eq)
   259 apply(simp only: eqvts Pair_eq)
   260 apply(simp add: supp_Abs supp_Pair)
   260 apply(simp add: supp_Abs supp_Pair)
   261 apply blast
   261 apply blast
   262 apply(simp only: supp_def)
   262 apply(simp only: supp_def)
   263 apply(simp only: lam'_bp'_perm)
   263 apply(simp only: lam'_bp'.perm)
   264 apply(simp only: lam'_bp'_eq_iff)
   264 apply(simp only: lam'_bp'.eq_iff)
   265 apply(simp only: de_Morgan_conj)
   265 apply(simp only: de_Morgan_conj)
   266 apply(simp only: Collect_disj_eq)
   266 apply(simp only: Collect_disj_eq)
   267 apply(simp only: infinite_Un)
   267 apply(simp only: infinite_Un)
   268 apply(simp only: Collect_disj_eq)
   268 apply(simp only: Collect_disj_eq)
   269 apply(simp only: supp_def[symmetric])
   269 apply(simp only: supp_def[symmetric])
   270 apply(simp only: supp_at_base supp_atom)
   270 apply(simp only: supp_at_base supp_atom)
   271 apply simp
   271 apply simp
   272 done
   272 done
   273 
   273 
   274 thm lam'_bp'_fv[simplified supp_fv'[symmetric]]
   274 thm lam'_bp'.fv[simplified supp_fv'[symmetric]]
   275 
   275 
   276 
   276 
   277 text {* example 2 *}
   277 text {* example 2 *}
   278 
   278 
   279 ML {* val _ = recursive := false  *}
   279 ML {* val _ = recursive := false  *}
   291 where
   291 where
   292   "f PN = {}"
   292   "f PN = {}"
   293 | "f (PD x y) = {atom x, atom y}"
   293 | "f (PD x y) = {atom x, atom y}"
   294 | "f (PS x) = {atom x}"
   294 | "f (PS x) = {atom x}"
   295 
   295 
   296 thm trm'_pat'_fv
   296 thm trm'_pat'.fv
   297 thm trm'_pat'_eq_iff
   297 thm trm'_pat'.eq_iff
   298 thm trm'_pat'_bn
   298 thm trm'_pat'.bn
   299 thm trm'_pat'_perm
   299 thm trm'_pat'.perm
   300 thm trm'_pat'_induct
   300 thm trm'_pat'.induct
   301 thm trm'_pat'_distinct
   301 thm trm'_pat'.distinct
   302 
   302 
   303 lemma supp_fv_trm'_pat':
   303 lemma supp_fv_trm'_pat':
   304   shows "supp t = fv_trm' t" 
   304   shows "supp t = fv_trm' t" 
   305   and "supp bp = fv_pat' bp \<and> {a. infinite {b. \<not>alpha_f ((a \<rightleftharpoons> b) \<bullet> bp) bp}} = fv_f bp"
   305   and "supp bp = fv_pat' bp \<and> {a. infinite {b. \<not>alpha_f ((a \<rightleftharpoons> b) \<bullet> bp) bp}} = fv_f bp"
   306 apply(induct t and bp rule: trm'_pat'_inducts)
   306 apply(induct t and bp rule: trm'_pat'.inducts)
   307 apply(simp_all)
   307 apply(simp_all)
   308 (* VAR case *)
   308 (* VAR case *)
   309 apply(simp only: supp_def)
   309 apply(simp only: supp_def)
   310 apply(simp only: trm'_pat'_perm)
   310 apply(simp only: trm'_pat'.perm)
   311 apply(simp only: trm'_pat'_eq_iff)
   311 apply(simp only: trm'_pat'.eq_iff)
   312 apply(simp only: supp_def[symmetric])
   312 apply(simp only: supp_def[symmetric])
   313 apply(simp only: supp_at_base)
   313 apply(simp only: supp_at_base)
   314 (* APP case *)
   314 (* APP case *)
   315 apply(simp only: supp_def)
   315 apply(simp only: supp_def)
   316 apply(simp only: trm'_pat'_perm)
   316 apply(simp only: trm'_pat'.perm)
   317 apply(simp only: trm'_pat'_eq_iff)
   317 apply(simp only: trm'_pat'.eq_iff)
   318 apply(simp only: de_Morgan_conj)
   318 apply(simp only: de_Morgan_conj)
   319 apply(simp only: Collect_disj_eq)
   319 apply(simp only: Collect_disj_eq)
   320 apply(simp only: infinite_Un)
   320 apply(simp only: infinite_Un)
   321 apply(simp only: Collect_disj_eq)
   321 apply(simp only: Collect_disj_eq)
   322 (* LAM case *)
   322 (* LAM case *)
   323 apply(rule_tac t="supp (Lam name trm')" and s="supp (Abs {atom name} trm')" in subst)
   323 apply(rule_tac t="supp (Lam name trm')" and s="supp (Abs {atom name} trm')" in subst)
   324 apply(simp (no_asm) only: supp_def)
   324 apply(simp (no_asm) only: supp_def)
   325 apply(simp only: trm'_pat'_perm)
   325 apply(simp only: trm'_pat'.perm)
   326 apply(simp only: permute_ABS)
   326 apply(simp only: permute_ABS)
   327 apply(simp only: trm'_pat'_eq_iff)
   327 apply(simp only: trm'_pat'.eq_iff)
   328 apply(simp only: Abs_eq_iff)
   328 apply(simp only: Abs_eq_iff)
   329 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   329 apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
   330 apply(simp only: alpha_gen)
   330 apply(simp only: alpha_gen)
   331 apply(simp only: supp_eqvt[symmetric])
   331 apply(simp only: supp_eqvt[symmetric])
   332 apply(simp only: eqvts)
   332 apply(simp only: eqvts)
   333 apply(simp only: supp_Abs)
   333 apply(simp only: supp_Abs)
   334 (* LET case *)
   334 (* LET case *)
   335 apply(rule_tac t="supp (Let pat' trm'1 trm'2)" 
   335 apply(rule_tac t="supp (Let pat' trm'1 trm'2)" 
   336            and s="supp (Abs (f pat') trm'2) \<union> supp trm'1 \<union> fv_f pat'" in subst)
   336            and s="supp (Abs (f pat') trm'2) \<union> supp trm'1 \<union> fv_f pat'" in subst)
   337 apply(simp (no_asm) only: supp_def)
   337 apply(simp (no_asm) only: supp_def)
   338 apply(simp only: trm'_pat'_perm)
   338 apply(simp only: trm'_pat'.perm)
   339 apply(simp only: permute_ABS)
   339 apply(simp only: permute_ABS)
   340 apply(simp only: trm'_pat'_eq_iff)
   340 apply(simp only: trm'_pat'.eq_iff)
   341 apply(simp only: eqvts)
   341 apply(simp only: eqvts)
   342 apply(simp only: Abs_eq_iff)
   342 apply(simp only: Abs_eq_iff)
   343 apply(simp only: ex_simps)
   343 apply(simp only: ex_simps)
   344 apply(simp only: de_Morgan_conj)
   344 apply(simp only: de_Morgan_conj)
   345 apply(simp only: Collect_disj_eq)
   345 apply(simp only: Collect_disj_eq)
   351 apply(blast)
   351 apply(blast)
   352 apply(simp add: supp_Abs)
   352 apply(simp add: supp_Abs)
   353 apply(blast)
   353 apply(blast)
   354 (* PN case *)
   354 (* PN case *)
   355 apply(simp only: supp_def)
   355 apply(simp only: supp_def)
   356 apply(simp only: trm'_pat'_perm)
   356 apply(simp only: trm'_pat'.perm)
   357 apply(simp only: trm'_pat'_eq_iff)
   357 apply(simp only: trm'_pat'.eq_iff)
   358 apply(simp)
   358 apply(simp)
   359 (* PS case *)
   359 (* PS case *)
   360 apply(simp only: supp_def)
   360 apply(simp only: supp_def)
   361 apply(simp only: trm'_pat'_perm)
   361 apply(simp only: trm'_pat'.perm)
   362 apply(simp only: trm'_pat'_eq_iff)
   362 apply(simp only: trm'_pat'.eq_iff)
   363 apply(simp only: supp_def[symmetric])
   363 apply(simp only: supp_def[symmetric])
   364 apply(simp only: supp_at_base)
   364 apply(simp only: supp_at_base)
   365 apply(simp)
   365 apply(simp)
   366 (* PD case *)
   366 (* PD case *)
   367 apply(simp only: supp_def)
   367 apply(simp only: supp_def)
   368 apply(simp only: trm'_pat'_perm)
   368 apply(simp only: trm'_pat'.perm)
   369 apply(simp only: trm'_pat'_eq_iff)
   369 apply(simp only: trm'_pat'.eq_iff)
   370 apply(simp only: de_Morgan_conj)
   370 apply(simp only: de_Morgan_conj)
   371 apply(simp only: Collect_disj_eq)
   371 apply(simp only: Collect_disj_eq)
   372 apply(simp only: infinite_Un)
   372 apply(simp only: infinite_Un)
   373 apply(simp only: Collect_disj_eq)
   373 apply(simp only: Collect_disj_eq)
   374 apply(simp only: supp_def[symmetric])
   374 apply(simp only: supp_def[symmetric])
   375 apply(simp add: supp_at_base)
   375 apply(simp add: supp_at_base)
   376 done
   376 done
   377 
   377 
   378 thm trm'_pat'_fv[simplified supp_fv_trm'_pat'(1)[symmetric] supp_fv_trm'_pat'(2)[THEN conjunct1, symmetric]]
   378 thm trm'_pat'.fv[simplified supp_fv_trm'_pat'(1)[symmetric] supp_fv_trm'_pat'(2)[THEN conjunct1, symmetric]]
   379 
   379 
   380 nominal_datatype trm0 =
   380 nominal_datatype trm0 =
   381   Var0 "name"
   381   Var0 "name"
   382 | App0 "trm0" "trm0"
   382 | App0 "trm0" "trm0"
   383 | Lam0 x::"name" t::"trm0"          bind x in t
   383 | Lam0 x::"name" t::"trm0"          bind x in t
   391 where
   391 where
   392   "f0 PN0 = {}"
   392   "f0 PN0 = {}"
   393 | "f0 (PS0 x) = {atom x}"
   393 | "f0 (PS0 x) = {atom x}"
   394 | "f0 (PD0 p1 p2) = (f0 p1) \<union> (f0 p2)"
   394 | "f0 (PD0 p1 p2) = (f0 p1) \<union> (f0 p2)"
   395 
   395 
   396 thm trm0_pat0_fv
   396 thm trm0_pat0.fv
   397 thm trm0_pat0_eq_iff
   397 thm trm0_pat0.eq_iff
   398 thm trm0_pat0_bn
   398 thm trm0_pat0.bn
   399 thm trm0_pat0_perm
   399 thm trm0_pat0.perm
   400 thm trm0_pat0_induct
   400 thm trm0_pat0.induct
   401 thm trm0_pat0_distinct
   401 thm trm0_pat0.distinct
   402 
   402 
   403 text {* example type schemes *}
   403 text {* example type schemes *}
   404 
   404 
   405 nominal_datatype t =
   405 nominal_datatype t =
   406   VarTS "name"
   406   VarTS "name"
   407 | FunTS "t" "t"
   407 | FunTS "t" "t"
   408 and  tyS =
   408 and  tyS =
   409   All xs::"name set" ty::"t" bind xs in ty
   409   All xs::"name set" ty::"t" bind xs in ty
   410 
   410 
   411 thm t_tyS_fv
   411 thm t_tyS.fv
   412 thm t_tyS_eq_iff
   412 thm t_tyS.eq_iff
   413 thm t_tyS_bn
   413 thm t_tyS.bn
   414 thm t_tyS_perm
   414 thm t_tyS.perm
   415 thm t_tyS_induct
   415 thm t_tyS.induct
   416 thm t_tyS_distinct
   416 thm t_tyS.distinct
   417 
   417 
   418 ML {* Sign.of_sort @{theory} (@{typ t}, @{sort fs}) *}
   418 ML {* Sign.of_sort @{theory} (@{typ t}, @{sort fs}) *}
   419 ML {* Sign.of_sort @{theory} (@{typ tyS}, @{sort fs}) *}
   419 ML {* Sign.of_sort @{theory} (@{typ tyS}, @{sort fs}) *}
   420 
   420 
   421 lemma supports_subset:
   421 lemma supports_subset:
   429 lemma finite_fv_t_tyS:
   429 lemma finite_fv_t_tyS:
   430   fixes T::"t"
   430   fixes T::"t"
   431   and   S::"tyS"
   431   and   S::"tyS"
   432   shows "finite (fv_t T)" 
   432   shows "finite (fv_t T)" 
   433   and   "finite (fv_tyS S)"
   433   and   "finite (fv_tyS S)"
   434 apply(induct T and S rule: t_tyS_inducts)
   434 apply(induct T and S rule: t_tyS.inducts)
   435 apply(simp_all add: t_tyS_fv)
   435 apply(simp_all add: t_tyS.fv)
   436 done
   436 done
   437 
   437 
   438 lemma supp_fv_t_tyS:
   438 lemma supp_fv_t_tyS:
   439   shows "supp T = fv_t T" 
   439   shows "supp T = fv_t T" 
   440   and   "supp S = fv_tyS S"
   440   and   "supp S = fv_tyS S"
   441 apply(induct T and S rule: t_tyS_inducts)
   441 apply(induct T and S rule: t_tyS.inducts)
   442 apply(simp_all)
   442 apply(simp_all)
   443 (* VarTS case *)
   443 (* VarTS case *)
   444 apply(simp only: supp_def)
   444 apply(simp only: supp_def)
   445 apply(simp only: t_tyS_perm)
   445 apply(simp only: t_tyS.perm)
   446 apply(simp only: t_tyS_eq_iff)
   446 apply(simp only: t_tyS.eq_iff)
   447 apply(simp only: supp_def[symmetric])
   447 apply(simp only: supp_def[symmetric])
   448 apply(simp only: supp_at_base)
   448 apply(simp only: supp_at_base)
   449 (* FunTS case *)
   449 (* FunTS case *)
   450 apply(simp only: supp_def)
   450 apply(simp only: supp_def)
   451 apply(simp only: t_tyS_perm)
   451 apply(simp only: t_tyS.perm)
   452 apply(simp only: t_tyS_eq_iff)
   452 apply(simp only: t_tyS.eq_iff)
   453 apply(simp only: de_Morgan_conj)
   453 apply(simp only: de_Morgan_conj)
   454 apply(simp only: Collect_disj_eq)
   454 apply(simp only: Collect_disj_eq)
   455 apply(simp only: infinite_Un)
   455 apply(simp only: infinite_Un)
   456 apply(simp only: Collect_disj_eq)
   456 apply(simp only: Collect_disj_eq)
   457 (* All case *)
   457 (* All case *)
   458 apply(rule_tac t="supp (All fun t)" and s="supp (Abs (atom ` fun) t)" in subst)
   458 apply(rule_tac t="supp (All fun t)" and s="supp (Abs (atom ` fun) t)" in subst)
   459 apply(simp (no_asm) only: supp_def)
   459 apply(simp (no_asm) only: supp_def)
   460 apply(simp only: t_tyS_perm)
   460 apply(simp only: t_tyS.perm)
   461 apply(simp only: permute_ABS)
   461 apply(simp only: permute_ABS)
   462 apply(simp only: t_tyS_eq_iff)
   462 apply(simp only: t_tyS.eq_iff)
   463 apply(simp only: Abs_eq_iff)
   463 apply(simp only: Abs_eq_iff)
   464 apply(simp only: insert_eqvt atom_eqvt empty_eqvt image_eqvt atom_eqvt_raw)
   464 apply(simp only: insert_eqvt atom_eqvt empty_eqvt image_eqvt atom_eqvt_raw)
   465 apply(simp only: alpha_gen)
   465 apply(simp only: alpha_gen)
   466 apply(simp only: supp_eqvt[symmetric])
   466 apply(simp only: supp_eqvt[symmetric])
   467 apply(simp only: eqvts)
   467 apply(simp only: eqvts)
   487 where
   487 where
   488   "bv1 (BUnit1) = {}"
   488   "bv1 (BUnit1) = {}"
   489 | "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"
   489 | "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"
   490 | "bv1 (BV1 x) = {atom x}"
   490 | "bv1 (BV1 x) = {atom x}"
   491 
   491 
   492 thm trm1_bp1_fv
   492 thm trm1_bp1.fv
   493 thm trm1_bp1_eq_iff
   493 thm trm1_bp1.eq_iff
   494 thm trm1_bp1_bn
   494 thm trm1_bp1.bn
   495 thm trm1_bp1_perm
   495 thm trm1_bp1.perm
   496 thm trm1_bp1_induct
   496 thm trm1_bp1.induct
   497 thm trm1_bp1_distinct
   497 thm trm1_bp1.distinct
   498 
   498 
   499 text {* example 3 from Terms.thy *}
   499 text {* example 3 from Terms.thy *}
   500 
   500 
   501 nominal_datatype trm3 =
   501 nominal_datatype trm3 =
   502   Vr3 "name"
   502   Vr3 "name"
   510   bv3
   510   bv3
   511 where
   511 where
   512   "bv3 ANil = {}"
   512   "bv3 ANil = {}"
   513 | "bv3 (ACons x t as) = {atom x} \<union> (bv3 as)"
   513 | "bv3 (ACons x t as) = {atom x} \<union> (bv3 as)"
   514 
   514 
   515 thm trm3_rassigns3_fv
   515 thm trm3_rassigns3.fv
   516 thm trm3_rassigns3_eq_iff
   516 thm trm3_rassigns3.eq_iff
   517 thm trm3_rassigns3_bn
   517 thm trm3_rassigns3.bn
   518 thm trm3_rassigns3_perm
   518 thm trm3_rassigns3.perm
   519 thm trm3_rassigns3_induct
   519 thm trm3_rassigns3.induct
   520 thm trm3_rassigns3_distinct
   520 thm trm3_rassigns3.distinct
   521 
   521 
   522 (* example 5 from Terms.thy *)
   522 (* example 5 from Terms.thy *)
   523 
   523 
   524 nominal_datatype trm5 =
   524 nominal_datatype trm5 =
   525   Vr5 "name"
   525   Vr5 "name"
   532   bv5
   532   bv5
   533 where
   533 where
   534   "bv5 Lnil = {}"
   534   "bv5 Lnil = {}"
   535 | "bv5 (Lcons n t ltl) = {atom n} \<union> (bv5 ltl)"
   535 | "bv5 (Lcons n t ltl) = {atom n} \<union> (bv5 ltl)"
   536 
   536 
   537 thm trm5_lts_fv
   537 thm trm5_lts.fv
   538 thm trm5_lts_eq_iff
   538 thm trm5_lts.eq_iff
   539 thm trm5_lts_bn
   539 thm trm5_lts.bn
   540 thm trm5_lts_perm
   540 thm trm5_lts.perm
   541 thm trm5_lts_induct
   541 thm trm5_lts.induct
   542 thm trm5_lts_distinct
   542 thm trm5_lts.distinct
   543 
   543 
   544 (* example from my PHD *)
   544 (* example from my PHD *)
   545 
   545 
   546 atom_decl coname
   546 atom_decl coname
   547 
   547 
   552 |  AndL1 n::"name" t::"phd" "name"                              bind n in t
   552 |  AndL1 n::"name" t::"phd" "name"                              bind n in t
   553 |  AndL2 n::"name" t::"phd" "name"                              bind n in t
   553 |  AndL2 n::"name" t::"phd" "name"                              bind n in t
   554 |  ImpL c::"coname" t1::"phd" n::"name" t2::"phd" "name"        bind c in t1, bind n in t2
   554 |  ImpL c::"coname" t1::"phd" n::"name" t2::"phd" "name"        bind c in t1, bind n in t2
   555 |  ImpR c::"coname" n::"name" t::"phd" "coname"                 bind n in t, bind c in t
   555 |  ImpR c::"coname" n::"name" t::"phd" "coname"                 bind n in t, bind c in t
   556 
   556 
   557 thm phd_fv
   557 thm phd.fv
   558 thm phd_eq_iff
   558 thm phd.eq_iff
   559 thm phd_bn
   559 thm phd.bn
   560 thm phd_perm
   560 thm phd.perm
   561 thm phd_induct
   561 thm phd.induct
   562 thm phd_distinct
   562 thm phd.distinct
   563 
   563 
   564 (* example form Leroy 96 about modules; OTT *)
   564 (* example form Leroy 96 about modules; OTT *)
   565 
   565 
   566 nominal_datatype mexp =
   566 nominal_datatype mexp =
   567   Acc "path"
   567   Acc "path"
   612 | "Cbinders (Type1 t) = {atom t}"
   612 | "Cbinders (Type1 t) = {atom t}"
   613 | "Cbinders (Type2 t T) = {atom t}"
   613 | "Cbinders (Type2 t T) = {atom t}"
   614 | "Cbinders (SStru x S) = {atom x}"
   614 | "Cbinders (SStru x S) = {atom x}"
   615 | "Cbinders (SVal v T) = {atom v}"
   615 | "Cbinders (SVal v T) = {atom v}"
   616 
   616 
   617 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_fv
   617 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.fv
   618 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_eq_iff
   618 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.eq_iff
   619 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_bn
   619 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.bn
   620 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_perm
   620 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.perm
   621 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_induct
   621 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.induct
   622 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_inducts
   622 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.inducts
   623 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_distinct
   623 thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.distinct
   624 
   624 
   625 (* example 3 from Peter Sewell's bestiary *)
   625 (* example 3 from Peter Sewell's bestiary *)
   626 
   626 
   627 nominal_datatype exp =
   627 nominal_datatype exp =
   628   VarP "name"
   628   VarP "name"
   638 where
   638 where
   639   "bp'' (PVar x) = {atom x}"
   639   "bp'' (PVar x) = {atom x}"
   640 | "bp'' (PUnit) = {}"
   640 | "bp'' (PUnit) = {}"
   641 | "bp'' (PPair p1 p2) = bp'' p1 \<union> bp'' p2"
   641 | "bp'' (PPair p1 p2) = bp'' p1 \<union> bp'' p2"
   642 
   642 
   643 thm exp_pat3_fv
   643 thm exp_pat3.fv
   644 thm exp_pat3_eq_iff
   644 thm exp_pat3.eq_iff
   645 thm exp_pat3_bn
   645 thm exp_pat3.bn
   646 thm exp_pat3_perm
   646 thm exp_pat3.perm
   647 thm exp_pat3_induct
   647 thm exp_pat3.induct
   648 thm exp_pat3_distinct
   648 thm exp_pat3.distinct
   649 
   649 
   650 (* example 6 from Peter Sewell's bestiary *)
   650 (* example 6 from Peter Sewell's bestiary *)
   651 nominal_datatype exp6 =
   651 nominal_datatype exp6 =
   652   EVar name
   652   EVar name
   653 | EPair exp6 exp6
   653 | EPair exp6 exp6
   661 where
   661 where
   662   "bp6 (PVar' x) = {atom x}"
   662   "bp6 (PVar' x) = {atom x}"
   663 | "bp6 (PUnit') = {}"
   663 | "bp6 (PUnit') = {}"
   664 | "bp6 (PPair' p1 p2) = bp6 p1 \<union> bp6 p2"
   664 | "bp6 (PPair' p1 p2) = bp6 p1 \<union> bp6 p2"
   665 
   665 
   666 thm exp6_pat6_fv
   666 thm exp6_pat6.fv
   667 thm exp6_pat6_eq_iff
   667 thm exp6_pat6.eq_iff
   668 thm exp6_pat6_bn
   668 thm exp6_pat6.bn
   669 thm exp6_pat6_perm
   669 thm exp6_pat6.perm
   670 thm exp6_pat6_induct
   670 thm exp6_pat6.induct
   671 thm exp6_pat6_distinct
   671 thm exp6_pat6.distinct
   672 
   672 
   673 (* THE REST ARE NOT SUPPOSED TO WORK YET *)
   673 (* THE REST ARE NOT SUPPOSED TO WORK YET *)
   674 
   674 
   675 (* example 7 from Peter Sewell's bestiary *)
   675 (* example 7 from Peter Sewell's bestiary *)
   676 (* dest_Const raised
   676 (* dest_Const raised