107 subgroup.one_closed) |
107 subgroup.one_closed) |
108 done |
108 done |
109 |
109 |
110 text (in group) {* Opposite of @{thm [source] "repr_independence"} *} |
110 text (in group) {* Opposite of @{thm [source] "repr_independence"} *} |
111 lemma (in group) repr_independenceD: |
111 lemma (in group) repr_independenceD: |
112 includes subgroup H G |
112 assumes "subgroup H G" |
113 assumes ycarr: "y \<in> carrier G" |
113 assumes ycarr: "y \<in> carrier G" |
114 and repr: "H #> x = H #> y" |
114 and repr: "H #> x = H #> y" |
115 shows "y \<in> H #> x" |
115 shows "y \<in> H #> x" |
116 apply (subst repr) |
116 proof - |
|
117 interpret subgroup [H G] by fact |
|
118 show ?thesis apply (subst repr) |
117 apply (intro rcos_self) |
119 apply (intro rcos_self) |
118 apply (rule ycarr) |
120 apply (rule ycarr) |
119 apply (rule is_subgroup) |
121 apply (rule is_subgroup) |
120 done |
122 done |
|
123 qed |
121 |
124 |
122 text {* Elements of a right coset are in the carrier *} |
125 text {* Elements of a right coset are in the carrier *} |
123 lemma (in subgroup) elemrcos_carrier: |
126 lemma (in subgroup) elemrcos_carrier: |
124 includes group |
127 assumes "group G" |
125 assumes acarr: "a \<in> carrier G" |
128 assumes acarr: "a \<in> carrier G" |
126 and a': "a' \<in> H #> a" |
129 and a': "a' \<in> H #> a" |
127 shows "a' \<in> carrier G" |
130 shows "a' \<in> carrier G" |
128 proof - |
131 proof - |
|
132 interpret group [G] by fact |
129 from subset and acarr |
133 from subset and acarr |
130 have "H #> a \<subseteq> carrier G" by (rule r_coset_subset_G) |
134 have "H #> a \<subseteq> carrier G" by (rule r_coset_subset_G) |
131 from this and a' |
135 from this and a' |
132 show "a' \<in> carrier G" |
136 show "a' \<in> carrier G" |
133 by fast |
137 by fast |
134 qed |
138 qed |
135 |
139 |
136 lemma (in subgroup) rcos_const: |
140 lemma (in subgroup) rcos_const: |
137 includes group |
141 assumes "group G" |
138 assumes hH: "h \<in> H" |
142 assumes hH: "h \<in> H" |
139 shows "H #> h = H" |
143 shows "H #> h = H" |
140 apply (unfold r_coset_def) |
144 proof - |
141 apply rule |
145 interpret group [G] by fact |
142 apply rule |
146 show ?thesis apply (unfold r_coset_def) |
143 apply clarsimp |
147 apply rule |
144 apply (intro subgroup.m_closed) |
148 apply rule |
145 apply (rule is_subgroup) |
149 apply clarsimp |
|
150 apply (intro subgroup.m_closed) |
|
151 apply (rule is_subgroup) |
146 apply assumption |
152 apply assumption |
147 apply (rule hH) |
153 apply (rule hH) |
148 apply rule |
154 apply rule |
149 apply simp |
155 apply simp |
150 proof - |
156 proof - |
151 fix h' |
157 fix h' |
152 assume h'H: "h' \<in> H" |
158 assume h'H: "h' \<in> H" |
153 note carr = hH[THEN mem_carrier] h'H[THEN mem_carrier] |
159 note carr = hH[THEN mem_carrier] h'H[THEN mem_carrier] |
154 from carr |
160 from carr |
155 have a: "h' = (h' \<otimes> inv h) \<otimes> h" by (simp add: m_assoc) |
161 have a: "h' = (h' \<otimes> inv h) \<otimes> h" by (simp add: m_assoc) |
156 from h'H hH |
162 from h'H hH |
157 have "h' \<otimes> inv h \<in> H" by simp |
163 have "h' \<otimes> inv h \<in> H" by simp |
158 from this and a |
164 from this and a |
159 show "\<exists>x\<in>H. h' = x \<otimes> h" by fast |
165 show "\<exists>x\<in>H. h' = x \<otimes> h" by fast |
|
166 qed |
160 qed |
167 qed |
161 |
168 |
162 text {* Step one for lemma @{text "rcos_module"} *} |
169 text {* Step one for lemma @{text "rcos_module"} *} |
163 lemma (in subgroup) rcos_module_imp: |
170 lemma (in subgroup) rcos_module_imp: |
164 includes group |
171 assumes "group G" |
165 assumes xcarr: "x \<in> carrier G" |
172 assumes xcarr: "x \<in> carrier G" |
166 and x'cos: "x' \<in> H #> x" |
173 and x'cos: "x' \<in> H #> x" |
167 shows "(x' \<otimes> inv x) \<in> H" |
174 shows "(x' \<otimes> inv x) \<in> H" |
168 proof - |
175 proof - |
|
176 interpret group [G] by fact |
169 from xcarr x'cos |
177 from xcarr x'cos |
170 have x'carr: "x' \<in> carrier G" |
178 have x'carr: "x' \<in> carrier G" |
171 by (rule elemrcos_carrier[OF is_group]) |
179 by (rule elemrcos_carrier[OF is_group]) |
172 from xcarr |
180 from xcarr |
173 have ixcarr: "inv x \<in> carrier G" |
181 have ixcarr: "inv x \<in> carrier G" |
198 show "x' \<otimes> (inv x) \<in> H" by simp |
206 show "x' \<otimes> (inv x) \<in> H" by simp |
199 qed |
207 qed |
200 |
208 |
201 text {* Step two for lemma @{text "rcos_module"} *} |
209 text {* Step two for lemma @{text "rcos_module"} *} |
202 lemma (in subgroup) rcos_module_rev: |
210 lemma (in subgroup) rcos_module_rev: |
203 includes group |
211 assumes "group G" |
204 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
212 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
205 and xixH: "(x' \<otimes> inv x) \<in> H" |
213 and xixH: "(x' \<otimes> inv x) \<in> H" |
206 shows "x' \<in> H #> x" |
214 shows "x' \<in> H #> x" |
207 proof - |
215 proof - |
|
216 interpret group [G] by fact |
208 from xixH |
217 from xixH |
209 have "\<exists>h\<in>H. x' \<otimes> (inv x) = h" by fast |
218 have "\<exists>h\<in>H. x' \<otimes> (inv x) = h" by fast |
210 from this |
219 from this |
211 obtain h |
220 obtain h |
212 where hH: "h \<in> H" |
221 where hH: "h \<in> H" |
229 by fast |
238 by fast |
230 qed |
239 qed |
231 |
240 |
232 text {* Module property of right cosets *} |
241 text {* Module property of right cosets *} |
233 lemma (in subgroup) rcos_module: |
242 lemma (in subgroup) rcos_module: |
234 includes group |
243 assumes "group G" |
235 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
244 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
236 shows "(x' \<in> H #> x) = (x' \<otimes> inv x \<in> H)" |
245 shows "(x' \<in> H #> x) = (x' \<otimes> inv x \<in> H)" |
237 proof |
246 proof - |
238 assume "x' \<in> H #> x" |
247 interpret group [G] by fact |
239 from this and carr |
248 show ?thesis proof assume "x' \<in> H #> x" |
240 show "x' \<otimes> inv x \<in> H" |
249 from this and carr |
|
250 show "x' \<otimes> inv x \<in> H" |
241 by (intro rcos_module_imp[OF is_group]) |
251 by (intro rcos_module_imp[OF is_group]) |
242 next |
252 next |
243 assume "x' \<otimes> inv x \<in> H" |
253 assume "x' \<otimes> inv x \<in> H" |
244 from this and carr |
254 from this and carr |
245 show "x' \<in> H #> x" |
255 show "x' \<in> H #> x" |
246 by (intro rcos_module_rev[OF is_group]) |
256 by (intro rcos_module_rev[OF is_group]) |
|
257 qed |
247 qed |
258 qed |
248 |
259 |
249 text {* Right cosets are subsets of the carrier. *} |
260 text {* Right cosets are subsets of the carrier. *} |
250 lemma (in subgroup) rcosets_carrier: |
261 lemma (in subgroup) rcosets_carrier: |
251 includes group |
262 assumes "group G" |
252 assumes XH: "X \<in> rcosets H" |
263 assumes XH: "X \<in> rcosets H" |
253 shows "X \<subseteq> carrier G" |
264 shows "X \<subseteq> carrier G" |
254 proof - |
265 proof - |
|
266 interpret group [G] by fact |
255 from XH have "\<exists>x\<in> carrier G. X = H #> x" |
267 from XH have "\<exists>x\<in> carrier G. X = H #> x" |
256 unfolding RCOSETS_def |
268 unfolding RCOSETS_def |
257 by fast |
269 by fast |
258 from this |
270 from this |
259 obtain x |
271 obtain x |
329 from subgroup.m_inv_closed[OF subH hH] and subgroup.m_inv_closed[OF subK kK] and this |
341 from subgroup.m_inv_closed[OF subH hH] and subgroup.m_inv_closed[OF subK kK] and this |
330 show "\<exists>ha\<in>H. \<exists>ka\<in>K. inv (h \<otimes> k) = ha \<otimes> ka" by fast |
342 show "\<exists>ha\<in>H. \<exists>ka\<in>K. inv (h \<otimes> k) = ha \<otimes> ka" by fast |
331 qed |
343 qed |
332 |
344 |
333 lemma (in subgroup) lcos_module_rev: |
345 lemma (in subgroup) lcos_module_rev: |
334 includes group |
346 assumes "group G" |
335 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
347 assumes carr: "x \<in> carrier G" "x' \<in> carrier G" |
336 and xixH: "(inv x \<otimes> x') \<in> H" |
348 and xixH: "(inv x \<otimes> x') \<in> H" |
337 shows "x' \<in> x <# H" |
349 shows "x' \<in> x <# H" |
338 proof - |
350 proof - |
|
351 interpret group [G] by fact |
339 from xixH |
352 from xixH |
340 have "\<exists>h\<in>H. (inv x) \<otimes> x' = h" by fast |
353 have "\<exists>h\<in>H. (inv x) \<otimes> x' = h" by fast |
341 from this |
354 from this |
342 obtain h |
355 obtain h |
343 where hH: "h \<in> H" |
356 where hH: "h \<in> H" |
582 ("rcong\<index> _") |
595 ("rcong\<index> _") |
583 "rcong H \<equiv> {(x,y). x \<in> carrier G & y \<in> carrier G & inv x \<otimes> y \<in> H}" |
596 "rcong H \<equiv> {(x,y). x \<in> carrier G & y \<in> carrier G & inv x \<otimes> y \<in> H}" |
584 |
597 |
585 |
598 |
586 lemma (in subgroup) equiv_rcong: |
599 lemma (in subgroup) equiv_rcong: |
587 includes group G |
600 assumes "group G" |
588 shows "equiv (carrier G) (rcong H)" |
601 shows "equiv (carrier G) (rcong H)" |
589 proof (intro equiv.intro) |
602 proof - |
590 show "refl (carrier G) (rcong H)" |
603 interpret group [G] by fact |
591 by (auto simp add: r_congruent_def refl_def) |
604 show ?thesis |
592 next |
605 proof (intro equiv.intro) |
593 show "sym (rcong H)" |
606 show "refl (carrier G) (rcong H)" |
594 proof (simp add: r_congruent_def sym_def, clarify) |
607 by (auto simp add: r_congruent_def refl_def) |
595 fix x y |
608 next |
596 assume [simp]: "x \<in> carrier G" "y \<in> carrier G" |
609 show "sym (rcong H)" |
597 and "inv x \<otimes> y \<in> H" |
610 proof (simp add: r_congruent_def sym_def, clarify) |
598 hence "inv (inv x \<otimes> y) \<in> H" by (simp add: m_inv_closed) |
611 fix x y |
599 thus "inv y \<otimes> x \<in> H" by (simp add: inv_mult_group) |
612 assume [simp]: "x \<in> carrier G" "y \<in> carrier G" |
600 qed |
613 and "inv x \<otimes> y \<in> H" |
601 next |
614 hence "inv (inv x \<otimes> y) \<in> H" by (simp add: m_inv_closed) |
602 show "trans (rcong H)" |
615 thus "inv y \<otimes> x \<in> H" by (simp add: inv_mult_group) |
603 proof (simp add: r_congruent_def trans_def, clarify) |
616 qed |
604 fix x y z |
617 next |
605 assume [simp]: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
618 show "trans (rcong H)" |
606 and "inv x \<otimes> y \<in> H" and "inv y \<otimes> z \<in> H" |
619 proof (simp add: r_congruent_def trans_def, clarify) |
607 hence "(inv x \<otimes> y) \<otimes> (inv y \<otimes> z) \<in> H" by simp |
620 fix x y z |
608 hence "inv x \<otimes> (y \<otimes> inv y) \<otimes> z \<in> H" by (simp add: m_assoc del: r_inv) |
621 assume [simp]: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
609 thus "inv x \<otimes> z \<in> H" by simp |
622 and "inv x \<otimes> y \<in> H" and "inv y \<otimes> z \<in> H" |
|
623 hence "(inv x \<otimes> y) \<otimes> (inv y \<otimes> z) \<in> H" by simp |
|
624 hence "inv x \<otimes> (y \<otimes> inv y) \<otimes> z \<in> H" by (simp add: m_assoc del: r_inv) |
|
625 thus "inv x \<otimes> z \<in> H" by simp |
|
626 qed |
610 qed |
627 qed |
611 qed |
628 qed |
612 |
629 |
613 text{*Equivalence classes of @{text rcong} correspond to left cosets. |
630 text{*Equivalence classes of @{text rcong} correspond to left cosets. |
614 Was there a mistake in the definitions? I'd have expected them to |
631 Was there a mistake in the definitions? I'd have expected them to |
623 the context where K is a normal subgroup. Jacobson doesn't name it. |
640 the context where K is a normal subgroup. Jacobson doesn't name it. |
624 But in this context left and right cosets are identical. |
641 But in this context left and right cosets are identical. |
625 *) |
642 *) |
626 |
643 |
627 lemma (in subgroup) l_coset_eq_rcong: |
644 lemma (in subgroup) l_coset_eq_rcong: |
628 includes group G |
645 assumes "group G" |
629 assumes a: "a \<in> carrier G" |
646 assumes a: "a \<in> carrier G" |
630 shows "a <# H = rcong H `` {a}" |
647 shows "a <# H = rcong H `` {a}" |
631 by (force simp add: r_congruent_def l_coset_def m_assoc [symmetric] a ) |
648 proof - |
632 |
649 interpret group [G] by fact |
|
650 show ?thesis by (force simp add: r_congruent_def l_coset_def m_assoc [symmetric] a ) |
|
651 qed |
633 |
652 |
634 subsubsection{*Two Distinct Right Cosets are Disjoint*} |
653 subsubsection{*Two Distinct Right Cosets are Disjoint*} |
635 |
654 |
636 lemma (in group) rcos_equation: |
655 lemma (in group) rcos_equation: |
637 includes subgroup H G |
656 assumes "subgroup H G" |
638 shows |
657 assumes p: "ha \<otimes> a = h \<otimes> b" "a \<in> carrier G" "b \<in> carrier G" "h \<in> H" "ha \<in> H" "hb \<in> H" |
639 "\<lbrakk>ha \<otimes> a = h \<otimes> b; a \<in> carrier G; b \<in> carrier G; |
658 shows "hb \<otimes> a \<in> (\<Union>h\<in>H. {h \<otimes> b})" |
640 h \<in> H; ha \<in> H; hb \<in> H\<rbrakk> |
659 proof - |
641 \<Longrightarrow> hb \<otimes> a \<in> (\<Union>h\<in>H. {h \<otimes> b})" |
660 interpret subgroup [H G] by fact |
642 apply (rule UN_I [of "hb \<otimes> ((inv ha) \<otimes> h)"]) |
661 from p show ?thesis apply (rule_tac UN_I [of "hb \<otimes> ((inv ha) \<otimes> h)"]) |
643 apply (simp add: ) |
662 apply (simp add: ) |
644 apply (simp add: m_assoc transpose_inv) |
663 apply (simp add: m_assoc transpose_inv) |
645 done |
664 done |
|
665 qed |
646 |
666 |
647 lemma (in group) rcos_disjoint: |
667 lemma (in group) rcos_disjoint: |
648 includes subgroup H G |
668 assumes "subgroup H G" |
649 shows "\<lbrakk>a \<in> rcosets H; b \<in> rcosets H; a\<noteq>b\<rbrakk> \<Longrightarrow> a \<inter> b = {}" |
669 assumes p: "a \<in> rcosets H" "b \<in> rcosets H" "a\<noteq>b" |
650 apply (simp add: RCOSETS_def r_coset_def) |
670 shows "a \<inter> b = {}" |
651 apply (blast intro: rcos_equation prems sym) |
671 proof - |
652 done |
672 interpret subgroup [H G] by fact |
|
673 from p show ?thesis apply (simp add: RCOSETS_def r_coset_def) |
|
674 apply (blast intro: rcos_equation prems sym) |
|
675 done |
|
676 qed |
653 |
677 |
654 subsection {* Further lemmas for @{text "r_congruent"} *} |
678 subsection {* Further lemmas for @{text "r_congruent"} *} |
655 |
679 |
656 text {* The relation is a congruence *} |
680 text {* The relation is a congruence *} |
657 |
681 |
730 constdefs |
754 constdefs |
731 order :: "('a, 'b) monoid_scheme \<Rightarrow> nat" |
755 order :: "('a, 'b) monoid_scheme \<Rightarrow> nat" |
732 "order S \<equiv> card (carrier S)" |
756 "order S \<equiv> card (carrier S)" |
733 |
757 |
734 lemma (in group) rcosets_part_G: |
758 lemma (in group) rcosets_part_G: |
735 includes subgroup |
759 assumes "subgroup H G" |
736 shows "\<Union>(rcosets H) = carrier G" |
760 shows "\<Union>(rcosets H) = carrier G" |
737 apply (rule equalityI) |
761 proof - |
738 apply (force simp add: RCOSETS_def r_coset_def) |
762 interpret subgroup [H G] by fact |
739 apply (auto simp add: RCOSETS_def intro: rcos_self prems) |
763 show ?thesis |
740 done |
764 apply (rule equalityI) |
|
765 apply (force simp add: RCOSETS_def r_coset_def) |
|
766 apply (auto simp add: RCOSETS_def intro: rcos_self prems) |
|
767 done |
|
768 qed |
741 |
769 |
742 lemma (in group) cosets_finite: |
770 lemma (in group) cosets_finite: |
743 "\<lbrakk>c \<in> rcosets H; H \<subseteq> carrier G; finite (carrier G)\<rbrakk> \<Longrightarrow> finite c" |
771 "\<lbrakk>c \<in> rcosets H; H \<subseteq> carrier G; finite (carrier G)\<rbrakk> \<Longrightarrow> finite c" |
744 apply (auto simp add: RCOSETS_def) |
772 apply (auto simp add: RCOSETS_def) |
745 apply (simp add: r_coset_subset_G [THEN finite_subset]) |
773 apply (simp add: r_coset_subset_G [THEN finite_subset]) |
813 "\<lbrakk>M1 \<in> rcosets H; M2 \<in> rcosets H; M3 \<in> rcosets H\<rbrakk> |
841 "\<lbrakk>M1 \<in> rcosets H; M2 \<in> rcosets H; M3 \<in> rcosets H\<rbrakk> |
814 \<Longrightarrow> M1 <#> M2 <#> M3 = M1 <#> (M2 <#> M3)" |
842 \<Longrightarrow> M1 <#> M2 <#> M3 = M1 <#> (M2 <#> M3)" |
815 by (auto simp add: RCOSETS_def rcos_sum m_assoc) |
843 by (auto simp add: RCOSETS_def rcos_sum m_assoc) |
816 |
844 |
817 lemma (in subgroup) subgroup_in_rcosets: |
845 lemma (in subgroup) subgroup_in_rcosets: |
818 includes group G |
846 assumes "group G" |
819 shows "H \<in> rcosets H" |
847 shows "H \<in> rcosets H" |
820 proof - |
848 proof - |
|
849 interpret group [G] by fact |
821 from _ subgroup_axioms have "H #> \<one> = H" |
850 from _ subgroup_axioms have "H #> \<one> = H" |
822 by (rule coset_join2) auto |
851 by (rule coset_join2) auto |
823 then show ?thesis |
852 then show ?thesis |
824 by (auto simp add: RCOSETS_def) |
853 by (auto simp add: RCOSETS_def) |
825 qed |
854 qed |