helm/software/matita/library/algebra/groups.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "algebra/monoids.ma".
  16 include "nat/le_arith.ma".
  17 include "datatypes/bool.ma".
  18 include "nat/compare.ma".
  19
  20 record PreGroup : Type ≝
  21  { pre_monoid:> PreMonoid;
  22    inv: pre_monoid -> pre_monoid
  23  }.
  24
  25 interpretation "Group inverse" 'invert x = (inv ? x).
  26
  27 record isGroup (G:PreGroup) : Prop ≝
  28  { is_monoid           :> IsMonoid G;
  29    inv_is_left_inverse :  is_left_inverse G (inv G);
  30    inv_is_right_inverse:  is_right_inverse G (inv G)
  31  }.
  32
  33 record Group : Type ≝
  34  { pre_group:> PreGroup;
  35    is_group:> isGroup pre_group
  36  }.
  37
  38 definition Monoid_of_Group: Group → Monoid ≝
  39  λG. mk_Monoid ? (is_group G).
  40
  41 coercion Monoid_of_Group nocomposites.
  42
  43 definition left_cancellable ≝
  44  λT:Type. λop: T -> T -> T.
  45   ∀x. injective ? ? (op x).
  46
  47 definition right_cancellable ≝
  48  λT:Type. λop: T -> T -> T.
  49   ∀x. injective ? ? (λz.op z x).
  50
  51 theorem eq_op_x_y_op_x_z_to_eq:
  52  ∀G:Group. left_cancellable G (op G).
  53 intros;
  54 unfold left_cancellable;
  55 unfold injective;
  56 intros (x y z);
  57 rewrite < (e_is_left_unit ? G);
  58 rewrite < (e_is_left_unit ? G z);
  59 rewrite < (inv_is_left_inverse ? G x);
  60 rewrite > (op_is_associative ? G);
  61 rewrite > (op_is_associative ? G);
  62 apply eq_f;
  63 assumption.
  64 qed.
  65
  66 theorem eq_op_x_y_op_z_y_to_eq:
  67  ∀G:Group. right_cancellable G (op G).
  68 intros;
  69 unfold right_cancellable;
  70 unfold injective;
  71 intros (x y z);
  72 rewrite < (e_is_right_unit ? G);
  73 rewrite < (e_is_right_unit ? G z);
  74 rewrite < (inv_is_right_inverse ? G x);
  75 rewrite < (op_is_associative ? G);
  76 rewrite < (op_is_associative ? G);
  77 rewrite > H;
  78 reflexivity.
  79 qed.
  80
  81 theorem eq_inv_inv_x_x: ∀G:Group. ∀x:G. x \sup -1 \sup -1 = x.
  82 intros;
  83 apply (eq_op_x_y_op_z_y_to_eq ? (x \sup -1));
  84 rewrite > (inv_is_right_inverse ? G);
  85 rewrite > (inv_is_left_inverse ? G);
  86 reflexivity.
  87 qed.
  88
  89 theorem eq_opxy_e_to_eq_x_invy:
  90  ∀G:Group. ∀x,y:G. x·y=ⅇ → x=y \sup -1.
  91 intros;
  92 apply (eq_op_x_y_op_z_y_to_eq ? y);
  93 rewrite > (inv_is_left_inverse ? G);
  94 assumption.
  95 qed.
  96
  97 theorem eq_opxy_e_to_eq_invx_y:
  98  ∀G:Group. ∀x,y:G. x·y=ⅇ → x \sup -1=y.
  99 intros;
 100 apply (eq_op_x_y_op_x_z_to_eq ? x);
 101 rewrite > (inv_is_right_inverse ? G);
 102 symmetry;
 103 assumption.
 104 qed.
 105
 106 theorem eq_opxy_z_to_eq_x_opzinvy:
 107  ∀G:Group. ∀x,y,z:G. x·y=z → x = z·y \sup -1.
 108 intros;
 109 apply (eq_op_x_y_op_z_y_to_eq ? y);
 110 rewrite > (op_is_associative ? G);
 111 rewrite > (inv_is_left_inverse ? G);
 112 rewrite > (e_is_right_unit ? G);
 113 assumption.
 114 qed.
 115
 116 theorem eq_opxy_z_to_eq_y_opinvxz:
 117  ∀G:Group. ∀x,y,z:G. x·y=z → y = x \sup -1·z.
 118 intros;
 119 apply (eq_op_x_y_op_x_z_to_eq ? x);
 120 rewrite < (op_is_associative ? G);
 121 rewrite > (inv_is_right_inverse ? G);
 122 rewrite > (e_is_left_unit ? G);
 123 assumption.
 124 qed.
 125
 126 theorem eq_inv_op_x_y_op_inv_y_inv_x:
 127  ∀G:Group. ∀x,y:G. (x·y) \sup -1 = y \sup -1 · x \sup -1.
 128 intros;
 129 apply (eq_op_x_y_op_z_y_to_eq ? (x·y));
 130 rewrite > (inv_is_left_inverse ? G);
 131 rewrite < (op_is_associative ? G);
 132 rewrite > (op_is_associative ? G (y \sup -1));
 133 rewrite > (inv_is_left_inverse ? G);
 134 rewrite > (e_is_right_unit ? G);
 135 rewrite > (inv_is_left_inverse ? G);
 136 reflexivity.
 137 qed.
 138
 139 (* Morphisms *)
 140
 141 record morphism (G,G':Group) : Type ≝
 142  { image:1> G → G';
 143    f_morph: ∀x,y:G.image(x·y) = image x · image y
 144  }.
 145
 146 theorem morphism_to_eq_f_1_1:
 147  ∀G,G'.∀f:morphism G G'.f ⅇ  = ⅇ.
 148 intros;
 149 apply (eq_op_x_y_op_z_y_to_eq ? (f ⅇ));
 150 rewrite > (e_is_left_unit ? G');
 151 rewrite < f_morph;
 152 rewrite > (e_is_left_unit ? G);
 153 reflexivity.
 154 qed.
 155
 156 theorem eq_image_inv_inv_image:
 157  ∀G,G'.∀f:morphism G G'.
 158   ∀x.f (x \sup -1) = (f x) \sup -1.
 159 intros;
 160 apply (eq_op_x_y_op_z_y_to_eq ? (f x));
 161 rewrite > (inv_is_left_inverse ? G');
 162 rewrite < f_morph;
 163 rewrite > (inv_is_left_inverse ? G);
 164 apply (morphism_to_eq_f_1_1 ? ? f).
 165 qed.
 166
 167 record monomorphism (G,G':Group) : Type ≝
 168  { morphism:> morphism G G';
 169    injective: injective ? ? (image ? ? morphism)
 170  }.
 171
 172 (* Subgroups *)
 173
 174 record subgroup (G:Group) : Type ≝
 175  { group:> Group;
 176    embed:> monomorphism group G
 177  }.
 178
 179 notation "hvbox(x \sub H)" with precedence 79
 180 for @{ 'subgroupimage $H $x }.
 181
 182 interpretation "Subgroup image" 'subgroupimage H x =
 183  (image ?? (morphism_OF_subgroup ? H) x).
 184
 185 definition member_of_subgroup ≝
 186  λG.λH:subgroup G.λx:G.∃y.x=y \sub H.
 187
 188 notation "hvbox(x break \in H)" with precedence 79
 189 for @{ 'member_of $x $H }.
 190
 191 notation "hvbox(x break \notin H)" with precedence 79
 192 for @{ 'not_member_of $x $H }.
 193
 194 interpretation "Member of subgroup" 'member_of x H =
 195  (member_of_subgroup ? H x).
 196
 197 interpretation "Not member of subgroup" 'not_member_of x H =
 198  (Not (member_of_subgroup ? H x)).
 199
 200 (* Left cosets *)
 201
 202 record left_coset (G:Group) : Type ≝
 203  { element: G;
 204    subgrp: subgroup G
 205  }.
 206
 207 (* Here I would prefer 'magma_op, but this breaks something in the next definition *)
 208 interpretation "Left_coset" 'times x C =
 209  (mk_left_coset ? x C).
 210
 211 definition member_of_left_coset ≝
 212  λG:Group.λC:left_coset G.λx:G.
 213   ∃y.x=(element ? C)·y \sub (subgrp ? C).
 214
 215 interpretation "Member of left_coset" 'member_of x C =
 216  (member_of_left_coset ? C x).
 217
 218 definition left_coset_eq ≝
 219  λG.λC,C':left_coset G.
 220   ∀x.((element ? C)·x \sub (subgrp ? C)) ∈ C'.
 221
 222 interpretation "Left cosets equality" 'eq t C C' = (left_coset_eq t C C').
 223
 224 definition left_coset_disjoint ≝
 225  λG.λC,C':left_coset G.
 226   ∀x.¬(((element ? C)·x \sub (subgrp ? C)) ∈ C').
 227
 228 notation "hvbox(a break \par b)"
 229  non associative with precedence 45
 230 for @{ 'disjoint $a $b }.
 231
 232 interpretation "Left cosets disjoint" 'disjoint C C' =
 233  (left_coset_disjoint ? C C').
 234
 235 (* The following should be a one-shot alias! *)
 236 alias symbol "member_of" (instance 0) = "Member of subgroup".
 237 theorem member_of_subgroup_op_inv_x_y_to_left_coset_eq:
 238  ∀G.∀x,y.∀H:subgroup G. (x \sup -1 ·y) ∈ H → x*H = y*H.
 239 intros;
 240 simplify;
 241 intro;
 242 unfold member_of_subgroup in H1;
 243 elim H1;
 244 clear H1;
 245 exists;
 246 [ apply (a\sup-1 · x1)
 247 | rewrite > f_morph;
 248   rewrite > eq_image_inv_inv_image;
 249   rewrite < H2;
 250   rewrite > eq_inv_op_x_y_op_inv_y_inv_x;
 251   rewrite > eq_inv_inv_x_x;
 252   rewrite < (op_is_associative ? G);
 253   rewrite < (op_is_associative ? G);
 254   rewrite > (inv_is_right_inverse ? G);
 255   rewrite > (e_is_left_unit ? G);
 256   reflexivity
 257 ].
 258 qed.
 259
 260 theorem Not_member_of_subgroup_to_left_coset_disjoint:
 261  ∀G.∀x,y.∀H:subgroup G.(x \sup -1 ·y) ∉ H → x*H ∥ y*H.
 262 intros;
 263 simplify;
 264 unfold Not;
 265 intros (x');
 266 apply H1;
 267 unfold member_of_subgroup;
 268 elim H2;
 269 apply (ex_intro ? ? (x'·a \sup -1));
 270 rewrite > f_morph;
 271 apply (eq_op_x_y_op_z_y_to_eq ? (a \sub H));
 272 rewrite > (op_is_associative ? G);
 273 rewrite < H3;
 274 rewrite > (op_is_associative ? G);
 275 rewrite < f_morph;
 276 rewrite > (inv_is_left_inverse ? H);
 277 rewrite < (op_is_associative ? G);
 278 rewrite > (inv_is_left_inverse ? G);
 279 rewrite > (e_is_left_unit ? G);
 280 rewrite < (f_morph ? ? H);
 281 rewrite > (e_is_right_unit ? H);
 282 reflexivity.
 283 qed.
 284
 285 (*CSC: here the coercion Type_of_Group cannot be omitted. Why? *)
 286 theorem in_x_mk_left_coset_x_H:
 287  ∀G.∀x:Type_OF_Group G.∀H:subgroup G.x ∈ (x*H).
 288 intros;
 289 simplify;
 290 apply (ex_intro ? ? ⅇ);
 291 rewrite > morphism_to_eq_f_1_1;
 292 rewrite > (e_is_right_unit ? G);
 293 reflexivity.
 294 qed.
 295
 296 (* Normal Subgroups *)
 297
 298 record normal_subgroup (G:Group) : Type ≝
 299  { ns_subgroup:> subgroup G;
 300    normal:> ∀x:G.∀y:ns_subgroup.(x·y \sub ns_subgroup·x \sup -1) ∈ ns_subgroup
 301  }.
 302
 303 (*CSC: I have not defined yet right cosets
 304 theorem foo:
 305  ∀G.∀H:normal_subgroup G.∀x.x*H=H*x.
 306 *)
 307 (*
 308 theorem member_of_left_coset_mk_left_coset_x_H_a_to_member_of_left_coset_mk_left_coset_y_H_b_to_member_of_left_coset_mk_left_coset_op_x_y_H_op_a_b:
 309  ∀G.∀H:normal_subgroup G.∀x,y,a,b.
 310   a ∈ (x*H) → b ∈ (y*H) → (a·b) ∈ ((x·y)*H).
 311 intros;
 312 simplify;
 313 qed.
 314 *)