--- a/Quot/Nominal/Abs.thy Fri Jan 29 07:09:52 2010 +0100
+++ b/Quot/Nominal/Abs.thy Sat Jan 30 11:44:25 2010 +0100
@@ -25,27 +25,25 @@
apply(simp)
done
-datatype 'a ABS_raw = Abs_raw "atom set" "'a::pt"
-primrec
- Abs_raw_map
-where
- "Abs_raw_map f (Abs_raw as x) = Abs_raw as (f x)"
+datatype 'a rabst =
+ RAbst "atom set" "'a::pt"
+
+fun map_fun
+where "map_fun f (RAbst bs x) = RAbst bs (f x)"
-fun
- Abs_raw_rel
-where
- "Abs_raw_rel R (Abs_raw as x) (Abs_raw bs y) = R x y"
+fun map_rel
+where "map_rel R (RAbst bs x) (RAbst cs y) = R x y"
-declare [[map "ABS_raw" = (Abs_raw_map, Abs_raw_rel)]]
+declare [[map "rabst" = (map_fun, map_rel)]]
-instantiation ABS_raw :: (pt) pt
+instantiation rabst :: (pt) pt
begin
primrec
- permute_ABS_raw
+ permute_rabst
where
- "permute_ABS_raw p (Abs_raw as x) = Abs_raw (p \<bullet> as) (p \<bullet> x)"
+ "p \<bullet> (RAbst bs x) = RAbst (p \<bullet> bs) (p \<bullet> x)"
instance
apply(default)
@@ -53,89 +51,121 @@
apply(simp_all)
done
-end
+end
fun
- alpha_abs :: "('a::pt) ABS_raw \<Rightarrow> 'a ABS_raw \<Rightarrow> bool"
+ alpha_gen
where
- "alpha_abs (Abs_raw as x) (Abs_raw bs y) =
- (\<exists>pi. (supp x) - as = (supp y) - bs \<and> ((supp x) - as) \<sharp>* pi \<and> pi \<bullet> x = y)"
+ alpha_gen[simp del]:
+ "(alpha_gen (bs, x) R f pi (cs, y)) \<longleftrightarrow> (f x - bs = f y - cs) \<and> ((f x - bs) \<sharp>* pi) \<and> (R (pi \<bullet> x) y)"
+
+notation
+ alpha_gen ("_ \<approx>gen _ _ _ _")
+
+lemma alpha_gen_refl:
+ assumes a: "R x x"
+ shows "(bs, x) \<approx>gen R f 0 (bs, x)"
+ using a by (simp add: alpha_gen fresh_star_def fresh_zero_perm)
+
+lemma alpha_gen_sym:
+ assumes a: "(bs, x) \<approx>gen R f p (cs, y)"
+ and b: "R (p \<bullet> x) y \<Longrightarrow> R (- p \<bullet> y) x"
+ shows "(cs, y) \<approx>gen R f (- p) (bs, x)"
+ using a b by (simp add: alpha_gen fresh_star_def fresh_def supp_minus_perm)
+
+lemma alpha_gen_trans:
+ assumes a: "(bs, x) \<approx>gen R f p1 (cs, y)"
+ and b: "(cs, y) \<approx>gen R f p2 (ds, z)"
+ and c: "\<lbrakk>R (p1 \<bullet> x) y; R (p2 \<bullet> y) z\<rbrakk> \<Longrightarrow> R ((p2 + p1) \<bullet> x) z"
+ shows "(bs, x) \<approx>gen R f (p2 + p1) (ds, z)"
+ using a b c using supp_plus_perm
+ apply(simp add: alpha_gen fresh_star_def fresh_def)
+ apply(blast)
+ done
+
+lemma alpha_gen_eqvt:
+ assumes a: "(bs, x) \<approx>gen R f q (cs, y)"
+ and b: "R (q \<bullet> x) y \<Longrightarrow> R (p \<bullet> (q \<bullet> x)) (p \<bullet> y)"
+ and c: "p \<bullet> (f x) = f (p \<bullet> x)"
+ and d: "p \<bullet> (f y) = f (p \<bullet> y)"
+ shows "(p \<bullet> bs, p \<bullet> x) \<approx>gen R f (p \<bullet> q) (p \<bullet> cs, p \<bullet> y)"
+ using a b
+ apply(simp add: alpha_gen c[symmetric] d[symmetric] Diff_eqvt[symmetric])
+ apply(simp add: permute_eqvt[symmetric])
+ apply(simp add: fresh_star_permute_iff)
+ apply(clarsimp)
+ done
+
+fun
+ alpha_rabst :: "('a::pt) rabst \<Rightarrow> 'a rabst \<Rightarrow> bool" ("_ \<approx>raw _")
+where
+ "(RAbst bs x) \<approx>raw (RAbst cs y) = (\<exists>p. (bs, x) \<approx>gen (op=) supp p (cs, y))"
lemma alpha_reflp:
- shows "alpha_abs ab ab"
-apply(induct ab)
+ shows "abst \<approx>raw abst"
+apply(induct abst)
apply(simp)
-apply(rule_tac x="0" in exI)
-apply(simp add: fresh_star_def fresh_zero_perm)
+apply(rule exI)
+apply(rule alpha_gen_refl)
+apply(simp)
done
lemma alpha_symp:
- assumes a: "alpha_abs ab1 ab2"
- shows "alpha_abs ab2 ab1"
+ assumes a: "abst1 \<approx>raw abst2"
+ shows "abst2 \<approx>raw abst1"
using a
-apply(induct rule: alpha_abs.induct)
+apply(induct rule: alpha_rabst.induct)
apply(simp)
-apply(clarify)
-apply(rule_tac x="- pi" in exI)
-apply(auto)
-apply(auto simp add: fresh_star_def)
-apply(simp add: fresh_def supp_minus_perm)
+apply(erule exE)
+apply(rule exI)
+apply(rule alpha_gen_sym)
+apply(assumption)
+apply(clarsimp)
done
lemma alpha_transp:
- assumes a1: "alpha_abs ab1 ab2"
- and a2: "alpha_abs ab2 ab3"
- shows "alpha_abs ab1 ab3"
+ assumes a1: "abst1 \<approx>raw abst2"
+ and a2: "abst2 \<approx>raw abst3"
+ shows "abst1 \<approx>raw abst3"
using a1 a2
-apply(induct rule: alpha_abs.induct)
-apply(induct rule: alpha_abs.induct)
+apply(induct rule: alpha_rabst.induct)
+apply(induct rule: alpha_rabst.induct)
apply(simp)
-apply(clarify)
-apply(rule_tac x="pia + pi" in exI)
+apply(erule exE)+
+apply(rule exI)
+apply(rule alpha_gen_trans)
+apply(assumption)
+apply(assumption)
apply(simp)
-apply(auto simp add: fresh_star_def)
-using supp_plus_perm
-apply(simp add: fresh_def)
-apply(blast)
done
lemma alpha_eqvt:
- assumes a: "alpha_abs ab1 ab2"
- shows "alpha_abs (p \<bullet> ab1) (p \<bullet> ab2)"
+ assumes a: "abst1 \<approx>raw abst2"
+ shows "(p \<bullet> abst1) \<approx>raw(p \<bullet> abst2)"
using a
-apply(induct ab1 ab2 rule: alpha_abs.induct)
+apply(induct abst1 abst2 rule: alpha_rabst.induct)
apply(simp)
-apply(clarify)
-apply(rule conjI)
-apply(simp add: supp_eqvt[symmetric])
-apply(simp add: Diff_eqvt[symmetric])
-apply(rule_tac x="p \<bullet> pi" in exI)
-apply(rule conjI)
-apply(simp add: supp_eqvt[symmetric])
-apply(simp add: Diff_eqvt[symmetric])
-apply(simp only: fresh_star_permute_iff)
-apply(simp add: permute_eqvt[symmetric])
+apply(erule exE)
+apply(rule exI)
+apply(rule alpha_gen_eqvt)
+apply(assumption)
+apply(simp)
+apply(simp add: supp_eqvt)
+apply(simp add: supp_eqvt)
done
lemma test1:
assumes a1: "a \<notin> (supp x) - bs"
and a2: "b \<notin> (supp x) - bs"
- shows "alpha_abs (Abs_raw bs x) (Abs_raw ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
-unfolding alpha_abs.simps
+ shows "(RAbst bs x) \<approx>raw (RAbst ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
+apply(simp)
apply(rule_tac x="(a \<rightleftharpoons> b)" in exI)
-apply(rule_tac conjI)
-apply(simp add: supp_eqvt[symmetric])
-apply(simp add: Diff_eqvt[symmetric])
-using a1 a2
-apply(simp add: swap_set_fresh)
-apply(rule conjI)
-prefer 2
-apply(simp)
-apply(simp add: fresh_star_def)
-apply(simp add: fresh_def)
+apply(simp add: alpha_gen)
+apply(simp add: supp_eqvt[symmetric] Diff_eqvt[symmetric])
+apply(simp add: swap_set_fresh[OF a1 a2])
apply(subgoal_tac "supp (a \<rightleftharpoons> b) \<subseteq> {a, b}")
using a1 a2
-apply -
+apply(simp add: fresh_star_def fresh_def)
apply(blast)
apply(simp add: supp_swap)
done
@@ -143,67 +173,65 @@
fun
s_test
where
- "s_test (Abs_raw bs x) = (supp x) - bs"
+ "s_test (RAbst bs x) = (supp x) - bs"
lemma s_test_lemma:
- assumes a: "alpha_abs x y"
+ assumes a: "x \<approx>raw y"
shows "s_test x = s_test y"
using a
-apply(induct rule: alpha_abs.induct)
-apply(simp)
+apply(induct rule: alpha_rabst.induct)
+apply(simp add: alpha_gen)
done
-quotient_type 'a ABS = "('a::pt) ABS_raw" / "alpha_abs::('a::pt) ABS_raw \<Rightarrow> 'a ABS_raw \<Rightarrow> bool"
+quotient_type 'a abst = "('a::pt) rabst" / "alpha_rabst::('a::pt) rabst \<Rightarrow> 'a rabst \<Rightarrow> bool"
apply(rule equivpI)
unfolding reflp_def symp_def transp_def
apply(auto intro: alpha_reflp alpha_symp alpha_transp)
done
quotient_definition
- "Abs::atom set \<Rightarrow> ('a::pt) \<Rightarrow> 'a ABS"
+ "Abst::atom set \<Rightarrow> ('a::pt) \<Rightarrow> 'a abst"
as
- "Abs_raw"
+ "RAbst"
lemma [quot_respect]:
- shows "((op =) ===> (op =) ===> alpha_abs) Abs_raw Abs_raw"
-apply(auto simp del: alpha_abs.simps)
-apply(rule alpha_reflp)
+ shows "((op =) ===> (op =) ===> alpha_rabst) RAbst RAbst"
+apply(simp del: alpha_rabst.simps add: alpha_reflp)
done
lemma [quot_respect]:
- shows "((op =) ===> alpha_abs ===> alpha_abs) permute permute"
-apply(auto)
+ shows "((op =) ===> alpha_rabst ===> alpha_rabst) permute permute"
apply(simp add: alpha_eqvt)
done
lemma [quot_respect]:
- shows "(alpha_abs ===> (op =)) s_test s_test"
+ shows "(alpha_rabst ===> (op =)) s_test s_test"
apply(simp add: s_test_lemma)
done
-lemma ABS_induct:
- "\<lbrakk>\<And>as (x::'a::pt). P (Abs as x)\<rbrakk> \<Longrightarrow> P t"
-apply(lifting ABS_raw.induct)
+lemma abst_induct:
+ "\<lbrakk>\<And>as (x::'a::pt). P (Abst as x)\<rbrakk> \<Longrightarrow> P t"
+apply(lifting rabst.induct)
done
-instantiation ABS :: (pt) pt
+instantiation abst :: (pt) pt
begin
quotient_definition
- "permute_ABS::perm \<Rightarrow> ('a::pt ABS) \<Rightarrow> 'a ABS"
+ "permute_abst::perm \<Rightarrow> ('a::pt abst) \<Rightarrow> 'a abst"
as
- "permute::perm \<Rightarrow> ('a::pt ABS_raw) \<Rightarrow> 'a ABS_raw"
+ "permute::perm \<Rightarrow> ('a::pt rabst) \<Rightarrow> 'a rabst"
lemma permute_ABS [simp]:
- fixes x::"'b::pt" (* ??? has to be 'b \<dots> 'a doe not work *)
- shows "(p \<bullet> (Abs as x)) = Abs (p \<bullet> as) (p \<bullet> x)"
-apply(lifting permute_ABS_raw.simps(1))
+ fixes x::"'a::pt" (* ??? has to be 'a \<dots> 'b does not work *)
+ shows "(p \<bullet> (Abst as x)) = Abst (p \<bullet> as) (p \<bullet> x)"
+apply(lifting permute_rabst.simps(1))
done
instance
apply(default)
- apply(induct_tac [!] x rule: ABS_induct)
+ apply(induct_tac [!] x rule: abst_induct)
apply(simp_all)
done
@@ -212,13 +240,13 @@
lemma test1_lifted:
assumes a1: "a \<notin> (supp x) - bs"
and a2: "b \<notin> (supp x) - bs"
- shows "(Abs bs x) = (Abs ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
+ shows "(Abst bs x) = (Abst ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
using a1 a2
apply(lifting test1)
done
-lemma Abs_supports:
- shows "((supp x) - as) supports (Abs as x) "
+lemma Abst_supports:
+ shows "((supp x) - as) supports (Abst as x)"
unfolding supports_def
apply(clarify)
apply(simp (no_asm))
@@ -227,18 +255,18 @@
done
quotient_definition
- "s_test_lifted :: ('a::pt) ABS \<Rightarrow> atom \<Rightarrow> bool"
+ "s_test_lifted :: ('a::pt) abst \<Rightarrow> atom \<Rightarrow> bool"
as
- "s_test::('a::pt) ABS_raw \<Rightarrow> atom \<Rightarrow> bool"
+ "s_test::('a::pt) rabst \<Rightarrow> atom \<Rightarrow> bool"
lemma s_test_lifted_simp:
- shows "s_test_lifted (Abs bs x) = (supp x) - bs"
+ shows "s_test_lifted (Abst bs x) = (supp x) - bs"
apply(lifting s_test.simps(1))
done
lemma s_test_lifted_eqvt:
shows "(p \<bullet> (s_test_lifted ab)) = s_test_lifted (p \<bullet> ab)"
-apply(induct ab rule: ABS_induct)
+apply(induct ab rule: abst_induct)
apply(simp add: s_test_lifted_simp supp_eqvt Diff_eqvt)
done
@@ -257,7 +285,7 @@
lemma s_test_fresh_lemma:
- shows "(a \<sharp> Abs bs x) \<Longrightarrow> (a \<sharp> s_test_lifted (Abs bs x))"
+ shows "(a \<sharp> Abst bs x) \<Longrightarrow> (a \<sharp> s_test_lifted (Abst bs x))"
apply(rule fresh_f_empty_supp)
apply(rule allI)
apply(subst permute_fun_def)
@@ -279,7 +307,7 @@
lemma s_test_subset:
fixes x::"'a::fs"
- shows "((supp x) - as) \<subseteq> (supp (Abs as x))"
+ shows "((supp x) - as) \<subseteq> (supp (Abst as x))"
apply(rule subsetI)
apply(rule contrapos_pp)
apply(assumption)
@@ -292,34 +320,36 @@
apply(simp add: finite_supp)
done
-lemma supp_Abs:
+lemma supp_Abst:
fixes x::"'a::fs"
- shows "supp (Abs as x) = (supp x) - as"
+ shows "supp (Abst as x) = (supp x) - as"
apply(rule subset_antisym)
apply(rule supp_is_subset)
-apply(rule Abs_supports)
+apply(rule Abst_supports)
apply(simp add: finite_supp)
apply(rule s_test_subset)
done
-instance ABS :: (fs) fs
+instance abst :: (fs) fs
apply(default)
-apply(induct_tac x rule: ABS_induct)
-apply(simp add: supp_Abs)
+apply(induct_tac x rule: abst_induct)
+apply(simp add: supp_Abst)
apply(simp add: finite_supp)
done
lemma fresh_abs:
fixes x::"'a::fs"
- shows "a \<sharp> Abs bs x = (a \<in> bs \<or> (a \<notin> bs \<and> a \<sharp> x))"
+ shows "a \<sharp> Abst bs x = (a \<in> bs \<or> (a \<notin> bs \<and> a \<sharp> x))"
apply(simp add: fresh_def)
-apply(simp add: supp_Abs)
+apply(simp add: supp_Abst)
apply(auto)
done
+thm alpha_rabst.simps(1)
+
lemma abs_eq:
- shows "(Abs as x) = (Abs bs y) \<longleftrightarrow> (\<exists>pi. supp x - as = supp y - bs \<and> (supp x - as) \<sharp>* pi \<and> pi \<bullet> x = y)"
-apply(lifting alpha_abs.simps(1))
+ shows "(Abst bs x) = (Abst cs y) \<longleftrightarrow> (\<exists>p. (bs, x) \<approx>gen (op =) supp p (cs, y))"
+apply(lifting alpha_rabst.simps(1))
done
end