271 show ?thesis |
271 show ?thesis |
272 by (rule groupI) (auto intro: m_assoc l_inv mem_carrier) |
272 by (rule groupI) (auto intro: m_assoc l_inv mem_carrier) |
273 qed |
273 qed |
274 |
274 |
275 text \<open> |
275 text \<open> |
276 Since @{term H} is nonempty, it contains some element @{term x}. Since |
276 Since \<^term>\<open>H\<close> is nonempty, it contains some element \<^term>\<open>x\<close>. Since |
277 it is closed under inverse, it contains \<open>inv x\<close>. Since |
277 it is closed under inverse, it contains \<open>inv x\<close>. Since |
278 it is closed under product, it contains \<open>x \<cdot> inv x = \<one>\<close>. |
278 it is closed under product, it contains \<open>x \<cdot> inv x = \<one>\<close>. |
279 \<close> |
279 \<close> |
280 |
280 |
281 text \<open> |
281 text \<open> |
282 Since @{term H} is nonempty, it contains some element @{term x}. Since |
282 Since \<^term>\<open>H\<close> is nonempty, it contains some element \<^term>\<open>x\<close>. Since |
283 it is closed under inverse, it contains \<open>inv x\<close>. Since |
283 it is closed under inverse, it contains \<open>inv x\<close>. Since |
284 it is closed under product, it contains \<open>x \<cdot> inv x = \<one>\<close>. |
284 it is closed under product, it contains \<open>x \<cdot> inv x = \<one>\<close>. |
285 \<close> |
285 \<close> |
286 |
286 |
287 lemma (in group) one_in_subset: |
287 lemma (in group) one_in_subset: |
409 interpret group I by fact |
409 interpret group I by fact |
410 show ?thesis |
410 show ?thesis |
411 by (auto intro: lam_type simp add: iso_def hom_def inj_def surj_def bij_def) |
411 by (auto intro: lam_type simp add: iso_def hom_def inj_def surj_def bij_def) |
412 qed |
412 qed |
413 |
413 |
414 text\<open>Basis for homomorphism proofs: we assume two groups @{term G} and |
414 text\<open>Basis for homomorphism proofs: we assume two groups \<^term>\<open>G\<close> and |
415 @{term H}, with a homomorphism @{term h} between them\<close> |
415 \<^term>\<open>H\<close>, with a homomorphism \<^term>\<open>h\<close> between them\<close> |
416 locale group_hom = G: group G + H: group H |
416 locale group_hom = G: group G + H: group H |
417 for G (structure) and H (structure) and h + |
417 for G (structure) and H (structure) and h + |
418 assumes homh: "h \<in> hom(G,H)" |
418 assumes homh: "h \<in> hom(G,H)" |
419 notes hom_mult [simp] = hom_mult [OF homh] |
419 notes hom_mult [simp] = hom_mult [OF homh] |
420 and hom_closed [simp] = hom_closed [OF homh] |
420 and hom_closed [simp] = hom_closed [OF homh] |
626 subgroup.subset [THEN subsetD] |
626 subgroup.subset [THEN subsetD] |
627 subgroup.m_closed solve_equation) |
627 subgroup.m_closed solve_equation) |
628 |
628 |
629 lemma (in group) coset_join2: |
629 lemma (in group) coset_join2: |
630 "\<lbrakk>x \<in> carrier(G); subgroup(H,G); x\<in>H\<rbrakk> \<Longrightarrow> H #> x = H" |
630 "\<lbrakk>x \<in> carrier(G); subgroup(H,G); x\<in>H\<rbrakk> \<Longrightarrow> H #> x = H" |
631 \<comment> \<open>Alternative proof is to put @{term "x=\<one>"} in \<open>repr_independence\<close>.\<close> |
631 \<comment> \<open>Alternative proof is to put \<^term>\<open>x=\<one>\<close> in \<open>repr_independence\<close>.\<close> |
632 by (force simp add: subgroup.m_closed r_coset_def solve_equation) |
632 by (force simp add: subgroup.m_closed r_coset_def solve_equation) |
633 |
633 |
634 lemma (in group) r_coset_subset_G: |
634 lemma (in group) r_coset_subset_G: |
635 "\<lbrakk>H \<subseteq> carrier(G); x \<in> carrier(G)\<rbrakk> \<Longrightarrow> H #> x \<subseteq> carrier(G)" |
635 "\<lbrakk>H \<subseteq> carrier(G); x \<in> carrier(G)\<rbrakk> \<Longrightarrow> H #> x \<subseteq> carrier(G)" |
636 by (auto simp add: r_coset_def) |
636 by (auto simp add: r_coset_def) |
970 "\<lbrakk>c \<in> rcosets H; H \<subseteq> carrier(G); Finite (carrier(G))\<rbrakk> \<Longrightarrow> Finite(c)" |
970 "\<lbrakk>c \<in> rcosets H; H \<subseteq> carrier(G); Finite (carrier(G))\<rbrakk> \<Longrightarrow> Finite(c)" |
971 apply (auto simp add: RCOSETS_def) |
971 apply (auto simp add: RCOSETS_def) |
972 apply (simp add: r_coset_subset_G [THEN subset_Finite]) |
972 apply (simp add: r_coset_subset_G [THEN subset_Finite]) |
973 done |
973 done |
974 |
974 |
975 text\<open>More general than the HOL version, which also requires @{term G} to |
975 text\<open>More general than the HOL version, which also requires \<^term>\<open>G\<close> to |
976 be finite.\<close> |
976 be finite.\<close> |
977 lemma (in group) card_cosets_equal: |
977 lemma (in group) card_cosets_equal: |
978 assumes H: "H \<subseteq> carrier(G)" |
978 assumes H: "H \<subseteq> carrier(G)" |
979 shows "c \<in> rcosets H \<Longrightarrow> |c| = |H|" |
979 shows "c \<in> rcosets H \<Longrightarrow> |c| = |H|" |
980 proof (simp add: RCOSETS_def, clarify) |
980 proof (simp add: RCOSETS_def, clarify) |
1069 "X \<in> carrier (G Mod H) \<Longrightarrow> inv\<^bsub>G Mod H\<^esub> X = set_inv X" |
1069 "X \<in> carrier (G Mod H) \<Longrightarrow> inv\<^bsub>G Mod H\<^esub> X = set_inv X" |
1070 apply (rule group.inv_equality [OF factorgroup_is_group]) |
1070 apply (rule group.inv_equality [OF factorgroup_is_group]) |
1071 apply (simp_all add: FactGroup_def setinv_closed rcosets_inv_mult_group_eq) |
1071 apply (simp_all add: FactGroup_def setinv_closed rcosets_inv_mult_group_eq) |
1072 done |
1072 done |
1073 |
1073 |
1074 text\<open>The coset map is a homomorphism from @{term G} to the quotient group |
1074 text\<open>The coset map is a homomorphism from \<^term>\<open>G\<close> to the quotient group |
1075 @{term "G Mod H"}\<close> |
1075 \<^term>\<open>G Mod H\<close>\<close> |
1076 lemma (in normal) r_coset_hom_Mod: |
1076 lemma (in normal) r_coset_hom_Mod: |
1077 "(\<lambda>a \<in> carrier(G). H #> a) \<in> hom(G, G Mod H)" |
1077 "(\<lambda>a \<in> carrier(G). H #> a) \<in> hom(G, G Mod H)" |
1078 by (auto simp add: FactGroup_def RCOSETS_def hom_def rcos_sum intro: lam_type) |
1078 by (auto simp add: FactGroup_def RCOSETS_def hom_def rcos_sum intro: lam_type) |
1079 |
1079 |
1080 |
1080 |
1199 shows "kernel(G,H,h) #> g \<subseteq> carrier (G)" |
1199 shows "kernel(G,H,h) #> g \<subseteq> carrier (G)" |
1200 by (auto simp add: g kernel_def r_coset_def) |
1200 by (auto simp add: g kernel_def r_coset_def) |
1201 |
1201 |
1202 |
1202 |
1203 |
1203 |
1204 text\<open>If the homomorphism @{term h} is onto @{term H}, then so is the |
1204 text\<open>If the homomorphism \<^term>\<open>h\<close> is onto \<^term>\<open>H\<close>, then so is the |
1205 homomorphism from the quotient group\<close> |
1205 homomorphism from the quotient group\<close> |
1206 lemma (in group_hom) FactGroup_surj: |
1206 lemma (in group_hom) FactGroup_surj: |
1207 assumes h: "h \<in> surj(carrier(G), carrier(H))" |
1207 assumes h: "h \<in> surj(carrier(G), carrier(H))" |
1208 shows "(\<lambda>X\<in>carrier (G Mod kernel(G,H,h)). contents (h `` X)) |
1208 shows "(\<lambda>X\<in>carrier (G Mod kernel(G,H,h)). contents (h `` X)) |
1209 \<in> surj(carrier (G Mod kernel(G,H,h)), carrier(H))" |
1209 \<in> surj(carrier (G Mod kernel(G,H,h)), carrier(H))" |
1213 with h obtain g where g: "g \<in> carrier(G)" "h ` g = y" |
1213 with h obtain g where g: "g \<in> carrier(G)" "h ` g = y" |
1214 by (auto simp add: surj_def) |
1214 by (auto simp add: surj_def) |
1215 hence "(\<Union>x\<in>kernel(G,H,h) #> g. {h ` x}) = {y}" |
1215 hence "(\<Union>x\<in>kernel(G,H,h) #> g. {h ` x}) = {y}" |
1216 by (auto simp add: y kernel_def r_coset_def) |
1216 by (auto simp add: y kernel_def r_coset_def) |
1217 with g show "\<exists>x\<in>carrier(G Mod kernel(G, H, h)). contents(h `` x) = y" |
1217 with g show "\<exists>x\<in>carrier(G Mod kernel(G, H, h)). contents(h `` x) = y" |
1218 \<comment> \<open>The witness is @{term "kernel(G,H,h) #> g"}\<close> |
1218 \<comment> \<open>The witness is \<^term>\<open>kernel(G,H,h) #> g\<close>\<close> |
1219 by (force simp add: FactGroup_def RCOSETS_def |
1219 by (force simp add: FactGroup_def RCOSETS_def |
1220 image_eq_UN [OF hom_is_fun] kernel_rcoset_subset) |
1220 image_eq_UN [OF hom_is_fun] kernel_rcoset_subset) |
1221 qed |
1221 qed |
1222 |
1222 |
1223 |
1223 |
1224 text\<open>If @{term h} is a homomorphism from @{term G} onto @{term H}, then the |
1224 text\<open>If \<^term>\<open>h\<close> is a homomorphism from \<^term>\<open>G\<close> onto \<^term>\<open>H\<close>, then the |
1225 quotient group @{term "G Mod (kernel(G,H,h))"} is isomorphic to @{term H}.\<close> |
1225 quotient group \<^term>\<open>G Mod (kernel(G,H,h))\<close> is isomorphic to \<^term>\<open>H\<close>.\<close> |
1226 theorem (in group_hom) FactGroup_iso: |
1226 theorem (in group_hom) FactGroup_iso: |
1227 "h \<in> surj(carrier(G), carrier(H)) |
1227 "h \<in> surj(carrier(G), carrier(H)) |
1228 \<Longrightarrow> (\<lambda>X\<in>carrier (G Mod kernel(G,H,h)). contents (h``X)) \<in> (G Mod (kernel(G,H,h))) \<cong> H" |
1228 \<Longrightarrow> (\<lambda>X\<in>carrier (G Mod kernel(G,H,h)). contents (h``X)) \<in> (G Mod (kernel(G,H,h))) \<cong> H" |
1229 by (simp add: iso_def FactGroup_hom FactGroup_inj bij_def FactGroup_surj) |
1229 by (simp add: iso_def FactGroup_hom FactGroup_inj bij_def FactGroup_surj) |
1230 |
1230 |