src/ZF/ex/Group.thy
changeset 69593 3dda49e08b9d
parent 69587 53982d5ec0bb
child 76213 e44d86131648
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   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