diff options
| author | Hannes Schulze <haschu0103@outlook.de> | 2025-12-03 20:34:41 +0100 |
|---|---|---|
| committer | Hannes Schulze <haschu0103@outlook.de> | 2025-12-03 20:34:41 +0100 |
| commit | 71a6a3d5b6f4b428b463bc4a0766c91d8c1d5768 (patch) | |
| tree | add4bf6d650df4b8ec743de45fc37dc7de16baaa /Nominal/Equivariance.lean | |
| parent | 4ba4f11725d42286a2e94ee78dd938636ad2528a (diff) | |
refactor equivariant props to use type classes
Diffstat (limited to 'Nominal/Equivariance.lean')
| -rw-r--r-- | Nominal/Equivariance.lean | 224 |
1 files changed, 124 insertions, 100 deletions
diff --git a/Nominal/Equivariance.lean b/Nominal/Equivariance.lean index 4ba580d..2682a55 100644 --- a/Nominal/Equivariance.lean +++ b/Nominal/Equivariance.lean @@ -20,40 +20,42 @@ section Definition variable {X Y : Type} [PermSet πΈ X] [PermSet πΈ Y] /-- A function is equivariant if it is invariant to applying a permutation before or after the function. -/ -def Function.Equivariant (f : X β Y) : Prop := - β (x : X) (Ο : FPerm πΈ), f (Ο β’ x) = Ο β’ f x +class inductive Function.Equivariant (f : X β Y) : Prop + | intro : (β (x : X) (Ο : FPerm πΈ), f (Ο β’ x) = Ο β’ f x) β Equivariant f -/-- A set is equivariant if it is closed under permutations. -/ -def Set.Equivariant (S : Set X) : Prop := - β (x : X) (Ο : FPerm πΈ), x β S β Ο β’ x β S +lemma Function.equivariant (f : X β Y) [Equivariant πΈ f] : + β (x : X) (Ο : FPerm πΈ), f (Ο β’ x) = Ο β’ f x := by + cases (inferInstanceAs (Equivariant πΈ f)); assumption -/-- A binary relation is equivariant if it is closed under permutations. -/ -def Rel.Equivariant (R : Rel X Y) : Prop := - β (x : X) (y : Y) (Ο : FPerm πΈ), R x y β R (Ο β’ x) (Ο β’ y) +/-- A set is equivariant if it is closed under permutations. -/ +class inductive Set.Equivariant (S : Set X) : Prop + | intro : (β (x : X) (Ο : FPerm πΈ), x β S β Ο β’ x β S) β Equivariant S /-- For equivariant sets, we even have "if and only if". -/ -lemma Set.Equivariant.iff {S : Set X} : Set.Equivariant πΈ S β β (x : X) (Ο : FPerm πΈ), x β S β Ο β’ x β S := by - constructor - Β· intro h x Ο; constructor - Β· intro hx; exact h x Ο hx - Β· intro hx - apply (h (Ο β’ x) Οβ»ΒΉ) at hx - simp only [inv_smul_smul] at hx - exact hx - Β· intro h x Ο hx - exact (h x Ο).mp hx +lemma Set.equivariant (S : Set X) [Equivariant πΈ S] : + β (x : X) (Ο : FPerm πΈ), x β S β Ο β’ x β S := by + cases (inferInstanceAs (Equivariant πΈ S)); rename_i h + intro x Ο; constructor + Β· intro hx; exact h x Ο hx + Β· intro hx + apply (h (Ο β’ x) Οβ»ΒΉ) at hx + simp only [inv_smul_smul] at hx + exact hx + +/-- A binary relation is equivariant if it is closed under permutations. -/ +class inductive Rel.Equivariant (R : Rel X Y) : Prop + | intro : (β (x : X) (y : Y) (Ο : FPerm πΈ), R x y β R (Ο β’ x) (Ο β’ y)) β Equivariant R /-- For equivariant relations, we even have "if and only if". -/ -lemma Rel.Equivariant.iff {R : Rel X Y} : Rel.Equivariant πΈ R β β (x : X) (y : Y) (Ο : FPerm πΈ), R x y β R (Ο β’ x) (Ο β’ y) := by - constructor - Β· intro h x y Ο; constructor - Β· intro hxy; exact h x y Ο hxy - Β· intro hxy - apply (h (Ο β’ x) (Ο β’ y) Οβ»ΒΉ) at hxy - simp only [inv_smul_smul] at hxy - exact hxy - Β· intro h x y Ο hxy - exact (h x y Ο).mp hxy +lemma Rel.equivariant (R : Rel X Y) [Rel.Equivariant πΈ R] : + β (x : X) (y : Y) (Ο : FPerm πΈ), R x y β R (Ο β’ x) (Ο β’ y) := by + cases (inferInstanceAs (Equivariant πΈ R)); rename_i h + intro x y Ο; constructor + Β· intro hxy; exact h x y Ο hxy + Β· intro hxy + apply (h (Ο β’ x) (Ο β’ y) Οβ»ΒΉ) at hxy + simp only [inv_smul_smul] at hxy + exact hxy end Definition @@ -67,25 +69,32 @@ section Trivial variable {X Y Z : Type} [PermSet πΈ X] [PermSet πΈ Y] [PermSet πΈ Z] /-- The identity function is equivariant. -/ -lemma id_equivariant : Function.Equivariant πΈ (id : X β X) := by - simp [Function.Equivariant] +instance Function.Equivariant.id : Function.Equivariant πΈ (id : X β X) := by + constructor + simp /-- The composition of two equivariant functions is equivariant. -/ -lemma comp_equivariant {f : Y β Z} {g : X β Y} : Function.Equivariant πΈ f β Function.Equivariant πΈ g β Function.Equivariant πΈ (f β g) := by - intro hf hg x Ο +instance Function.Equivariant.comp + {f : Y β Z} [Function.Equivariant πΈ f] {g : X β Y} [Function.Equivariant πΈ g] : + Function.Equivariant πΈ (f β g) := by + constructor; intro x Ο calc - f (g (Ο β’ x)) = f (Ο β’ g x) := by rw [hg] - _ = Ο β’ (f (g x)) := by rw [hf] + f (g (Ο β’ x)) = f (Ο β’ g x) := by rw [β Function.equivariant πΈ g] + _ = Ο β’ (f (g x)) := by rw [β Function.equivariant πΈ f] /-- If a function is equivariant, its inverse is also equivariant. -/ -lemma Function.inv_equivariant {f : X β Y} {inv : Y β X} : Function.LeftInverse inv f β Function.RightInverse inv f β Function.Equivariant πΈ f β Function.Equivariant πΈ inv := by - intro hleft hright hequi y Ο +def Function.Equivariant.inv + {f : X β Y} [Function.Equivariant πΈ f] {inv : Y β X} + (hleft : Function.LeftInverse inv f) + (hright : Function.RightInverse inv f) : + Function.Equivariant πΈ inv := by + constructor; intro y Ο apply hleft.injective - rw [hequi, hright, hright] + rw [Function.equivariant πΈ f, hright, hright] /-- The subset relation is equivariant. -/ -lemma Set.subset_equivariant : Rel.Equivariant πΈ (Set.Subset : Set X β Set X β Prop) := by - intro S T Ο hST x hx +instance Set.Equivariant.subset : Rel.Equivariant πΈ (Set.Subset : Set X β Set X β Prop) := by + constructor; intro S T Ο hST x hx rw [Set.mem_smul_set_iff_inv_smul_mem] at hx rw [Set.mem_smul_set_iff_inv_smul_mem] exact hST hx @@ -104,27 +113,29 @@ variable {X Y : Type} [PermSet πΈ X] [PermSet πΈ Y] namespace Function.Equivariant /-- Equivariant functions preserve supports. -/ -lemma preserve_support {x : X} {f : X β Y} {S : Set πΈ} : Equivariant πΈ f β PermSet.HasSupport πΈ x S β PermSet.HasSupport πΈ (f x) S := by - intro hequi hsupp Ο hΟ +lemma preserve_support {x : X} {f : X β Y} [Equivariant πΈ f] {S : Set πΈ} : + PermSet.HasSupport πΈ x S β PermSet.HasSupport πΈ (f x) S := by + intro hsupp Ο hΟ calc - Ο β’ f x = f (Ο β’ x) := by rw [β hequi] + Ο β’ f x = f (Ο β’ x) := by rw [β equivariant πΈ f] _ = f x := by rw [hsupp hΟ] /-- Equivariant injective functions exactly preserve supports. -/ -lemma preserve_support_inj {x : X} {f : X β Y} {S : Set πΈ} : Equivariant πΈ f β f.Injective β (PermSet.HasSupport πΈ x S β PermSet.HasSupport πΈ (f x) S) := by - intro hequi hinj; constructor - Β· exact preserve_support πΈ hequi +lemma preserve_support_inj {x : X} {f : X β Y} [Equivariant πΈ f] {S : Set πΈ} : + f.Injective β (PermSet.HasSupport πΈ x S β PermSet.HasSupport πΈ (f x) S) := by + intro hinj; constructor + Β· exact preserve_support πΈ Β· intro hsupp Ο hΟ by_contra h - have : Ο β’ f x β f x := by rw [β hequi]; exact fun a => h (hinj a) + have : Ο β’ f x β f x := by rw [β equivariant πΈ f]; intro hcontra; exact h (hinj hcontra) have : Ο β’ f x = f x := hsupp hΟ contradiction end Function.Equivariant /-- HasSupport is an equivariant relation. -/ -lemma PermSet.support_equivariant : Rel.Equivariant πΈ (HasSupport πΈ : X β Set πΈ β Prop) := by - intro x S Ο hS Ο hΟ +instance PermSet.instHasSupportEquivariant : Rel.Equivariant πΈ (HasSupport πΈ : X β Set πΈ β Prop) := by + constructor; intro x S Ο hS Ο hΟ have hfix : (Οβ»ΒΉ * Ο * Ο) β fix πΈ S := by intro a ha calc @@ -154,52 +165,58 @@ variable {X Y : Type} [NominalSet πΈ X] [NominalSet πΈ Y] namespace Function.Equivariant /-- If f is equivariant, then supp (f x) β supp x. -/ -lemma supp_subset {x : X} {f : X β Y} : Equivariant πΈ f β NominalSet.supp πΈ (f x) β NominalSet.supp πΈ x := by - intro hequi +lemma supp_subset {x : X} {f : X β Y} [Equivariant πΈ f] : + NominalSet.supp πΈ (f x) β NominalSet.supp πΈ x := by apply NominalSet.support_subset_supp - Β· exact preserve_support πΈ hequi (NominalSet.supp_is_support πΈ) + Β· exact preserve_support πΈ (NominalSet.supp_is_support πΈ) Β· exact NominalSet.supp_finite πΈ /-- If f is equivariant and injective, then supp (f x) = supp x. -/ -lemma supp_eq_if_inj {x : X} {f : X β Y} : Equivariant πΈ f β Function.Injective f β NominalSet.supp πΈ (f x) = NominalSet.supp πΈ x := by - intro hequi hinj - simp [NominalSet.supp, preserve_support_inj πΈ hequi hinj] +lemma supp_eq_if_inj {x : X} {f : X β Y} [Equivariant πΈ f] : + Function.Injective f β NominalSet.supp πΈ (f x) = NominalSet.supp πΈ x := by + intro hinj + simp [NominalSet.supp, preserve_support_inj πΈ hinj] /-- If f is equivariant and a # x, then a # f x. -/ -lemma preserve_fresh {a : πΈ} {x : X} {f : X β Y} : Equivariant πΈ f β a # x β a # f x := by - intro hequi hx ha - exact hx ((supp_subset πΈ hequi) ha) +lemma preserve_fresh {a : πΈ} {x : X} {f : X β Y} [Equivariant πΈ f] : a # x β a # f x := by + intro hx ha + exact hx (supp_subset πΈ ha) /-- If f is equivariant and injective, then a # x iff a # f x. -/ -lemma preserve_fresh_inj {a : πΈ} {x : X} {f : X β Y} : Equivariant πΈ f β Function.Injective f β (a # x β a # f x) := by - intro hequi hinj - rw [NominalSet.IsFresh, NominalSet.IsFresh, supp_eq_if_inj πΈ hequi hinj] +lemma preserve_fresh_inj {a : πΈ} {x : X} {f : X β Y} [Equivariant πΈ f] : + Function.Injective f β (a # x β a # f x) := by + intro hinj + rw [NominalSet.IsFresh, NominalSet.IsFresh, supp_eq_if_inj πΈ hinj] end Function.Equivariant /-- If there is an equivariant surjection from a nominal set into an (FPerm πΈ)-Set, then that set is nominal. -/ -def NominalSet.fromEquivariantSurjective {X Y : Type} [NominalSet πΈ X] [PermSet πΈ Y] (f : X β Y) (hequi : Function.Equivariant πΈ f) (hsurj : Function.Surjective f) : NominalSet πΈ Y where +def NominalSet.ofEquivariantSurjective + {X Y : Type} [NominalSet πΈ X] [PermSet πΈ Y] + (f : X β Y) [Function.Equivariant πΈ f] (hsurj : Function.Surjective f) : + NominalSet πΈ Y where fin_supp := by intro y obtain β¨x, hxβ© := hsurj y use (NominalSet.supp πΈ x) constructor Β· rw [β hx] - exact Function.Equivariant.preserve_support πΈ hequi (supp_is_support πΈ) + exact Function.Equivariant.preserve_support πΈ (supp_is_support πΈ) Β· exact supp_finite πΈ /-- supp is an equivariant function. -/ -lemma NominalSet.supp_equivariant : Function.Equivariant πΈ (supp πΈ : X β Set πΈ) := by - intro x Ο; ext a; constructor +instance NominalSet.instSuppEquivariant : Function.Equivariant πΈ (supp πΈ : X β Set πΈ) := by + constructor; intro x Ο + ext a; constructor Β· apply support_subset_supp πΈ - Β· apply PermSet.support_equivariant + Β· rw [β Rel.equivariant πΈ (PermSet.HasSupport πΈ)] exact supp_is_support πΈ Β· apply Set.Finite.smul_set exact supp_finite πΈ Β· intro ha S hS have hsupp : PermSet.HasSupport πΈ x (Οβ»ΒΉ β’ S) := by rw [show x = Οβ»ΒΉ β’ Ο β’ x by exact eq_inv_smul_iff.mpr rfl] - apply PermSet.support_equivariant + rw [β Rel.equivariant πΈ (PermSet.HasSupport πΈ)] exact hS.out.left rw [Set.mem_smul_set_iff_inv_smul_mem] at ha suffices Οβ»ΒΉ β’ a β Οβ»ΒΉ β’ S by rw [Set.smul_mem_smul_set_iff] at this; assumption @@ -210,9 +227,9 @@ lemma NominalSet.supp_equivariant : Function.Equivariant πΈ (supp πΈ : X β exact hS.out.right /-- Freshness is an equivariant relation. -/ -lemma NominalSet.fresh_equivariant : Rel.Equivariant πΈ (NominalSet.IsFresh : πΈ β X β Prop) := by - intro x y Ο h - rwa [IsFresh, supp_equivariant, Set.smul_mem_smul_set_iff] +instance NominalSet.instFreshEquivariant : Rel.Equivariant πΈ (NominalSet.IsFresh : πΈ β X β Prop) := by + constructor; intro x y Ο h + rwa [IsFresh, Function.equivariant πΈ (supp πΈ), Set.smul_mem_smul_set_iff] end Nominal @@ -229,8 +246,8 @@ variable {X : Type} [NominalSet πΈ X] {R: Rel πΈ X} {x : X} -- We continue with a circular implication chain argument to show these equivalences. -private lemma for_fresh_iffβ : Equivariant πΈ R β (Π a, R a x) β (β a, a # x β§ R a x) := by - intro hequi h +private lemma for_fresh_iffβ : (Π a, R a x) β (β a, a # x β§ R a x) := by + intro h apply Set.Finite.infinite_compl at h simp at h have hinf : ({a | R a x} \ NominalSet.supp πΈ x).Infinite := Set.Infinite.diff h (NominalSet.supp_finite πΈ) @@ -238,17 +255,16 @@ private lemma for_fresh_iffβ : Equivariant πΈ R β (Π a, R a x) β (β a simp only [Set.mem_diff, Set.mem_setOf_eq] at ha use a; exact ha.symm -private lemma for_fresh_iffβ : Equivariant πΈ R β (β a, a # x β§ R a x) β (β a, a # x β R a x) := by - intro hequi h +private lemma for_fresh_iffβ [Rel.Equivariant πΈ R] : (β a, a # x β§ R a x) β (β a, a # x β R a x) := by + intro h obtain β¨a, β¨hfresha, haβ©β© := h intro b hfreshb - have hmem := hequi a x βΈ¨a, bβΈ© ha - rw [PermSet.atom_swap, Equiv.swap_apply_left] at hmem - rw [NominalSet.fresh_swap_fix πΈ hfresha hfreshb] at hmem - exact hmem + rw [Rel.equivariant πΈ R b x βΈ¨a, bβΈ©] + rw [PermSet.atom_swap, Equiv.swap_apply_right, NominalSet.fresh_swap_fix πΈ hfresha hfreshb] + exact ha -private lemma for_fresh_iffβ : Equivariant πΈ R β (β a, a # x β R a x) β (Π a, R a x) := by - intro hequi h +private lemma for_fresh_iffβ : (β a, a # x β R a x) β (Π a, R a x) := by + intro h have hsub : {a : πΈ | R a x}αΆ β NominalSet.supp πΈ x := by rw [Set.compl_subset_comm] intro a ha @@ -258,25 +274,25 @@ private lemma for_fresh_iffβ : Equivariant πΈ R β (β a, a # x β R a x) apply Set.Finite.subset (NominalSet.supp_finite πΈ) hsub /-- The quantifier in `Π a, a R x` is equivalent to "for any fresh `a`". -/ -lemma for_fresh_iff_exists : Equivariant πΈ R β ((Π a, R a x) β (β a, a # x β§ R a x)) := by - intro hequi; constructor +lemma for_fresh_iff_exists [Rel.Equivariant πΈ R] : ((Π a, R a x) β (β a, a # x β§ R a x)) := by + constructor Β· intro h - apply for_fresh_iffβ πΈ hequi + apply for_fresh_iffβ exact h Β· intro h - apply for_fresh_iffβ πΈ hequi - apply for_fresh_iffβ πΈ hequi + apply for_fresh_iffβ + apply for_fresh_iffβ exact h /-- The quantifier in `Π a, a R x` is equivalent to "for all fresh `a`". -/ -lemma for_fresh_iff_all : Equivariant πΈ R β ((Π a, R a x) β (β a, a # x β R a x)) := by - intro hequi; constructor +lemma for_fresh_iff_all [Rel.Equivariant πΈ R] : ((Π a, R a x) β (β a, a # x β R a x)) := by + constructor Β· intro h - apply for_fresh_iffβ πΈ hequi - apply for_fresh_iffβ πΈ hequi + apply for_fresh_iffβ + apply for_fresh_iffβ exact h Β· intro h - apply for_fresh_iffβ πΈ hequi + apply for_fresh_iffβ exact h end Rel.Equivariant @@ -305,6 +321,9 @@ notation:25 X " ββ[" A "] " Y => EquivariantMap A X Y variable {X Y Z : Type} [PermSet πΈ X] [PermSet πΈ Y] [PermSet πΈ Z] +instance EquivariantMap.toFunEquivariant (f : X ββ[πΈ] Y) : Function.Equivariant πΈ f.toFun := + f.equivariant + instance : FunLike (X ββ[πΈ] Y) X Y where coe := EquivariantMap.toFun coe_injective' f g h := by cases f; cases g; congr @@ -312,10 +331,10 @@ instance : FunLike (X ββ[πΈ] Y) X Y where namespace EquivariantMap /-- The identity function. -/ -def id : X ββ[πΈ] X := β¨_root_.id, id_equivariant πΈβ© +def id : X ββ[πΈ] X := β¨_root_.id, inferInstanceβ© /-- Function composition. -/ -def comp (f : Y ββ[πΈ] Z) (g : X ββ[πΈ] Y) : X ββ[πΈ] Z := β¨f β g, comp_equivariant πΈ f.equivariant g.equivariantβ© +def comp (f : Y ββ[πΈ] Z) (g : X ββ[πΈ] Y) : X ββ[πΈ] Z := β¨f.toFun β g.toFun, inferInstanceβ© @[simp] lemma id_app (x : X) : id πΈ x = x := rfl @@ -333,10 +352,6 @@ lemma ext {f g : X ββ[πΈ] Y} (h : β a, f a = g a) : f = g := end EquivariantMap -/-- Extended setoid definition that also requires the relation to be equivariant. -/ -class EquivariantSetoid (X : Type) [PermSet πΈ X] extends Setoid X where - equivariant : Rel.Equivariant πΈ r - end BundledFunction /-! @@ -349,7 +364,7 @@ section Equivalence /-- An equivalence where the function is equivariant. -/ structure EquivariantEquiv (X Y : Type) [PermSet πΈ X] [PermSet πΈ Y] extends Equiv X Y where toFun_equivariant : Function.Equivariant πΈ toFun - invFun_equivariant : Function.Equivariant πΈ invFun := Function.inv_equivariant πΈ left_inv right_inv toFun_equivariant + invFun_equivariant : Function.Equivariant πΈ invFun := Function.Equivariant.inv πΈ left_inv right_inv def Equivariant.Equiv.symm {πΈ X Y : Type} [Infinite πΈ] [Countable πΈ] [DecidableEq πΈ] [PermSet πΈ X] [PermSet πΈ Y] (equiv : EquivariantEquiv πΈ X Y) : EquivariantEquiv πΈ Y X := { toFun := equiv.invFun @@ -359,15 +374,24 @@ def Equivariant.Equiv.symm {πΈ X Y : Type} [Infinite πΈ] [Countable πΈ] [D right_inv := equiv.left_inv } +instance EquivariantEquiv.toFunEquivariant + {X Y : Type} [PermSet πΈ X] [PermSet πΈ Y] + (equiv : EquivariantEquiv πΈ X Y) : Function.Equivariant πΈ equiv.toFun := + equiv.toFun_equivariant + +instance EquivariantEquiv.invFunEquivariant + {X Y : Type} [PermSet πΈ X] [PermSet πΈ Y] + (equiv : EquivariantEquiv πΈ X Y) : Function.Equivariant πΈ equiv.invFun := + equiv.invFun_equivariant + /-- If an (FPerm πΈ)-Set is equivalent to a nominal set, it is also a nominal set. -/ -def NominalSet.fromEquivariantEquiv {X Y : Type} [PermSet πΈ X] [NominalSet πΈ Y] (equiv : EquivariantEquiv πΈ X Y) : NominalSet πΈ X := - NominalSet.fromEquivariantSurjective πΈ equiv.invFun equiv.invFun_equivariant equiv.symm.surjective +def NominalSet.ofEquivariantEquiv {X Y : Type} [PermSet πΈ X] [NominalSet πΈ Y] (equiv : EquivariantEquiv πΈ X Y) : NominalSet πΈ X := + NominalSet.ofEquivariantSurjective πΈ equiv.invFun equiv.symm.surjective /-- If two nominal sets are equivalent, the corresponding least supports are equal. -/ lemma EquivariantEquiv.supp_eq {X Y : Type} [NominalSet πΈ X] [NominalSet πΈ Y] (equiv : EquivariantEquiv πΈ X Y) (x : X) : NominalSet.supp πΈ x = NominalSet.supp πΈ (equiv.toFun x) := by symm apply Function.Equivariant.supp_eq_if_inj - Β· exact equiv.toFun_equivariant - Β· exact equiv.injective + exact equiv.injective end Equivalence |
