src/HOL/Algebra/Coset.thy
changeset 14666 65f8680c3f16
parent 14651 02b8f3bcf7fe
child 14706 71590b7733b7
equal deleted inserted replaced
14665:d2e5df3d1201 14666:65f8680c3f16
     5 
     5 
     6 header{*Theory of Cosets*}
     6 header{*Theory of Cosets*}
     7 
     7 
     8 theory Coset = Group + Exponent:
     8 theory Coset = Group + Exponent:
     9 
     9 
    10 declare (in group) l_inv [simp]  r_inv [simp] 
    10 declare (in group) l_inv [simp] and r_inv [simp]
    11 
    11 
    12 constdefs (structure G)
    12 constdefs (structure G)
    13   r_coset    :: "[_,'a set, 'a] => 'a set"    
    13   r_coset    :: "[_,'a set, 'a] => 'a set"
    14    "r_coset G H a == (% x. x \<otimes> a) ` H"
    14   "r_coset G H a == (% x. x \<otimes> a) ` H"
    15 
    15 
    16   l_coset    :: "[_, 'a, 'a set] => 'a set"
    16   l_coset    :: "[_, 'a, 'a set] => 'a set"
    17    "l_coset G a H == (% x. a \<otimes> x) ` H"
    17   "l_coset G a H == (% x. a \<otimes> x) ` H"
    18 
    18 
    19   rcosets  :: "[_, 'a set] => ('a set)set"
    19   rcosets  :: "[_, 'a set] => ('a set)set"
    20    "rcosets G H == r_coset G H ` (carrier G)"
    20   "rcosets G H == r_coset G H ` (carrier G)"
    21 
    21 
    22   set_mult  :: "[_, 'a set ,'a set] => 'a set"
    22   set_mult  :: "[_, 'a set ,'a set] => 'a set"
    23    "set_mult G H K == (%(x,y). x \<otimes> y) ` (H \<times> K)"
    23   "set_mult G H K == (%(x,y). x \<otimes> y) ` (H \<times> K)"
    24 
    24 
    25   set_inv   :: "[_,'a set] => 'a set"
    25   set_inv   :: "[_,'a set] => 'a set"
    26    "set_inv G H == m_inv G ` H"
    26   "set_inv G H == m_inv G ` H"
    27 
    27 
    28   normal     :: "['a set, _] => bool"       (infixl "<|" 60)
    28   normal     :: "['a set, _] => bool"       (infixl "<|" 60)
    29    "normal H G == subgroup H G & 
    29   "normal H G == subgroup H G &
    30                   (\<forall>x \<in> carrier G. r_coset G H x = l_coset G x H)"
    30                   (\<forall>x \<in> carrier G. r_coset G H x = l_coset G x H)"
    31 
    31 
    32 syntax (xsymbols)
    32 syntax (xsymbols)
    33   normal  :: "['a set, ('a,'b) monoid_scheme] => bool" (infixl "\<lhd>" 60)
    33   normal  :: "['a set, ('a,'b) monoid_scheme] => bool" (infixl "\<lhd>" 60)
    34 
    34 
    54      "[|f \<in> A\<rightarrow>B; inj_on f A; finite A; finite B|] ==> card(A) <= card(B)"
    54      "[|f \<in> A\<rightarrow>B; inj_on f A; finite A; finite B|] ==> card(A) <= card(B)"
    55 apply (rule card_inj_on_le)
    55 apply (rule card_inj_on_le)
    56 apply (auto simp add: Pi_def)
    56 apply (auto simp add: Pi_def)
    57 done
    57 done
    58 
    58 
    59 lemma card_bij: 
    59 lemma card_bij:
    60      "[|f \<in> A\<rightarrow>B; inj_on f A; 
    60      "[|f \<in> A\<rightarrow>B; inj_on f A;
    61         g \<in> B\<rightarrow>A; inj_on g B; finite A; finite B|] ==> card(A) = card(B)"
    61         g \<in> B\<rightarrow>A; inj_on g B; finite A; finite B|] ==> card(A) = card(B)"
    62 by (blast intro: card_inj order_antisym) 
    62 by (blast intro: card_inj order_antisym)
    63 
    63 
    64 
    64 
    65 subsection{*Lemmas Using Locale Constants*}
    65 subsection {*Lemmas Using *}
    66 
    66 
    67 lemma (in coset) r_coset_eq: "H #> a = {b . \<exists>h\<in>H. h \<otimes> a = b}"
    67 lemma (in coset) r_coset_eq: "H #> a = {b . \<exists>h\<in>H. h \<otimes> a = b}"
    68 by (auto simp add: rcos_def r_coset_def)
    68 by (auto simp add: rcos_def r_coset_def)
    69 
    69 
    70 lemma (in coset) l_coset_eq: "a <# H = {b . \<exists>h\<in>H. a \<otimes> h = b}"
    70 lemma (in coset) l_coset_eq: "a <# H = {b . \<exists>h\<in>H. a \<otimes> h = b}"
    75 
    75 
    76 lemma (in coset) set_mult_eq: "H <#> K = {c . \<exists>h\<in>H. \<exists>k\<in>K. c = h \<otimes> k}"
    76 lemma (in coset) set_mult_eq: "H <#> K = {c . \<exists>h\<in>H. \<exists>k\<in>K. c = h \<otimes> k}"
    77 by (simp add: setmult_def set_mult_def image_def)
    77 by (simp add: setmult_def set_mult_def image_def)
    78 
    78 
    79 lemma (in coset) coset_mult_assoc:
    79 lemma (in coset) coset_mult_assoc:
    80      "[| M <= carrier G; g \<in> carrier G; h \<in> carrier G |]  
    80      "[| M <= carrier G; g \<in> carrier G; h \<in> carrier G |]
    81       ==> (M #> g) #> h = M #> (g \<otimes> h)"
    81       ==> (M #> g) #> h = M #> (g \<otimes> h)"
    82 by (force simp add: r_coset_eq m_assoc)
    82 by (force simp add: r_coset_eq m_assoc)
    83 
    83 
    84 lemma (in coset) coset_mult_one [simp]: "M <= carrier G ==> M #> \<one> = M"
    84 lemma (in coset) coset_mult_one [simp]: "M <= carrier G ==> M #> \<one> = M"
    85 by (force simp add: r_coset_eq)
    85 by (force simp add: r_coset_eq)
    86 
    86 
    87 lemma (in coset) coset_mult_inv1:
    87 lemma (in coset) coset_mult_inv1:
    88      "[| M #> (x \<otimes> (inv y)) = M;  x \<in> carrier G ; y \<in> carrier G; 
    88      "[| M #> (x \<otimes> (inv y)) = M;  x \<in> carrier G ; y \<in> carrier G;
    89          M <= carrier G |] ==> M #> x = M #> y"
    89          M <= carrier G |] ==> M #> x = M #> y"
    90 apply (erule subst [of concl: "%z. M #> x = z #> y"])
    90 apply (erule subst [of concl: "%z. M #> x = z #> y"])
    91 apply (simp add: coset_mult_assoc m_assoc)
    91 apply (simp add: coset_mult_assoc m_assoc)
    92 done
    92 done
    93 
    93 
    94 lemma (in coset) coset_mult_inv2:
    94 lemma (in coset) coset_mult_inv2:
    95      "[| M #> x = M #> y;  x \<in> carrier G;  y \<in> carrier G;  M <= carrier G |]  
    95      "[| M #> x = M #> y;  x \<in> carrier G;  y \<in> carrier G;  M <= carrier G |]
    96       ==> M #> (x \<otimes> (inv y)) = M "
    96       ==> M #> (x \<otimes> (inv y)) = M "
    97 apply (simp add: coset_mult_assoc [symmetric])
    97 apply (simp add: coset_mult_assoc [symmetric])
    98 apply (simp add: coset_mult_assoc)
    98 apply (simp add: coset_mult_assoc)
    99 done
    99 done
   100 
   100 
   108 text{*Locales don't currently work with @{text rule_tac}, so we
   108 text{*Locales don't currently work with @{text rule_tac}, so we
   109 must prove this lemma separately.*}
   109 must prove this lemma separately.*}
   110 lemma (in coset) solve_equation:
   110 lemma (in coset) solve_equation:
   111     "\<lbrakk>subgroup H G; x \<in> H; y \<in> H\<rbrakk> \<Longrightarrow> \<exists>h\<in>H. h \<otimes> x = y"
   111     "\<lbrakk>subgroup H G; x \<in> H; y \<in> H\<rbrakk> \<Longrightarrow> \<exists>h\<in>H. h \<otimes> x = y"
   112 apply (rule bexI [of _ "y \<otimes> (inv x)"])
   112 apply (rule bexI [of _ "y \<otimes> (inv x)"])
   113 apply (auto simp add: subgroup.m_closed subgroup.m_inv_closed m_assoc 
   113 apply (auto simp add: subgroup.m_closed subgroup.m_inv_closed m_assoc
   114                       subgroup.subset [THEN subsetD])
   114                       subgroup.subset [THEN subsetD])
   115 done
   115 done
   116 
   116 
   117 lemma (in coset) coset_join2:
   117 lemma (in coset) coset_join2:
   118      "[| x \<in> carrier G;  subgroup H G;  x\<in>H |] ==> H #> x = H"
   118      "[| x \<in> carrier G;  subgroup H G;  x\<in>H |] ==> H #> x = H"
   131 by (auto simp add: setrcos_eq)
   131 by (auto simp add: setrcos_eq)
   132 
   132 
   133 
   133 
   134 text{*Really needed?*}
   134 text{*Really needed?*}
   135 lemma (in coset) transpose_inv:
   135 lemma (in coset) transpose_inv:
   136      "[| x \<otimes> y = z;  x \<in> carrier G;  y \<in> carrier G;  z \<in> carrier G |]  
   136      "[| x \<otimes> y = z;  x \<in> carrier G;  y \<in> carrier G;  z \<in> carrier G |]
   137       ==> (inv x) \<otimes> z = y"
   137       ==> (inv x) \<otimes> z = y"
   138 by (force simp add: m_assoc [symmetric])
   138 by (force simp add: m_assoc [symmetric])
   139 
   139 
   140 lemma (in coset) repr_independence:
   140 lemma (in coset) repr_independence:
   141      "[| y \<in> H #> x;  x \<in> carrier G; subgroup H G |] ==> H #> x = H #> y"
   141      "[| y \<in> H #> x;  x \<in> carrier G; subgroup H G |] ==> H #> x = H #> y"
   142 by (auto simp add: r_coset_eq m_assoc [symmetric] 
   142 by (auto simp add: r_coset_eq m_assoc [symmetric]
   143                    subgroup.subset [THEN subsetD]
   143                    subgroup.subset [THEN subsetD]
   144                    subgroup.m_closed solve_equation)
   144                    subgroup.m_closed solve_equation)
   145 
   145 
   146 lemma (in coset) rcos_self: "[| x \<in> carrier G; subgroup H G |] ==> x \<in> H #> x"
   146 lemma (in coset) rcos_self: "[| x \<in> carrier G; subgroup H G |] ==> x \<in> H #> x"
   147 apply (simp add: r_coset_eq)
   147 apply (simp add: r_coset_eq)
   148 apply (blast intro: l_one subgroup.subset [THEN subsetD] 
   148 apply (blast intro: l_one subgroup.subset [THEN subsetD]
   149                     subgroup.one_closed)
   149                     subgroup.one_closed)
   150 done
   150 done
   151 
   151 
   152 
   152 
   153 subsection{*normal subgroups*}
   153 subsection {* Normal subgroups *}
   154 
   154 
   155 (*????????????????
   155 (*????????????????
   156 text "Allows use of theorems proved in the locale coset"
   156 text "Allows use of theorems proved in the locale coset"
   157 lemma subgroup_imp_coset: "subgroup H G ==> coset G"
   157 lemma subgroup_imp_coset: "subgroup H G ==> coset G"
   158 apply (drule subgroup_imp_group)
   158 apply (drule subgroup_imp_group)
   159 apply (simp add: group_def coset_def)  
   159 apply (simp add: group_def coset_def)
   160 done
   160 done
   161 *)
   161 *)
   162 
   162 
   163 lemma normal_imp_subgroup: "H <| G ==> subgroup H G"
   163 lemma normal_imp_subgroup: "H <| G ==> subgroup H G"
   164 by (simp add: normal_def)
   164 by (simp add: normal_def)
   178 by (simp add: lcos_def rcos_def normal_def)
   178 by (simp add: lcos_def rcos_def normal_def)
   179 
   179 
   180 lemma (in coset) normal_inv_op_closed1:
   180 lemma (in coset) normal_inv_op_closed1:
   181      "\<lbrakk>H \<lhd> G; x \<in> carrier G; h \<in> H\<rbrakk> \<Longrightarrow> (inv x) \<otimes> h \<otimes> x \<in> H"
   181      "\<lbrakk>H \<lhd> G; x \<in> carrier G; h \<in> H\<rbrakk> \<Longrightarrow> (inv x) \<otimes> h \<otimes> x \<in> H"
   182 apply (auto simp add: l_coset_eq r_coset_eq normal_iff)
   182 apply (auto simp add: l_coset_eq r_coset_eq normal_iff)
   183 apply (drule bspec, assumption) 
   183 apply (drule bspec, assumption)
   184 apply (drule equalityD1 [THEN subsetD], blast, clarify)
   184 apply (drule equalityD1 [THEN subsetD], blast, clarify)
   185 apply (simp add: m_assoc subgroup.subset [THEN subsetD])
   185 apply (simp add: m_assoc subgroup.subset [THEN subsetD])
   186 apply (erule subst)
   186 apply (erule subst)
   187 apply (simp add: m_assoc [symmetric] subgroup.subset [THEN subsetD])
   187 apply (simp add: m_assoc [symmetric] subgroup.subset [THEN subsetD])
   188 done
   188 done
   189 
   189 
   190 lemma (in coset) normal_inv_op_closed2:
   190 lemma (in coset) normal_inv_op_closed2:
   191      "\<lbrakk>H \<lhd> G; x \<in> carrier G; h \<in> H\<rbrakk> \<Longrightarrow> x \<otimes> h \<otimes> (inv x) \<in> H"
   191      "\<lbrakk>H \<lhd> G; x \<in> carrier G; h \<in> H\<rbrakk> \<Longrightarrow> x \<otimes> h \<otimes> (inv x) \<in> H"
   192 apply (drule normal_inv_op_closed1 [of H "(inv x)"]) 
   192 apply (drule normal_inv_op_closed1 [of H "(inv x)"])
   193 apply auto
   193 apply auto
   194 done
   194 done
   195 
   195 
   196 lemma (in coset) lcos_m_assoc:
   196 lemma (in coset) lcos_m_assoc:
   197      "[| M <= carrier G; g \<in> carrier G; h \<in> carrier G |]  
   197      "[| M <= carrier G; g \<in> carrier G; h \<in> carrier G |]
   198       ==> g <# (h <# M) = (g \<otimes> h) <# M"
   198       ==> g <# (h <# M) = (g \<otimes> h) <# M"
   199 by (force simp add: l_coset_eq m_assoc)
   199 by (force simp add: l_coset_eq m_assoc)
   200 
   200 
   201 lemma (in coset) lcos_mult_one: "M <= carrier G ==> \<one> <# M = M"
   201 lemma (in coset) lcos_mult_one: "M <= carrier G ==> \<one> <# M = M"
   202 by (force simp add: l_coset_eq)
   202 by (force simp add: l_coset_eq)
   206 by (auto simp add: l_coset_eq subsetD)
   206 by (auto simp add: l_coset_eq subsetD)
   207 
   207 
   208 lemma (in coset) l_coset_swap:
   208 lemma (in coset) l_coset_swap:
   209      "[| y \<in> x <# H;  x \<in> carrier G;  subgroup H G |] ==> x \<in> y <# H"
   209      "[| y \<in> x <# H;  x \<in> carrier G;  subgroup H G |] ==> x \<in> y <# H"
   210 proof (simp add: l_coset_eq)
   210 proof (simp add: l_coset_eq)
   211   assume "\<exists>h\<in>H. x \<otimes> h = y" 
   211   assume "\<exists>h\<in>H. x \<otimes> h = y"
   212     and x: "x \<in> carrier G" 
   212     and x: "x \<in> carrier G"
   213     and sb: "subgroup H G"
   213     and sb: "subgroup H G"
   214   then obtain h' where h': "h' \<in> H & x \<otimes> h' = y" by blast
   214   then obtain h' where h': "h' \<in> H & x \<otimes> h' = y" by blast
   215   show "\<exists>h\<in>H. y \<otimes> h = x"
   215   show "\<exists>h\<in>H. y \<otimes> h = x"
   216   proof
   216   proof
   217     show "y \<otimes> inv h' = x" using h' x sb
   217     show "y \<otimes> inv h' = x" using h' x sb
   221   qed
   221   qed
   222 qed
   222 qed
   223 
   223 
   224 lemma (in coset) l_coset_carrier:
   224 lemma (in coset) l_coset_carrier:
   225      "[| y \<in> x <# H;  x \<in> carrier G;  subgroup H G |] ==> y \<in> carrier G"
   225      "[| y \<in> x <# H;  x \<in> carrier G;  subgroup H G |] ==> y \<in> carrier G"
   226 by (auto simp add: l_coset_eq m_assoc 
   226 by (auto simp add: l_coset_eq m_assoc
   227                    subgroup.subset [THEN subsetD] subgroup.m_closed)
   227                    subgroup.subset [THEN subsetD] subgroup.m_closed)
   228 
   228 
   229 lemma (in coset) l_repr_imp_subset:
   229 lemma (in coset) l_repr_imp_subset:
   230   assumes y: "y \<in> x <# H" and x: "x \<in> carrier G" and sb: "subgroup H G" 
   230   assumes y: "y \<in> x <# H" and x: "x \<in> carrier G" and sb: "subgroup H G"
   231   shows "y <# H \<subseteq> x <# H"
   231   shows "y <# H \<subseteq> x <# H"
   232 proof -
   232 proof -
   233   from y
   233   from y
   234   obtain h' where "h' \<in> H" "x \<otimes> h' = y" by (auto simp add: l_coset_eq)
   234   obtain h' where "h' \<in> H" "x \<otimes> h' = y" by (auto simp add: l_coset_eq)
   235   thus ?thesis using x sb
   235   thus ?thesis using x sb
   236     by (auto simp add: l_coset_eq m_assoc 
   236     by (auto simp add: l_coset_eq m_assoc
   237                        subgroup.subset [THEN subsetD] subgroup.m_closed)
   237                        subgroup.subset [THEN subsetD] subgroup.m_closed)
   238 qed
   238 qed
   239 
   239 
   240 lemma (in coset) l_repr_independence:
   240 lemma (in coset) l_repr_independence:
   241   assumes y: "y \<in> x <# H" and x: "x \<in> carrier G" and sb: "subgroup H G" 
   241   assumes y: "y \<in> x <# H" and x: "x \<in> carrier G" and sb: "subgroup H G"
   242   shows "x <# H = y <# H"
   242   shows "x <# H = y <# H"
   243 proof 
   243 proof
   244   show "x <# H \<subseteq> y <# H"
   244   show "x <# H \<subseteq> y <# H"
   245     by (rule l_repr_imp_subset, 
   245     by (rule l_repr_imp_subset,
   246         (blast intro: l_coset_swap l_coset_carrier y x sb)+)
   246         (blast intro: l_coset_swap l_coset_carrier y x sb)+)
   247   show "y <# H \<subseteq> x <# H" by (rule l_repr_imp_subset [OF y x sb]) 
   247   show "y <# H \<subseteq> x <# H" by (rule l_repr_imp_subset [OF y x sb])
   248 qed
   248 qed
   249 
   249 
   250 lemma (in coset) setmult_subset_G:
   250 lemma (in coset) setmult_subset_G:
   251      "[| H <= carrier G; K <= carrier G |] ==> H <#> K <= carrier G"
   251      "[| H <= carrier G; K <= carrier G |] ==> H <#> K <= carrier G"
   252 by (auto simp add: set_mult_eq subsetD)
   252 by (auto simp add: set_mult_eq subsetD)
   253 
   253 
   254 lemma (in coset) subgroup_mult_id: "subgroup H G ==> H <#> H = H"
   254 lemma (in coset) subgroup_mult_id: "subgroup H G ==> H <#> H = H"
   255 apply (auto simp add: subgroup.m_closed set_mult_eq Sigma_def image_def)
   255 apply (auto simp add: subgroup.m_closed set_mult_eq Sigma_def image_def)
   256 apply (rule_tac x = x in bexI)
   256 apply (rule_tac x = x in bexI)
   257 apply (rule bexI [of _ "\<one>"])
   257 apply (rule bexI [of _ "\<one>"])
   258 apply (auto simp add: subgroup.m_closed subgroup.one_closed 
   258 apply (auto simp add: subgroup.m_closed subgroup.one_closed
   259                       r_one subgroup.subset [THEN subsetD])
   259                       r_one subgroup.subset [THEN subsetD])
   260 done
   260 done
   261 
   261 
   262 
   262 
   263 (* set of inverses of an r_coset *)
   263 text {* Set of inverses of an @{text r_coset}. *}
       
   264 
   264 lemma (in coset) rcos_inv:
   265 lemma (in coset) rcos_inv:
   265   assumes normalHG: "H <| G"
   266   assumes normalHG: "H <| G"
   266       and xinG:     "x \<in> carrier G"
   267       and xinG:     "x \<in> carrier G"
   267   shows "set_inv G (H #> x) = H #> (inv x)"
   268   shows "set_inv G (H #> x) = H #> (inv x)"
   268 proof -
   269 proof -
   269   have H_subset: "H <= carrier G" 
   270   have H_subset: "H <= carrier G"
   270     by (rule subgroup.subset [OF normal_imp_subgroup, OF normalHG])
   271     by (rule subgroup.subset [OF normal_imp_subgroup, OF normalHG])
   271   show ?thesis
   272   show ?thesis
   272   proof (auto simp add: r_coset_eq image_def set_inv_def)
   273   proof (auto simp add: r_coset_eq image_def set_inv_def)
   273     fix h
   274     fix h
   274     assume "h \<in> H"
   275     assume "h \<in> H"
   275       hence "((inv x) \<otimes> (inv h) \<otimes> x) \<otimes> inv x = inv (h \<otimes> x)"
   276       hence "((inv x) \<otimes> (inv h) \<otimes> x) \<otimes> inv x = inv (h \<otimes> x)"
   276 	by (simp add: xinG m_assoc inv_mult_group H_subset [THEN subsetD])
   277         by (simp add: xinG m_assoc inv_mult_group H_subset [THEN subsetD])
   277       thus "\<exists>j\<in>H. j \<otimes> inv x = inv (h \<otimes> x)" 
   278       thus "\<exists>j\<in>H. j \<otimes> inv x = inv (h \<otimes> x)"
   278        using prems
   279        using prems
   279 	by (blast intro: normal_inv_op_closed1 normal_imp_subgroup 
   280         by (blast intro: normal_inv_op_closed1 normal_imp_subgroup
   280 			 subgroup.m_inv_closed)
   281                          subgroup.m_inv_closed)
   281   next
   282   next
   282     fix h
   283     fix h
   283     assume "h \<in> H"
   284     assume "h \<in> H"
   284       hence eq: "(x \<otimes> (inv h) \<otimes> (inv x)) \<otimes> x = x \<otimes> inv h"
   285       hence eq: "(x \<otimes> (inv h) \<otimes> (inv x)) \<otimes> x = x \<otimes> inv h"
   285         by (simp add: xinG m_assoc H_subset [THEN subsetD])
   286         by (simp add: xinG m_assoc H_subset [THEN subsetD])
   286       hence "(\<exists>j\<in>H. j \<otimes> x = inv  (h \<otimes> (inv x))) \<and> h \<otimes> inv x = inv (inv (h \<otimes> (inv x)))"
   287       hence "(\<exists>j\<in>H. j \<otimes> x = inv  (h \<otimes> (inv x))) \<and> h \<otimes> inv x = inv (inv (h \<otimes> (inv x)))"
   287        using prems
   288        using prems
   288 	by (simp add: m_assoc inv_mult_group H_subset [THEN subsetD],
   289         by (simp add: m_assoc inv_mult_group H_subset [THEN subsetD],
   289             blast intro: eq normal_inv_op_closed2 normal_imp_subgroup 
   290             blast intro: eq normal_inv_op_closed2 normal_imp_subgroup
   290 			 subgroup.m_inv_closed)
   291                          subgroup.m_inv_closed)
   291       thus "\<exists>y. (\<exists>h\<in>H. h \<otimes> x = y) \<and> h \<otimes> inv x = inv y" ..
   292       thus "\<exists>y. (\<exists>h\<in>H. h \<otimes> x = y) \<and> h \<otimes> inv x = inv y" ..
   292   qed
   293   qed
   293 qed
   294 qed
   294 
   295 
   295 (*The old proof is something like this, but the rule_tac calls make
   296 (*The old proof is something like this, but the rule_tac calls make
   312 lemma (in coset) rcos_inv2:
   313 lemma (in coset) rcos_inv2:
   313      "[| H <| G; K \<in> rcosets G H; x \<in> K |] ==> set_inv G K = H #> (inv x)"
   314      "[| H <| G; K \<in> rcosets G H; x \<in> K |] ==> set_inv G K = H #> (inv x)"
   314 apply (simp add: setrcos_eq, clarify)
   315 apply (simp add: setrcos_eq, clarify)
   315 apply (subgoal_tac "x : carrier G")
   316 apply (subgoal_tac "x : carrier G")
   316  prefer 2
   317  prefer 2
   317  apply (blast dest: r_coset_subset_G subgroup.subset normal_imp_subgroup) 
   318  apply (blast dest: r_coset_subset_G subgroup.subset normal_imp_subgroup)
   318 apply (drule repr_independence)
   319 apply (drule repr_independence)
   319   apply assumption
   320   apply assumption
   320  apply (erule normal_imp_subgroup)
   321  apply (erule normal_imp_subgroup)
   321 apply (simp add: rcos_inv)
   322 apply (simp add: rcos_inv)
   322 done
   323 done
   323 
   324 
   324 
   325 
   325 (* some rules for <#> with #> or <# *)
   326 text {* Some rules for @{text "<#>"} with @{text "#>"} or @{text "<#"}. *}
       
   327 
   326 lemma (in coset) setmult_rcos_assoc:
   328 lemma (in coset) setmult_rcos_assoc:
   327      "[| H <= carrier G; K <= carrier G; x \<in> carrier G |] 
   329      "[| H <= carrier G; K <= carrier G; x \<in> carrier G |]
   328       ==> H <#> (K #> x) = (H <#> K) #> x"
   330       ==> H <#> (K #> x) = (H <#> K) #> x"
   329 apply (auto simp add: rcos_def r_coset_def setmult_def set_mult_def)
   331 apply (auto simp add: rcos_def r_coset_def setmult_def set_mult_def)
   330 apply (force simp add: m_assoc)+
   332 apply (force simp add: m_assoc)+
   331 done
   333 done
   332 
   334 
   333 lemma (in coset) rcos_assoc_lcos:
   335 lemma (in coset) rcos_assoc_lcos:
   334      "[| H <= carrier G; K <= carrier G; x \<in> carrier G |] 
   336      "[| H <= carrier G; K <= carrier G; x \<in> carrier G |]
   335       ==> (H #> x) <#> K = H <#> (x <# K)"
   337       ==> (H #> x) <#> K = H <#> (x <# K)"
   336 apply (auto simp add: rcos_def r_coset_def lcos_def l_coset_def 
   338 apply (auto simp add: rcos_def r_coset_def lcos_def l_coset_def
   337                       setmult_def set_mult_def Sigma_def image_def)
   339                       setmult_def set_mult_def Sigma_def image_def)
   338 apply (force intro!: exI bexI simp add: m_assoc)+
   340 apply (force intro!: exI bexI simp add: m_assoc)+
   339 done
   341 done
   340 
   342 
   341 lemma (in coset) rcos_mult_step1:
   343 lemma (in coset) rcos_mult_step1:
   342      "[| H <| G; x \<in> carrier G; y \<in> carrier G |] 
   344      "[| H <| G; x \<in> carrier G; y \<in> carrier G |]
   343       ==> (H #> x) <#> (H #> y) = (H <#> (x <# H)) #> y"
   345       ==> (H #> x) <#> (H #> y) = (H <#> (x <# H)) #> y"
   344 by (simp add: setmult_rcos_assoc normal_imp_subgroup [THEN subgroup.subset]
   346 by (simp add: setmult_rcos_assoc normal_imp_subgroup [THEN subgroup.subset]
   345               r_coset_subset_G l_coset_subset_G rcos_assoc_lcos)
   347               r_coset_subset_G l_coset_subset_G rcos_assoc_lcos)
   346 
   348 
   347 lemma (in coset) rcos_mult_step2:
   349 lemma (in coset) rcos_mult_step2:
   348      "[| H <| G; x \<in> carrier G; y \<in> carrier G |] 
   350      "[| H <| G; x \<in> carrier G; y \<in> carrier G |]
   349       ==> (H <#> (x <# H)) #> y = (H <#> (H #> x)) #> y"
   351       ==> (H <#> (x <# H)) #> y = (H <#> (H #> x)) #> y"
   350 by (simp add: normal_imp_rcos_eq_lcos)
   352 by (simp add: normal_imp_rcos_eq_lcos)
   351 
   353 
   352 lemma (in coset) rcos_mult_step3:
   354 lemma (in coset) rcos_mult_step3:
   353      "[| H <| G; x \<in> carrier G; y \<in> carrier G |] 
   355      "[| H <| G; x \<in> carrier G; y \<in> carrier G |]
   354       ==> (H <#> (H #> x)) #> y = H #> (x \<otimes> y)"
   356       ==> (H <#> (H #> x)) #> y = H #> (x \<otimes> y)"
   355 by (simp add: setmult_rcos_assoc r_coset_subset_G coset_mult_assoc
   357 by (simp add: setmult_rcos_assoc r_coset_subset_G coset_mult_assoc
   356               setmult_subset_G  subgroup_mult_id
   358               setmult_subset_G  subgroup_mult_id
   357               subgroup.subset normal_imp_subgroup)
   359               subgroup.subset normal_imp_subgroup)
   358 
   360 
   359 lemma (in coset) rcos_sum:
   361 lemma (in coset) rcos_sum:
   360      "[| H <| G; x \<in> carrier G; y \<in> carrier G |] 
   362      "[| H <| G; x \<in> carrier G; y \<in> carrier G |]
   361       ==> (H #> x) <#> (H #> y) = H #> (x \<otimes> y)"
   363       ==> (H #> x) <#> (H #> y) = H #> (x \<otimes> y)"
   362 by (simp add: rcos_mult_step1 rcos_mult_step2 rcos_mult_step3)
   364 by (simp add: rcos_mult_step1 rcos_mult_step2 rcos_mult_step3)
   363 
   365 
   364 (*generalizes subgroup_mult_id*)
       
   365 lemma (in coset) setrcos_mult_eq: "[|H <| G; M \<in> rcosets G H|] ==> H <#> M = M"
   366 lemma (in coset) setrcos_mult_eq: "[|H <| G; M \<in> rcosets G H|] ==> H <#> M = M"
   366 by (auto simp add: setrcos_eq normal_imp_subgroup subgroup.subset
   367   -- {* generalizes @{text subgroup_mult_id} *}
   367                    setmult_rcos_assoc subgroup_mult_id)
   368   by (auto simp add: setrcos_eq normal_imp_subgroup subgroup.subset
   368 
   369     setmult_rcos_assoc subgroup_mult_id)
   369 
   370 
   370 subsection{*Lemmas Leading to Lagrange's Theorem*}
   371 
   371 
   372 subsection {*Lemmas Leading to Lagrange's Theorem *}
   372 lemma (in coset) setrcos_part_G: "subgroup H G ==> \<Union> rcosets G H = carrier G"
   373 
       
   374 lemma (in coset) setrcos_part_G: "subgroup H G ==> \<Union>rcosets G H = carrier G"
   373 apply (rule equalityI)
   375 apply (rule equalityI)
   374 apply (force simp add: subgroup.subset [THEN subsetD] 
   376 apply (force simp add: subgroup.subset [THEN subsetD]
   375                        setrcos_eq r_coset_eq)
   377                        setrcos_eq r_coset_eq)
   376 apply (auto simp add: setrcos_eq subgroup.subset rcos_self)
   378 apply (auto simp add: setrcos_eq subgroup.subset rcos_self)
   377 done
   379 done
   378 
   380 
   379 lemma (in coset) cosets_finite:
   381 lemma (in coset) cosets_finite:
   396 lemma (in coset) inj_on_g:
   398 lemma (in coset) inj_on_g:
   397     "[|H \<subseteq> carrier G;  a \<in> carrier G|] ==> inj_on (\<lambda>y. y \<otimes> a) H"
   399     "[|H \<subseteq> carrier G;  a \<in> carrier G|] ==> inj_on (\<lambda>y. y \<otimes> a) H"
   398 by (force simp add: inj_on_def subsetD)
   400 by (force simp add: inj_on_def subsetD)
   399 
   401 
   400 lemma (in coset) card_cosets_equal:
   402 lemma (in coset) card_cosets_equal:
   401      "[| c \<in> rcosets G H;  H <= carrier G; finite(carrier G) |] 
   403      "[| c \<in> rcosets G H;  H <= carrier G; finite(carrier G) |]
   402       ==> card c = card H"
   404       ==> card c = card H"
   403 apply (auto simp add: setrcos_eq)
   405 apply (auto simp add: setrcos_eq)
   404 apply (rule card_bij_eq)
   406 apply (rule card_bij_eq)
   405      apply (rule inj_on_f, assumption+) 
   407      apply (rule inj_on_f, assumption+)
   406     apply (force simp add: m_assoc subsetD r_coset_eq)
   408     apply (force simp add: m_assoc subsetD r_coset_eq)
   407    apply (rule inj_on_g, assumption+) 
   409    apply (rule inj_on_g, assumption+)
   408   apply (force simp add: m_assoc subsetD r_coset_eq)
   410   apply (force simp add: m_assoc subsetD r_coset_eq)
   409  txt{*The sets @{term "H #> a"} and @{term "H"} are finite.*}
   411  txt{*The sets @{term "H #> a"} and @{term "H"} are finite.*}
   410  apply (simp add: r_coset_subset_G [THEN finite_subset])
   412  apply (simp add: r_coset_subset_G [THEN finite_subset])
   411 apply (blast intro: finite_subset)
   413 apply (blast intro: finite_subset)
   412 done
   414 done
   413 
   415 
   414 subsection{*Two distinct right cosets are disjoint*}
   416 subsection{*Two distinct right cosets are disjoint*}
   415 
   417 
   416 lemma (in coset) rcos_equation:
   418 lemma (in coset) rcos_equation:
   417      "[|subgroup H G;  a \<in> carrier G;  b \<in> carrier G;  ha \<otimes> a = h \<otimes> b;   
   419      "[|subgroup H G;  a \<in> carrier G;  b \<in> carrier G;  ha \<otimes> a = h \<otimes> b;
   418         h \<in> H;  ha \<in> H;  hb \<in> H|]  
   420         h \<in> H;  ha \<in> H;  hb \<in> H|]
   419       ==> \<exists>h\<in>H. h \<otimes> b = hb \<otimes> a"
   421       ==> \<exists>h\<in>H. h \<otimes> b = hb \<otimes> a"
   420 apply (rule bexI [of _"hb \<otimes> ((inv ha) \<otimes> h)"])
   422 apply (rule bexI [of _"hb \<otimes> ((inv ha) \<otimes> h)"])
   421 apply (simp  add: m_assoc transpose_inv subgroup.subset [THEN subsetD])
   423 apply (simp  add: m_assoc transpose_inv subgroup.subset [THEN subsetD])
   422 apply (simp add: subgroup.m_closed subgroup.m_inv_closed)
   424 apply (simp add: subgroup.m_closed subgroup.m_inv_closed)
   423 done
   425 done
   437 subsection {*Factorization of a Group*}
   439 subsection {*Factorization of a Group*}
   438 
   440 
   439 constdefs
   441 constdefs
   440   FactGroup :: "[('a,'b) monoid_scheme, 'a set] => ('a set) monoid"
   442   FactGroup :: "[('a,'b) monoid_scheme, 'a set] => ('a set) monoid"
   441      (infixl "Mod" 60)
   443      (infixl "Mod" 60)
   442    "FactGroup G H ==
   444   "FactGroup G H ==
   443       (| carrier = rcosets G H,
   445     (| carrier = rcosets G H,
   444 	 mult = (%X: rcosets G H. %Y: rcosets G H. set_mult G X Y),
   446        mult = (%X: rcosets G H. %Y: rcosets G H. set_mult G X Y),
   445 	 one = H (*,
   447        one = H (*,
   446 	 m_inv = (%X: rcosets G H. set_inv G X) *) |)"
   448        m_inv = (%X: rcosets G H. set_inv G X) *) |)"
   447 
   449 
   448 lemma (in coset) setmult_closed:
   450 lemma (in coset) setmult_closed:
   449      "[| H <| G; K1 \<in> rcosets G H; K2 \<in> rcosets G H |] 
   451      "[| H <| G; K1 \<in> rcosets G H; K2 \<in> rcosets G H |]
   450       ==> K1 <#> K2 \<in> rcosets G H"
   452       ==> K1 <#> K2 \<in> rcosets G H"
   451 by (auto simp add: normal_imp_subgroup [THEN subgroup.subset] 
   453 by (auto simp add: normal_imp_subgroup [THEN subgroup.subset]
   452                    rcos_sum setrcos_eq)
   454                    rcos_sum setrcos_eq)
   453 
   455 
   454 lemma (in group) setinv_closed:
   456 lemma (in group) setinv_closed:
   455      "[| H <| G; K \<in> rcosets G H |] ==> set_inv G K \<in> rcosets G H"
   457      "[| H <| G; K \<in> rcosets G H |] ==> set_inv G K \<in> rcosets G H"
   456 by (auto simp add:  normal_imp_subgroup
   458 by (auto simp add:  normal_imp_subgroup
   465 by (auto simp add:  normal_imp_subgroup
   467 by (auto simp add:  normal_imp_subgroup
   466                    subgroup.subset coset.rcos_inv coset.setrcos_eq)
   468                    subgroup.subset coset.rcos_inv coset.setrcos_eq)
   467 *)
   469 *)
   468 
   470 
   469 lemma (in coset) setrcos_assoc:
   471 lemma (in coset) setrcos_assoc:
   470      "[|H <| G; M1 \<in> rcosets G H; M2 \<in> rcosets G H; M3 \<in> rcosets G H|]   
   472      "[|H <| G; M1 \<in> rcosets G H; M2 \<in> rcosets G H; M3 \<in> rcosets G H|]
   471       ==> M1 <#> M2 <#> M3 = M1 <#> (M2 <#> M3)"
   473       ==> M1 <#> M2 <#> M3 = M1 <#> (M2 <#> M3)"
   472 by (auto simp add: setrcos_eq rcos_sum normal_imp_subgroup 
   474 by (auto simp add: setrcos_eq rcos_sum normal_imp_subgroup
   473                    subgroup.subset m_assoc)
   475                    subgroup.subset m_assoc)
   474 
   476 
   475 lemma (in group) subgroup_in_rcosets:
   477 lemma (in group) subgroup_in_rcosets:
   476   "subgroup H G ==> H \<in> rcosets G H"
   478   "subgroup H G ==> H \<in> rcosets G H"
   477 proof -
   479 proof -
   484 qed
   486 qed
   485 
   487 
   486 (*
   488 (*
   487 lemma subgroup_in_rcosets:
   489 lemma subgroup_in_rcosets:
   488   "subgroup H G ==> H \<in> rcosets G H"
   490   "subgroup H G ==> H \<in> rcosets G H"
   489 apply (frule subgroup_imp_coset) 
   491 apply (frule subgroup_imp_coset)
   490 apply (frule subgroup_imp_group) 
   492 apply (frule subgroup_imp_group)
   491 apply (simp add: coset.setrcos_eq)
   493 apply (simp add: coset.setrcos_eq)
   492 apply (blast del: equalityI 
   494 apply (blast del: equalityI
   493              intro!: group.subgroup.one_closed group.one_closed
   495              intro!: group.subgroup.one_closed group.one_closed
   494                      coset.coset_join2 [symmetric])
   496                      coset.coset_join2 [symmetric])
   495 done
   497 done
   496 *)
   498 *)
   497 
   499 
   498 lemma (in coset) setrcos_inv_mult_group_eq:
   500 lemma (in coset) setrcos_inv_mult_group_eq:
   499      "[|H <| G; M \<in> rcosets G H|] ==> set_inv G M <#> M = H"
   501      "[|H <| G; M \<in> rcosets G H|] ==> set_inv G M <#> M = H"
   500 by (auto simp add: setrcos_eq rcos_inv rcos_sum normal_imp_subgroup 
   502 by (auto simp add: setrcos_eq rcos_inv rcos_sum normal_imp_subgroup
   501                    subgroup.subset)
   503                    subgroup.subset)
   502 (*
   504 (*
   503 lemma (in group) factorgroup_is_magma:
   505 lemma (in group) factorgroup_is_magma:
   504   "H <| G ==> magma (G Mod H)"
   506   "H <| G ==> magma (G Mod H)"
   505   by rule (simp add: FactGroup_def coset.setmult_closed [OF is_coset])
   507   by rule (simp add: FactGroup_def coset.setmult_closed [OF is_coset])
   509   by rule (simp add: FactGroup_def coset.setrcos_assoc [OF is_coset]
   511   by rule (simp add: FactGroup_def coset.setrcos_assoc [OF is_coset]
   510     coset.setmult_closed [OF is_coset])
   512     coset.setmult_closed [OF is_coset])
   511 *)
   513 *)
   512 theorem (in group) factorgroup_is_group:
   514 theorem (in group) factorgroup_is_group:
   513   "H <| G ==> group (G Mod H)"
   515   "H <| G ==> group (G Mod H)"
   514 apply (insert is_coset) 
   516 apply (insert is_coset)
   515 apply (simp add: FactGroup_def) 
   517 apply (simp add: FactGroup_def)
   516 apply (rule groupI)
   518 apply (rule groupI)
   517     apply (simp add: coset.setmult_closed)
   519     apply (simp add: coset.setmult_closed)
   518    apply (simp add: normal_imp_subgroup subgroup_in_rcosets)
   520    apply (simp add: normal_imp_subgroup subgroup_in_rcosets)
   519   apply (simp add: restrictI coset.setmult_closed coset.setrcos_assoc)
   521   apply (simp add: restrictI coset.setmult_closed coset.setrcos_assoc)
   520  apply (simp add: normal_imp_subgroup
   522  apply (simp add: normal_imp_subgroup