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