41 lemma Not_eqvt: |
42 lemma Not_eqvt: |
42 shows "p \<bullet> (\<not> A) = (\<not> (p \<bullet> A))" |
43 shows "p \<bullet> (\<not> A) = (\<not> (p \<bullet> A))" |
43 by (simp add: permute_bool_def) |
44 by (simp add: permute_bool_def) |
44 |
45 |
45 lemma all_eqvt: |
46 lemma all_eqvt: |
|
47 shows "p \<bullet> (\<forall>x. P x) = (\<forall>x. (p \<bullet> P) x)" |
|
48 unfolding permute_fun_def permute_bool_def |
|
49 by (auto, drule_tac x="p \<bullet> x" in spec, simp) |
|
50 |
|
51 lemma all_eqvt2: |
46 shows "p \<bullet> (\<forall>x. P x) = (\<forall>x. p \<bullet> P (- p \<bullet> x))" |
52 shows "p \<bullet> (\<forall>x. P x) = (\<forall>x. p \<bullet> P (- p \<bullet> x))" |
47 unfolding permute_fun_def permute_bool_def |
53 unfolding permute_fun_def permute_bool_def |
48 by (auto, drule_tac x="p \<bullet> x" in spec, simp) |
54 by (auto, drule_tac x="p \<bullet> x" in spec, simp) |
49 |
55 |
50 lemma ex_eqvt: |
56 lemma ex_eqvt: |
|
57 shows "p \<bullet> (\<exists>x. P x) = (\<exists>x. (p \<bullet> P) x)" |
|
58 unfolding permute_fun_def permute_bool_def |
|
59 by (auto, rule_tac x="p \<bullet> x" in exI, simp) |
|
60 |
|
61 lemma ex_eqvt2: |
51 shows "p \<bullet> (\<exists>x. P x) = (\<exists>x. p \<bullet> P (- p \<bullet> x))" |
62 shows "p \<bullet> (\<exists>x. P x) = (\<exists>x. p \<bullet> P (- p \<bullet> x))" |
52 unfolding permute_fun_def permute_bool_def |
63 unfolding permute_fun_def permute_bool_def |
53 by (auto, rule_tac x="p \<bullet> x" in exI, simp) |
64 by (auto, rule_tac x="p \<bullet> x" in exI, simp) |
54 |
65 |
55 lemma ex1_eqvt: |
66 lemma ex1_eqvt: |
|
67 shows "p \<bullet> (\<exists>!x. P x) = (\<exists>!x. (p \<bullet> P) x)" |
|
68 unfolding Ex1_def |
|
69 by (simp add: ex_eqvt permute_fun_def conj_eqvt all_eqvt imp_eqvt eq_eqvt) |
|
70 |
|
71 lemma ex1_eqvt2: |
56 shows "p \<bullet> (\<exists>!x. P x) = (\<exists>!x. p \<bullet> P (- p \<bullet> x))" |
72 shows "p \<bullet> (\<exists>!x. P x) = (\<exists>!x. p \<bullet> P (- p \<bullet> x))" |
57 unfolding Ex1_def ex_eqvt conj_eqvt all_eqvt imp_eqvt eq_eqvt |
73 unfolding Ex1_def ex_eqvt2 conj_eqvt all_eqvt2 imp_eqvt eq_eqvt |
58 by simp |
74 by simp |
59 |
75 |
60 lemma the_eqvt: |
76 lemma the_eqvt: |
61 assumes unique: "\<exists>!x. P x" |
77 assumes unique: "\<exists>!x. P x" |
62 shows "p \<bullet> (THE x. P x) = (THE x. p \<bullet> P (- p \<bullet> x))" |
78 shows "p \<bullet> (THE x. P x) = (THE x. p \<bullet> P (- p \<bullet> x))" |
63 apply(rule the1_equality [symmetric]) |
79 apply(rule the1_equality [symmetric]) |
64 apply(simp add: ex1_eqvt[symmetric]) |
80 apply(simp add: ex1_eqvt2[symmetric]) |
65 apply(simp add: permute_bool_def unique) |
81 apply(simp add: permute_bool_def unique) |
66 apply(simp add: permute_bool_def) |
82 apply(simp add: permute_bool_def) |
67 apply(rule theI'[OF unique]) |
83 apply(rule theI'[OF unique]) |
68 done |
84 done |
69 |
85 |
93 shows "a \<sharp> {}" |
113 shows "a \<sharp> {}" |
94 by (simp add: fresh_def supp_set_empty) |
114 by (simp add: fresh_def supp_set_empty) |
95 |
115 |
96 lemma UNIV_eqvt: |
116 lemma UNIV_eqvt: |
97 shows "p \<bullet> UNIV = UNIV" |
117 shows "p \<bullet> UNIV = UNIV" |
98 unfolding UNIV_def Collect_eqvt True_eqvt .. |
118 unfolding UNIV_def Collect_eqvt2 True_eqvt .. |
99 |
119 |
100 lemma union_eqvt: |
120 lemma union_eqvt: |
101 shows "p \<bullet> (A \<union> B) = (p \<bullet> A) \<union> (p \<bullet> B)" |
121 shows "p \<bullet> (A \<union> B) = (p \<bullet> A) \<union> (p \<bullet> B)" |
102 unfolding Un_def Collect_eqvt disj_eqvt mem_eqvt by simp |
122 unfolding Un_def Collect_eqvt2 disj_eqvt mem_eqvt by simp |
103 |
123 |
104 lemma inter_eqvt: |
124 lemma inter_eqvt: |
105 shows "p \<bullet> (A \<inter> B) = (p \<bullet> A) \<inter> (p \<bullet> B)" |
125 shows "p \<bullet> (A \<inter> B) = (p \<bullet> A) \<inter> (p \<bullet> B)" |
106 unfolding Int_def Collect_eqvt conj_eqvt mem_eqvt by simp |
126 unfolding Int_def Collect_eqvt2 conj_eqvt mem_eqvt by simp |
107 |
127 |
108 lemma Diff_eqvt: |
128 lemma Diff_eqvt: |
109 fixes A B :: "'a::pt set" |
129 fixes A B :: "'a::pt set" |
110 shows "p \<bullet> (A - B) = p \<bullet> A - p \<bullet> B" |
130 shows "p \<bullet> (A - B) = p \<bullet> A - p \<bullet> B" |
111 unfolding set_diff_eq Collect_eqvt conj_eqvt Not_eqvt mem_eqvt by simp |
131 unfolding set_diff_eq Collect_eqvt2 conj_eqvt Not_eqvt mem_eqvt by simp |
112 |
132 |
113 lemma Compl_eqvt: |
133 lemma Compl_eqvt: |
114 fixes A :: "'a::pt set" |
134 fixes A :: "'a::pt set" |
115 shows "p \<bullet> (- A) = - (p \<bullet> A)" |
135 shows "p \<bullet> (- A) = - (p \<bullet> A)" |
116 unfolding Compl_eq_Diff_UNIV Diff_eqvt UNIV_eqvt .. |
136 unfolding Compl_eq_Diff_UNIV Diff_eqvt UNIV_eqvt .. |
203 shows "a \<sharp> ()" |
218 shows "a \<sharp> ()" |
204 by (simp add: fresh_def supp_unit) |
219 by (simp add: fresh_def supp_unit) |
205 |
220 |
206 section {* Equivariance automation *} |
221 section {* Equivariance automation *} |
207 |
222 |
208 text {* |
|
209 below is a construction site for a conversion that |
|
210 pushes permutations into a term as far as possible |
|
211 *} |
|
212 |
|
213 text {* Setup of the theorem attributes @{text eqvt} and @{text eqvt_force} *} |
223 text {* Setup of the theorem attributes @{text eqvt} and @{text eqvt_force} *} |
214 |
224 |
215 use "nominal_thmdecls.ML" |
225 use "nominal_thmdecls.ML" |
216 setup "NominalThmDecls.setup" |
226 setup "Nominal_ThmDecls.setup" |
217 |
227 |
218 lemmas [eqvt] = |
228 lemmas [eqvt] = |
219 (* connectives *) |
229 (* connectives *) |
220 eq_eqvt if_eqvt imp_eqvt disj_eqvt conj_eqvt Not_eqvt |
230 eq_eqvt if_eqvt imp_eqvt disj_eqvt conj_eqvt Not_eqvt |
221 True_eqvt False_eqvt |
231 True_eqvt False_eqvt ex_eqvt all_eqvt |
222 imp_eqvt [folded induct_implies_def] |
232 imp_eqvt [folded induct_implies_def] |
|
233 |
|
234 (* nominal *) |
|
235 permute_eqvt supp_eqvt fresh_eqvt |
223 |
236 |
224 (* datatypes *) |
237 (* datatypes *) |
225 permute_prod.simps |
238 permute_prod.simps |
226 fst_eqvt snd_eqvt |
239 fst_eqvt snd_eqvt |
227 |
240 |
228 (* sets *) |
241 (* sets *) |
229 empty_eqvt UNIV_eqvt union_eqvt inter_eqvt |
242 empty_eqvt UNIV_eqvt union_eqvt inter_eqvt |
230 Diff_eqvt Compl_eqvt insert_eqvt |
243 Diff_eqvt Compl_eqvt insert_eqvt |
231 |
244 |
232 (* A simple conversion pushing permutations into a term *) |
245 declare permute_pure [eqvt] |
233 |
246 |
234 ML {* |
247 thm eqvt |
235 fun OF1 thm1 thm2 = thm2 RS thm1 |
248 |
236 |
249 text {* helper lemmas for the eqvt_tac *} |
237 fun get_eqvt_thms ctxt = |
|
238 map (OF1 @{thm eq_reflection}) (NominalThmDecls.get_eqvt_thms ctxt) |
|
239 *} |
|
240 |
|
241 ML {* |
|
242 fun eqvt_conv ctxt ctrm = |
|
243 case (term_of ctrm) of |
|
244 (Const (@{const_name "permute"}, _) $ _ $ t) => |
|
245 (if is_Const (head_of t) |
|
246 then (More_Conv.rewrs_conv (get_eqvt_thms ctxt) |
|
247 then_conv eqvt_conv ctxt) ctrm |
|
248 else Conv.comb_conv (eqvt_conv ctxt) ctrm) |
|
249 | _ $ _ => Conv.comb_conv (eqvt_conv ctxt) ctrm |
|
250 | Abs _ => Conv.abs_conv (fn (_, ctxt) => eqvt_conv ctxt) ctxt ctrm |
|
251 | _ => Conv.all_conv ctrm |
|
252 *} |
|
253 |
|
254 ML {* |
|
255 fun eqvt_tac ctxt = |
|
256 CONVERSION (More_Conv.bottom_conv (fn ctxt => eqvt_conv ctxt) ctxt) |
|
257 *} |
|
258 |
|
259 lemma "p \<bullet> (A \<longrightarrow> B = (C::bool))" |
|
260 apply(tactic {* eqvt_tac @{context} 1 *}) |
|
261 oops |
|
262 |
|
263 text {* |
|
264 Another conversion for pushing permutations into a term. |
|
265 It is designed not to apply rules like @{term permute_pure} to |
|
266 applications or abstractions, only to constants or free |
|
267 variables. Thus permutations are not removed too early, and they |
|
268 have a chance to cancel with bound variables. |
|
269 *} |
|
270 |
250 |
271 definition |
251 definition |
272 "unpermute p = permute (- p)" |
252 "unpermute p = permute (- p)" |
273 |
253 |
274 lemma push_apply: |
254 lemma eqvt_apply: |
275 fixes f :: "'a::pt \<Rightarrow> 'b::pt" and x :: "'a::pt" |
255 fixes f :: "'a::pt \<Rightarrow> 'b::pt" |
|
256 and x :: "'a::pt" |
276 shows "p \<bullet> (f x) \<equiv> (p \<bullet> f) (p \<bullet> x)" |
257 shows "p \<bullet> (f x) \<equiv> (p \<bullet> f) (p \<bullet> x)" |
277 unfolding permute_fun_def by simp |
258 unfolding permute_fun_def by simp |
278 |
259 |
279 lemma push_lambda: |
260 lemma eqvt_lambda: |
280 fixes f :: "'a::pt \<Rightarrow> 'b::pt" |
261 fixes f :: "'a::pt \<Rightarrow> 'b::pt" |
281 shows "p \<bullet> (\<lambda>x. f x) \<equiv> (\<lambda>x. p \<bullet> (f (unpermute p x)))" |
262 shows "p \<bullet> (\<lambda>x. f x) \<equiv> (\<lambda>x. p \<bullet> (f (unpermute p x)))" |
282 unfolding permute_fun_def unpermute_def by simp |
263 unfolding permute_fun_def unpermute_def by simp |
283 |
264 |
284 lemma push_bound: |
265 lemma eqvt_bound: |
285 shows "p \<bullet> unpermute p x \<equiv> x" |
266 shows "p \<bullet> unpermute p x \<equiv> x" |
286 unfolding unpermute_def by simp |
267 unfolding unpermute_def by simp |
287 |
268 |
288 ML {* |
269 use "nominal_permeq.ML" |
289 structure PushData = Named_Thms |
270 |
290 ( |
271 |
291 val name = "push" |
272 lemma "p \<bullet> (A \<longrightarrow> B = C)" |
292 val description = "push permutations" |
273 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
293 ) |
274 oops |
294 |
275 |
295 local |
276 lemma "p \<bullet> (\<lambda>(x::'a::pt). A \<longrightarrow> (B::'a \<Rightarrow> bool) x = C) = foo" |
296 |
277 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
297 fun push_apply_conv ctxt ct = |
278 oops |
298 case (term_of ct) of |
279 |
299 (Const (@{const_name "permute"}, _) $ _ $ (_ $ _)) => |
280 lemma "p \<bullet> (\<lambda>x y. \<exists>z. x = z \<and> x = y \<longrightarrow> z \<noteq> x) = foo" |
300 let |
281 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
301 val (perm, t) = Thm.dest_comb ct |
282 oops |
302 val (_, p) = Thm.dest_comb perm |
283 |
303 val (f, x) = Thm.dest_comb t |
284 lemma "p \<bullet> (\<lambda>f x. f (g (f x))) = foo" |
304 val a = ctyp_of_term x; |
285 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
305 val b = ctyp_of_term t; |
286 oops |
306 val ty_insts = map SOME [b, a] |
287 |
307 val term_insts = map SOME [p, f, x] |
288 lemma "p \<bullet> (\<lambda>q. q \<bullet> (r \<bullet> x)) = foo" |
308 in |
289 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
309 Drule.instantiate' ty_insts term_insts @{thm push_apply} |
290 oops |
310 end |
291 |
311 | _ => Conv.no_conv ct |
292 lemma "p \<bullet> (q \<bullet> r \<bullet> x) = foo" |
312 |
293 apply (tactic {* Nominal_Permeq.eqvt_tac @{context} 1 *}) |
313 fun push_lambda_conv ctxt ct = |
294 oops |
314 case (term_of ct) of |
295 |
315 (Const (@{const_name "permute"}, _) $ _ $ Abs _) => |
|
316 Conv.rewr_conv @{thm push_lambda} ct |
|
317 | _ => Conv.no_conv ct |
|
318 |
|
319 in |
|
320 |
|
321 fun push_conv ctxt ct = |
|
322 Conv.first_conv |
|
323 [ Conv.rewr_conv @{thm push_bound}, |
|
324 push_apply_conv ctxt |
|
325 then_conv Conv.comb_conv (push_conv ctxt), |
|
326 push_lambda_conv ctxt |
|
327 then_conv Conv.abs_conv (fn (v, ctxt) => push_conv ctxt) ctxt, |
|
328 More_Conv.rewrs_conv (PushData.get ctxt), |
|
329 Conv.all_conv |
|
330 ] ct |
|
331 |
|
332 fun push_tac ctxt = |
|
333 CONVERSION (More_Conv.bottom_conv (fn ctxt => push_conv ctxt) ctxt) |
|
334 |
296 |
335 end |
297 end |
336 *} |
|
337 |
|
338 setup PushData.setup |
|
339 |
|
340 declare permute_pure [THEN eq_reflection, push] |
|
341 |
|
342 lemma push_eq [THEN eq_reflection, push]: |
|
343 "p \<bullet> (op =) = (op =)" |
|
344 by (simp add: expand_fun_eq permute_fun_def eq_eqvt) |
|
345 |
|
346 lemma push_All [THEN eq_reflection, push]: |
|
347 "p \<bullet> All = All" |
|
348 by (simp add: expand_fun_eq permute_fun_def all_eqvt) |
|
349 |
|
350 lemma push_Ex [THEN eq_reflection, push]: |
|
351 "p \<bullet> Ex = Ex" |
|
352 by (simp add: expand_fun_eq permute_fun_def ex_eqvt) |
|
353 |
|
354 lemma "p \<bullet> (A \<longrightarrow> B = (C::bool))" |
|
355 apply (tactic {* push_tac @{context} 1 *}) |
|
356 oops |
|
357 |
|
358 lemma "p \<bullet> (\<lambda>x. A \<longrightarrow> B x = (C::bool)) = foo" |
|
359 apply (tactic {* push_tac @{context} 1 *}) |
|
360 oops |
|
361 |
|
362 lemma "p \<bullet> (\<lambda>x y. \<exists>z. x = z \<and> x = y \<longrightarrow> z \<noteq> x) = foo" |
|
363 apply (tactic {* push_tac @{context} 1 *}) |
|
364 oops |
|
365 |
|
366 lemma "p \<bullet> (\<lambda>f x. f (g (f x))) = foo" |
|
367 apply (tactic {* push_tac @{context} 1 *}) |
|
368 oops |
|
369 |
|
370 end |
|