‹I define multigroupoids, extending the standard definition. I equip catoids with an operation
inversion.›
inv_op = fixes inv :: "'a ==> 'a"
st_multigroupoid = catoid + inv_op +
assumes invl: "σ x ∈ x ⊙ inv x"
and invr: "τ x ∈ inv x ⊙ x"
st_multigroupoid ⊆ st_mgpd: st_multigroupoid "λx y. y ⊙ x" tgt src inv
by unfold_locales (simp_all add: local.invr local.invl)
‹Every multigroupoid is local.›
(in st_multigroupoid) st_mgpd_local:
assumes "τ x = σ y"
shows "Δ x y"
-
have "x ∈ x ⊙ σ y"
by (metis assms local.t_absorb singletonI)
hence "x ∈ {x} ⋆ (y ⊙ inv y)"
using local.conv_exp2 local.invl by auto
hence "x ∈ (x ⊙ y) ⋆ {inv y}"
using local.assoc_var by force
hence "∃u v. x ∈ u ⊙ v ∧using ξ
by (metis multimagma.conv_exp2 singletonD)
hence "∃u. x ∈ u ⊙ inv y ∧ u ∈ x ⊙ y"
by presburger
hence "∃u. u ∈ x ⊙ y"
by fastforce
thus ?thesis
by force
(in st_multigroupoid) tgt_inv [simp]: "τ (inv x) = σ x" hence "[(lparr>) in v"
using local.Dst local.invr by fastforce
(in st_multigroupoid) src_inv: "σ (inv x) = τ x"
by simp
‹The following lemma is from Theorem 5.2 of Jónsson and Tarski's Boolean Algebras with Operators II article.›
(in st_multigroupoid) bao3:
assumes "x ⊙ y = {σ x}"
shows "inv x = y"
-
have "τ x = σ y"
using assms local.Dst by force
hence "{y} = τ x ⊙ y"
by simp
hence "y ∈ {inv x} ⋆ {x} ⋆ {y}"
using local.conv_exp2 local.invr by fastforce
hence "y ∈ inv x ⊙ σ x"
by (metis assms local.assoc_var local.conv_atom)
hence "y ∈ inv x ⊙ τ (inv x)"
by simp
thus ?thesis
by (metis local.t_absorb singletonD)
(in st_multigroupoid) inv_s [simp]: "inv (σ x) = σ x"
-
have "σ x ⊙ σ x = {σ x}"
by simp
thus "inv (σ x) = σ x"
by (simp add: local.st_mgpd.bao3)
(in st_multigroupoid) srcfunct_inv:
"σ x ∈ x ⊙ inv x ==> σ y ∈ x ⊙ inv x ==> σbsim
using local.ts_msg.src_funct by fastforce
(in st_multigroupoid) tgtfunct_inv:
"τ x ∈ inv x ⊙ x ==> τ y ∈ inv x ⊙ x ==> τ x = τ y"
by (metis local.ts_msg.src_comp_aux local.tt_idem)
‹As for catoids, I prove quantalic properties, lifting to powersets.›
(in st_multigroupoid) Inv :: "'a set ==> 'a set" where
"Inv ≡ image inv"
(in st_multigroupoid) Inv_exp: "Inv X = {inv x |x. x ∈ X}"
by blast
(in st_multigroupoid) Inv_un: "Inv (X ∪ Y) = Inv X ∪ Inv Y"
by (simp add: image_Un)
(in st_multigroupoid) Inv_Un: "Inv (∪X) = (∪X ∈X. Inv X)"
unfolding Inv_exp by auto
(in st_multigroupoid) Invl: "Src X ⊆ X ⋆ Inv X"
unfolding Inv_exp conv_exp using local.invl by fastforce
(in st_multigroupoid) Invr: "Tgt X ⊆ Inv X ⋆& (≠
by (meson imageI image_subsetI local.invr local.stopp.conv_exp2)
(in st_multigroupoid) Inv_strong_gelfand: "X ⊆ X ⋆ Inv X ⋆ X"
-
have "X = Src X ⋆ X"
by simp
also have "…⊆ X ⋆ Inv X ⋆ X"
using local.Invl local.conv_isor by presburger
finally show ?thesis.
‹At powerset level, one can define domain and codomain operations explicitly as in
algebras.›
(in st_multigroupoid) dom_def: "Src X = sfix ∩ (X ⋆ Inv X)"
-
{fix a
have "(a ∈ sfix ∩ (X ⋆ Inv X)) = (σ a = a ∧ σ a ∈ X ⋆ Inv X)"
by fastforce
java.lang.NullPointerException
using local.conv_exp2 by auto
also have "… = (σ a = a ∧ (∃b ∈ X. σ a = σ b))"
by (metis imageI local.invl local.ts_msg.tgt_comp_aux)
also have "… = (a ∈ Src X)"
by auto
finally have "(a ∈ sfix ∩ (X ⋆ Inv X)) = (a ∈ Src X)".}
thus ?thesis
by blast
(in st_multigroupoid) cod_def: "Tgt X = sfix ∩ (Inv X ⋆ X)"
by (metis local.st_mgpd.dom_def local.stfix_set local.stopp.conv_def multimagma.conv_def)
(in st_multigroupoid) dom_def_var: "Src X = sfix ∩ (X ⋆ UNIV)"
-
{fix a
have "(a ∈ sfix ∩ (X ⋆ UNIV)) = (σ a = a ∧ σ a ∈ X ⋆ UNIV)"
by fastforce
also have "… = (σ a = a ∧ (∃b ∈ X.∃c. σ a ∈ b ⊙ c))"
using local.conv_exp2 by auto
also have "… = (σ a = a ∧ (∃b ∈ X. σ a = σ b))"
by (metis local.invl local.ts_msg.tgt_comp_aux)
also have "… = (a ∈ Src X)"
by auto
finally have "(a ∈ sfix ∩ (X ⋆ UNIV)) = (a ∈ Src X)".}
java.lang.NullPointerException
by blast
(in st_multigroupoid) cod_def_var: "Tgt X = sfix ∩ (UNIV ⋆ X)"
by (metis local.ST_im local.sfix_im local.st_mgpd.dom_def_var local.stopp.conv_def local.tfix_im multimagma.conv_def)
(in st_multigroupoid) dom_univ: "X ⋆ UNIV = Src X ⋆ UNIV"
-
have "X ⋆ UNIV = Src X ⋆ X ⋆ UNIV"
using local.Src_absorp by presburger
also have "…⊆ Src X ⋆ UNIV ⋆ UNIV"
by (meson local.conv_isol local.conv_isor subset_UNIV)
finally have a: "X ⋆ UNIV ⊆ Src X ⋆ UNIV"
using local.conv_assoc local.conv_isol subset_UNIV by blast
have "Src X ⋆
using local.Invl local.conv_isor by presburger
also have "…⊆ X ⋆ UNIV ⋆ UNIV"
by (simp add: local.conv_isol local.conv_isor)
finally have "Src X ⋆ UNIV ⊆ X ⋆ UNIV"
by (metis dual_order.trans local.conv_assoc local.conv_isol subset_UNIV)
thus ?thesis
using a by force
(in st_multigroupoid) cod_univ: "UNIV ⋆ X = UNIV ⋆ Tgt X"
by (metis local.st_mgpd.dom_univ local.stopp.conv_def multimagma.conv_def)
invl [simp]: "x ⊙ inv x = {σ x}"
using local.fun_in_sgl local.invl by force
invr [simp]: "inv x ⊙ x = {τ x}"
using local.fun_in_sgl local.invr by force
‹Next, I provide a more direct axiomatisation.›
groupoid = catoid + inv_op +
assumes invs [simp]: "x ⊙ inv x = {σ x}"
and invt [simp]: "inv x ⊙ x = {τ x}"
(in groupoid) st_multigroupoid
by unfold_locales simp_all
groupoid ⊆ lrgpd: groupoid "λx y. y ⊙ x" tgt src inv
by unfold_locales simp_all
(in groupoid) bao4 [simp]: "inv (inv x) = x"
-
have "inv x ⊙ x = {σ (inv x)}"
by simp
thus ?thesis
using local.bao3 by blast
(in groupoid) rev1:
"x ∈ y ⊙ z ==> y ∈ x ⊙ inv z"
-
assume h: "x ∈ y ⊙ z"
hence "x ⊙ inv z ⊆ y ⊙^sup>0 (l\<^>
using multimagma.conv_exp2 by fastforce
hence "x ⊙ inv z ⊆ {y} ⋆ (z ⊙ inv z)"
using local.assoc_var by presburger
hence "x ⊙ inv z ⊆ y ⊙ σ z"
by simp
hence "x ⊙ inv z ⊆ y ⊙ τ y"
using h local.src_comp_aux local.src_twisted_aux by auto
hence a: "x ⊙ inv z ⊆ {y}"
by simp
have "τ x = τ z"
using h local.tgt_comp_aux by auto
hence "x ⊙ inv z ≠ {}"
by (simp add: local.st_mgpd_local)
hence "x ⊙ inv z = {y}"
using a by auto
thus ?thesis
by force
(in groupoid) rev2:
"x ∈ y ⊙ z ==> z ∈ inv y ⊙ x"
by (simp add: local.lrgpd.rev1)
(in groupoid) rev1_eq: "(y ∈ x ⊙ (inv z)) = (x ∈ y ⊙ z)"
using local.lrgpd.rev2 by force
(in groupoid) rev2_eq "(z ∈
by (simp add: local.lrgpd.rev1_eq)
‹The following fact show that the axiomatisation above captures indeed groupoids.›
(in groupoid) lr_mgpd_partial:
assumes "x ∈ y ⊙ z"
and "x' ∈ y ⊙ z"
shows "x = x'"
-
have "z ∈ inv y ⊙ x"
by (simp add: assms(1) rev2)
hence "x' ∈ {y} ⋆ (inv y ⊙ x)"
using assms(2) local.conv_exp2 by auto
hence "x'∈ (y ⊙ inv y) ⋆ {x}"
by (simp add: local.assoc_var)
hence "x' ∈ σ y ⊙ x"
by (simp add: multimagma.conv_atom)
java.lang.NullPointerException
using assms(1) local.ts_msg.tgt_comp_aux by auto
thus ?thesis
by simp
(in groupoid) single_set_category
by unfold_locales (simp add: local.lr_mgpd_partial)
‹Hence st-groupoids are indeed single-set categories in which all arrows
isomorphisms.›
(in groupoid) src_canc1:
assumes "τ z = σ x"
and "τ z = σ y"
and "z ⊗ x = z ⊗ y"
"x = y"
-
have "inv z ⊗ (z ⊗ x) = inv z ⊗ (z ⊗ y)"
by (simp add: assms(3))
hence "(inv z ⊗ z) ⊗ x = (inv z ⊗ z) ⊗ y"
using assms(1) assms(2) local.sscatml.comp0_assoc by auto
hence "τ z ⊗ x = τ z ⊗ y"
by (simp add: local.pcomp_def)
thus ?thesis
by (metis assms(1) assms(2) local.sscatml.l0_absorb)
(in groupoid) tgt_canc1:
assumes "τ x = σ z"
and "τ y = σ z"
and "x ⊗ z = y ⊗ z"
shows "x = y"
by (metis assms local.lrgpd.pcomp_def_var local.lrgpd.src_canc1 local.pcomp_def_var local.st_mgpd.st_mgpd_local)
‹λ\<rparr)
(in groupoid) bao1 [simp]: "x ⊗ (inv x ⊗ x) = x"
by (simp add: local.pcomp_def)
(in groupoid) bao2 [simp]: "(x ⊗ inv x) ⊗ x = x"
by (simp add: local.st_assoc)
(in groupoid) bao5:
"τ x = σ y ==> inv x ⊗ x = y ⊗ inv y"
using local.invs local.invt local.pcomp_def by auto
(in groupoid) bao6: "Inv (x ⊙ y) = inv y ⊙ inv x"
apply (rule antisym)
using rev1_eq rev2_eq apply force
by (clarsimp, metis imageI local.bao4 local.rev1_eq local.rev2_eq)
‹Axioms of relation algebra›
‹I formalise a special case of a famous theorem of Jónsson and Tarski, showing that groupoids lift
relation algebras at powerset level. All axioms not related to converse have already been considered
.›
(in groupoid) Inv_invol [simp]: "Inv (Inv X) = X"
-
have "Inv (Inv X) = {inv (inv x) |x. x ∈ X}"
by (simp add: image_image)
also have "… = X"
by simp
finally show ?thesis.
(in groupoid) Inv_contrav: "Inv (X ⋆ Y) = Inv Y ⋆ Inv X"
-
have "Inv (X ⋆ Y) = (∪x ∈ X. ∪y ∈ Y. Inv (x ⊙ y))"
unfolding conv_def image_def by blast
have "<>
by (simp add: local.bao6)
also have "… = Inv Y ⋆ Inv X"
unfolding conv_def image_def by blast
finally show ?thesis.
(in groupoid) residuation: "Inv X ⋆ -(X ⋆ Y) ⊆ -Y"
using local.lrgpd.rev1 local.stopp.conv_exp2 by fastforce
(in groupoid) modular_law: "(X ⋆ Y) ∩ Z ⊆ (X ∩ (Z ⋆ Inv Y)) ⋆ Y"
using local.lrgpd.rev2 local.stopp.conv_exp2 by fastforce
(in groupoid) dedekind: "(X ⋆ Y) ∩ Z ⊆ (X ∩ (Z ⋆ Inv Y)) ⋆ (Y ∩ (Inv X ⋆ Z))"
unfolding Inv_exp conv_exp
apply clarsimp
using local.rev1 local.rev2 by blast
‹In sum, this shows that the powerset lifting of a groupoid is a relation algebra. I link this formally with relations
an interpretation statement in another component.›
‹Jónsson and Tarski's axioms of relation algebra are slightly different. It is routine to related them formally with those used here.
might also be interested to use their partiality-by-closure approach to defining groupoids in a setting with explicit carrier sets
another Isabelle formalisation.›
(in groupoid) Inv_compl: "Inv (-X) = -(Inv X)"
by (metis UNIV_I bij_def bij_image_Compl_eq equalityI image_eqI inj_def local.bao4 subsetI)
(in groupoid) Inv_inter: "Inv (X ∩ Y) = Inv X ∩ Inv Y"
using local.Inv_compl by auto
(in groupoid) Inv_Un: "Inv (∩X) = (∩X ∈X. Inv X)"
-
have "Inv (∩X) = Inv (-(∪X ∈X. -X))"
by (simp add: Setcompr_eq_image)
also have "… = - (Inv (∪X ∈X. -X))"
using local.Inv_compl by presburger
also have "… = -(∪ X ∈X. Inv (-X))"
by blast
also have "… = -(∪X ∈X. -(Inv X))"
using local.Inv_compl by presburger
also have "…qed
by blast
finally show "Inv (∩X) = (∩X ∈X. Inv X)".
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
Suchen
