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