src/HOL/Algebra/Group.thy
 changeset 14751 0d7850e27fed parent 14706 71590b7733b7 child 14761 28b5eb4a867f
     1.1 --- a/src/HOL/Algebra/Group.thy	Fri May 14 16:54:13 2004 +0200
1.2 +++ b/src/HOL/Algebra/Group.thy	Fri May 14 19:29:22 2004 +0200
1.3 @@ -8,7 +8,7 @@
1.4
1.6
1.7 -theory Group = FuncSet:
1.8 +theory Group = FuncSet + Lattice:
1.9
1.10  section {* From Magmas to Groups *}
1.11
1.12 @@ -20,11 +20,6 @@
1.13
1.14  subsection {* Definitions *}
1.15
1.16 -(* Object with a carrier set. *)
1.17 -
1.18 -record 'a partial_object =
1.19 -  carrier :: "'a set"
1.20 -
1.21  record 'a semigroup = "'a partial_object" +
1.22    mult :: "['a, 'a] => 'a" (infixl "\<otimes>\<index>" 70)
1.23
1.24 @@ -375,15 +370,6 @@
1.25
1.26  declare (in submagma) magma.intro [intro] semigroup.intro [intro]
1.27    semigroup_axioms.intro [intro]
1.28 -(*
1.29 -alternative definition of submagma
1.30 -
1.31 -locale submagma = var H + struct G +
1.32 -  assumes subset [intro, simp]: "carrier H \<subseteq> carrier G"
1.33 -    and m_equal [simp]: "mult H = mult G"
1.34 -    and m_closed [intro, simp]:
1.35 -      "[| x \<in> carrier H; y \<in> carrier H |] ==> x \<otimes> y \<in> carrier H"
1.36 -*)
1.37
1.38  lemma submagma_imp_subset:
1.39    "submagma H G ==> H \<subseteq> carrier G"
1.40 @@ -727,4 +713,96 @@
1.41    "[| x \<in> carrier G; y \<in> carrier G |] ==> inv (x \<otimes> y) = inv x \<otimes> inv y"
1.42    by (simp add: m_ac inv_mult_group)
1.43
1.44 +subsection {* Lattice of subgroups of a group *}
1.45 +
1.46 +text_raw {* \label{sec:subgroup-lattice} *}
1.47 +
1.48 +theorem (in group) subgroups_partial_order:
1.49 +  "partial_order (| carrier = {H. subgroup H G}, le = op \<subseteq> |)"
1.50 +  by (rule partial_order.intro) simp_all
1.51 +
1.52 +lemma (in group) subgroup_self:
1.53 +  "subgroup (carrier G) G"
1.54 +  by (rule subgroupI) auto
1.55 +
1.56 +lemma (in group) subgroup_imp_group:
1.57 +  "subgroup H G ==> group (G(| carrier := H |))"
1.58 +  using subgroup.groupI [OF _ group.intro] .
1.59 +
1.60 +lemma (in group) is_monoid [intro, simp]:
1.61 +  "monoid G"
1.62 +  by (rule monoid.intro)
1.63 +
1.64 +lemma (in group) subgroup_inv_equality:
1.65 +  "[| subgroup H G; x \<in> H |] ==> m_inv (G (| carrier := H |)) x = inv x"
1.66 +apply (rule_tac inv_equality [THEN sym])
1.67 +  apply (rule group.l_inv [OF subgroup_imp_group, simplified])
1.68 +   apply assumption+
1.69 + apply (rule subsetD [OF subgroup.subset])
1.70 +  apply assumption+
1.71 +apply (rule subsetD [OF subgroup.subset])
1.72 + apply assumption
1.73 +apply (rule_tac group.inv_closed [OF subgroup_imp_group, simplified])
1.74 +  apply assumption+
1.75 +done
1.76 +
1.77 +theorem (in group) subgroups_Inter:
1.78 +  assumes subgr: "(!!H. H \<in> A ==> subgroup H G)"
1.79 +    and not_empty: "A ~= {}"
1.80 +  shows "subgroup (\<Inter>A) G"
1.81 +proof (rule subgroupI)
1.82 +  from subgr [THEN subgroup.subset] and not_empty
1.83 +  show "\<Inter>A \<subseteq> carrier G" by blast
1.84 +next
1.85 +  from subgr [THEN subgroup.one_closed]
1.86 +  show "\<Inter>A ~= {}" by blast
1.87 +next
1.88 +  fix x assume "x \<in> \<Inter>A"
1.89 +  with subgr [THEN subgroup.m_inv_closed]
1.90 +  show "inv x \<in> \<Inter>A" by blast
1.91 +next
1.92 +  fix x y assume "x \<in> \<Inter>A" "y \<in> \<Inter>A"
1.93 +  with subgr [THEN subgroup.m_closed]
1.94 +  show "x \<otimes> y \<in> \<Inter>A" by blast
1.95 +qed
1.96 +
1.97 +theorem (in group) subgroups_complete_lattice:
1.98 +  "complete_lattice (| carrier = {H. subgroup H G}, le = op \<subseteq> |)"
1.99 +    (is "complete_lattice ?L")
1.100 +proof (rule partial_order.complete_lattice_criterion1)
1.101 +  show "partial_order ?L" by (rule subgroups_partial_order)
1.102 +next
1.103 +  have "greatest ?L (carrier G) (carrier ?L)"
1.104 +    by (unfold greatest_def) (simp add: subgroup.subset subgroup_self)
1.105 +  then show "EX G. greatest ?L G (carrier ?L)" ..
1.106 +next
1.107 +  fix A
1.108 +  assume L: "A \<subseteq> carrier ?L" and non_empty: "A ~= {}"
1.109 +  then have Int_subgroup: "subgroup (\<Inter>A) G"
1.110 +    by (fastsimp intro: subgroups_Inter)
1.111 +  have "greatest ?L (\<Inter>A) (Lower ?L A)"
1.112 +    (is "greatest ?L ?Int _")
1.113 +  proof (rule greatest_LowerI)
1.114 +    fix H
1.115 +    assume H: "H \<in> A"
1.116 +    with L have subgroupH: "subgroup H G" by auto
1.117 +    from subgroupH have submagmaH: "submagma H G" by (rule subgroup.axioms)
1.118 +    from subgroupH have groupH: "group (G (| carrier := H |))" (is "group ?H")
1.119 +      by (rule subgroup_imp_group)
1.120 +    from groupH have monoidH: "monoid ?H"
1.121 +      by (rule group.is_monoid)
1.122 +    from H have Int_subset: "?Int \<subseteq> H" by fastsimp
1.123 +    then show "le ?L ?Int H" by simp
1.124 +  next
1.125 +    fix H
1.126 +    assume H: "H \<in> Lower ?L A"
1.127 +    with L Int_subgroup show "le ?L H ?Int" by (fastsimp intro: Inter_greatest)
1.128 +  next
1.129 +    show "A \<subseteq> carrier ?L" by (rule L)
1.130 +  next
1.131 +    show "?Int \<in> carrier ?L" by simp (rule Int_subgroup)
1.132 +  qed
1.133 +  then show "EX I. greatest ?L I (Lower ?L A)" ..
1.134 +qed
1.135 +
1.136  end