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.5  header {* Groups *}
     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