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 |
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) |
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 |
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]) |