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