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