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