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    opp: premonoid -> premonoid
  25  }.
  26
  27 record isGroup (G:PreGroup) : Prop ≝
  28  { is_monoid: isMonoid G;
  29    opp_is_left_inverse: is_left_inverse (mk_Monoid ? is_monoid) (opp G);
  30    opp_is_right_inverse: is_right_inverse (mk_Monoid ? is_monoid) (opp 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 @{ 'gopp $x }.
  58
  59 interpretation "Group inverse" 'gopp x =
  60  (cic:/matita/algebra/groups/opp.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 ? (is_monoid ? (group_properties G)));
  77 rewrite < (e_is_left_unit ? (is_monoid ? (group_properties G)) z);
  78 rewrite < (opp_is_left_inverse ? (group_properties G) x);
  79 rewrite > (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
  80 rewrite > (associative ? (is_semi_group ? (is_monoid ? (group_properties 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 ? (is_monoid ? (group_properties G)));
  94 rewrite < (e_is_right_unit ? (is_monoid ? (group_properties G)) z);
  95 rewrite < (opp_is_right_inverse ? (group_properties G) x);
  96 rewrite < (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
  97 rewrite < (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
  98 rewrite > H;
  99 reflexivity.
 100 qed.
 101
 102
 103 record finite_enumerable (T:Type) : Type ≝
 104  { order: nat;
 105    repr: nat → T;
 106    index_of: T → nat;
 107    index_of_sur: ∀x.index_of x ≤ order;
 108    index_of_repr: ∀n. n≤order → index_of (repr n) = n;
 109    repr_index_of: ∀x. repr (index_of x) = x
 110  }.
 111
 112 notation "hvbox(C \sub i)" with precedence 89
 113 for @{ 'repr $C $i }.
 114
 115 (* CSC: multiple interpretations in the same file are not considered in the
 116  right order
 117 interpretation "Finite_enumerable representation" 'repr C i =
 118  (cic:/matita/algebra/groups/repr.con C _ i).*)
 119
 120 notation < "hvbox(|C|)" with precedence 89
 121 for @{ 'card $C }.
 122
 123 interpretation "Finite_enumerable order" 'card C =
 124  (cic:/matita/algebra/groups/order.con C _).
 125
 126 record finite_enumerable_SemiGroup : Type ≝
 127  { semigroup:> SemiGroup;
 128    is_finite_enumerable:> finite_enumerable semigroup
 129  }.
 130
 131 notation < "S"
 132 for @{ 'semigroup_of_finite_enumerable_semigroup $S }.
 133
 134 interpretation "Semigroup_of_finite_enumerable_semigroup"
 135  'semigroup_of_finite_enumerable_semigroup S
 136 =
 137  (cic:/matita/algebra/groups/semigroup.con S).
 138
 139 notation < "S"
 140 for @{ 'magma_of_finite_enumerable_semigroup $S }.
 141
 142 interpretation "Magma_of_finite_enumerable_semigroup"
 143  'magma_of_finite_enumerable_semigroup S
 144 =
 145  (cic:/matita/algebra/groups/Magma_of_finite_enumerable_SemiGroup.con S).
 146
 147 notation < "S"
 148 for @{ 'type_of_finite_enumerable_semigroup $S }.
 149
 150 interpretation "Type_of_finite_enumerable_semigroup"
 151  'type_of_finite_enumerable_semigroup S
 152 =
 153  (cic:/matita/algebra/groups/Type_of_finite_enumerable_SemiGroup.con S).
 154
 155 interpretation "Finite_enumerable representation" 'repr S i =
 156  (cic:/matita/algebra/groups/repr.con S
 157   (cic:/matita/algebra/groups/is_finite_enumerable.con S) i).
 158
 159 notation "hvbox(ι e)" with precedence 60
 160 for @{ 'index_of_finite_enumerable_semigroup $e }.
 161
 162 interpretation "Index_of_finite_enumerable representation"
 163  'index_of_finite_enumerable_semigroup e
 164 =
 165  (cic:/matita/algebra/groups/index_of.con _
 166   (cic:/matita/algebra/groups/is_finite_enumerable.con _) e).
 167
 168
 169 (* several definitions/theorems to be moved somewhere else *)
 170
 171 definition ltb ≝ λn,m. leb n m ∧ notb (eqb n m).
 172
 173 theorem not_eq_to_le_to_lt: ∀n,m. n≠m → n≤m → n<m.
 174 intros;
 175 elim (le_to_or_lt_eq ? ? H1);
 176 [ assumption
 177 | elim (H H2)
 178 ].
 179 qed.
 180
 181 theorem ltb_to_Prop :
 182  ∀n,m.
 183   match ltb n m with
 184   [ true ⇒ n < m
 185   | false ⇒ n ≮ m
 186   ].
 187 intros;
 188 unfold ltb;
 189 apply leb_elim;
 190 apply eqb_elim;
 191 intros;
 192 simplify;
 193 [ rewrite < H;
 194   apply le_to_not_lt;
 195   constructor 1
 196 | apply (not_eq_to_le_to_lt ? ? H H1)
 197 | rewrite < H;
 198   apply le_to_not_lt;
 199   constructor 1
 200 | apply le_to_not_lt;
 201   generalize in match (not_le_to_lt ? ? H1);
 202   clear H1;
 203   intro;
 204   apply lt_to_le;
 205   assumption
 206 ].
 207 qed.
 208
 209 theorem ltb_elim: ∀n,m:nat. ∀P:bool → Prop.
 210 (n < m → (P true)) → (n ≮ m → (P false)) →
 211 P (ltb n m).
 212 intros.
 213 cut
 214 (match (ltb n m) with
 215 [ true  ⇒ n < m
 216 | false ⇒ n ≮ m] → (P (ltb n m))).
 217 apply Hcut.apply ltb_to_Prop.
 218 elim (ltb n m).
 219 apply ((H H2)).
 220 apply ((H1 H2)).
 221 qed.
 222
 223 theorem Not_lt_n_n: ∀n. n ≮ n.
 224 intro;
 225 unfold Not;
 226 intro;
 227 unfold lt in H;
 228 apply (not_le_Sn_n ? H).
 229 qed.
 230
 231 theorem eq_pred_to_eq:
 232  ∀n,m. O < n → O < m → pred n = pred m → n = m.
 233 intros;
 234 generalize in match (eq_f ? ? S ? ? H2);
 235 intro;
 236 rewrite < S_pred in H3;
 237 rewrite < S_pred in H3;
 238 assumption.
 239 qed.
 240
 241 theorem le_pred_to_le:
 242  ∀n,m. O < m → pred n ≤ pred m → n ≤ m.
 243 intros 2;
 244 elim n;
 245 [ apply le_O_n
 246 | simplify in H2;
 247   rewrite > (S_pred m);
 248   [ apply le_S_S;
 249     assumption
 250   | assumption
 251   ]
 252 ].
 253 qed.
 254
 255 theorem le_to_le_pred:
 256  ∀n,m. n ≤ m → pred n ≤ pred m.
 257 intros 2;
 258 elim n;
 259 [ simplify;
 260   apply le_O_n
 261 | simplify;
 262   generalize in match H1;
 263   clear H1;
 264   elim m;
 265   [ elim (not_le_Sn_O ? H1)
 266   | simplify;
 267     apply le_S_S_to_le;
 268     assumption
 269   ]
 270 ].
 271 qed.
 272
 273 theorem lt_n_m_to_not_lt_m_Sn: ∀n,m. n < m → m ≮ S n.
 274 intros;
 275 unfold Not;
 276 intro;
 277 unfold lt in H;
 278 unfold lt in H1;
 279 generalize in match (le_S_S ? ? H);
 280 intro;
 281 generalize in match (transitive_le ? ? ? H2 H1);
 282 intro;
 283 apply (not_le_Sn_n ? H3).
 284 qed.
 285
 286 theorem lt_S_S: ∀n,m. n < m → S n < S m.
 287 intros;
 288 unfold lt in H;
 289 apply (le_S_S ? ? H).
 290 qed.
 291
 292 theorem lt_O_S: ∀n. O < S n.
 293 intro;
 294 unfold lt;
 295 apply le_S_S;
 296 apply le_O_n.
 297 qed.
 298
 299 theorem le_n_m_to_lt_m_Sn_to_eq_n_m: ∀n,m. n ≤ m → m < S n → n=m.
 300 intros;
 301 unfold lt in H1;
 302 generalize in match (le_S_S_to_le ? ? H1);
 303 intro;
 304 apply cic:/matita/nat/orders/antisym_le.con;
 305 assumption.
 306 qed.
 307
 308 theorem pigeonhole:
 309  ∀n:nat.∀f:nat→nat.
 310   (∀x,y.x≤n → y≤n → f x = f y → x=y) →
 311   (∀m. m ≤ n → f m ≤ n) →
 312    ∀x. x≤n → ∃y.f y = x ∧ y ≤ n.
 313 intro;
 314 elim n;
 315 [ apply (ex_intro ? ? O);
 316   split;
 317   [ rewrite < (le_n_O_to_eq ? H2);
 318     rewrite < (le_n_O_to_eq ? (H1 O ?));
 319     [ reflexivity
 320     | apply le_n
 321     ]
 322   | apply le_n
 323   ]
 324 | clear n;
 325   letin f' ≝
 326    (λx.
 327     let fSn1 ≝ f (S n1) in
 328      let fx ≝ f x in
 329       match ltb fSn1 fx with
 330       [ true ⇒ pred fx
 331       | false ⇒ fx
 332       ]);
 333   cut (∀x,y. x ≤ n1 → y ≤ n1 → f' x = f' y → x=y);
 334   [ cut (∀x. x ≤ n1 → f' x ≤ n1);
 335     [ apply (nat_compare_elim (f (S n1)) x);
 336       [ intro;
 337         elim (H f' ? ? (pred x));
 338         [ simplify in H5;
 339           clear Hcut;
 340           clear Hcut1;
 341           clear f';
 342           elim H5;
 343           clear H5;
 344           apply (ex_intro ? ? a);
 345           split;
 346           [ generalize in match (eq_f ? ? S ? ? H6);
 347             clear H6;
 348             intro;
 349             rewrite < S_pred in H5;
 350             [ generalize in match H4;
 351               clear H4;
 352               rewrite < H5;
 353               clear H5;
 354               apply (ltb_elim (f (S n1)) (f a));
 355               [ simplify;
 356                 intros;
 357                 rewrite < S_pred;
 358                 [ reflexivity
 359                 | apply (ltn_to_ltO ? ? H4)
 360                 ]
 361               | simplify;
 362                 intros;
 363                 generalize in match (not_lt_to_le ? ? H4);
 364                 clear H4;
 365                 intro;
 366                 generalize in match (le_n_m_to_lt_m_Sn_to_eq_n_m ? ? H6 H5);
 367                 intro;
 368                 generalize in match (H1 ? ? ? ? H4);
 369                 [ intro;
 370                   generalize in match (le_n_m_to_lt_m_Sn_to_eq_n_m ? ? H6 H5);
 371                   intro;
 372                   generalize in match (H1 ? ? ? ? H9);
 373                   [ intro;
 374                     rewrite > H10 in H7;
 375                     elim (not_le_Sn_n ? H7)
 376                   | rewrite > H8;
 377                     apply le_n
 378                   | apply le_n
 379                   ]
 380                 | apply le_S;
 381                   assumption
 382                 | apply le_n
 383                 ]
 384               ]
 385             | apply (ltn_to_ltO ? ? H4)
 386             ]
 387           | apply le_S;
 388             assumption
 389           ]
 390         | apply Hcut
 391         | apply Hcut1
 392         | apply le_S_S_to_le;
 393           rewrite < S_pred;
 394           [ assumption
 395           | apply (ltn_to_ltO ? ? H4)
 396           ]
 397         ]
 398       | intros;
 399         apply (ex_intro ? ? (S n1));
 400         split;
 401         [ assumption
 402         | constructor 1
 403         ]
 404       | intro;
 405         elim (H f' ? ? x);
 406         [ simplify in H5;
 407           clear Hcut;
 408           clear Hcut1;
 409           clear f';
 410           elim H5;
 411           clear H5;
 412           apply (ex_intro ? ? a);
 413           split;
 414           [ generalize in match H4;
 415             clear H4;
 416             rewrite < H6;
 417             clear H6;
 418             apply (ltb_elim (f (S n1)) (f a));
 419             [ simplify;
 420               intros;
 421               generalize in match (lt_S_S ? ? H5);
 422               intro;
 423               rewrite < S_pred in H6;
 424               [ elim (lt_n_m_to_not_lt_m_Sn ? ? H4 H6)
 425               | apply (ltn_to_ltO ? ? H4)
 426               ]
 427             | simplify;
 428               intros;
 429               reflexivity
 430             ]
 431           | apply le_S;
 432             assumption
 433           ]
 434         | apply Hcut
 435         | apply Hcut1
 436         | rewrite > (pred_Sn n1);
 437           simplify;
 438           generalize in match (H2 (S n1));
 439           intro;
 440           generalize in match (lt_to_le_to_lt ? ? ? H4 (H5 (le_n ?)));
 441           intro;
 442           unfold lt in H6;
 443           apply le_S_S_to_le;
 444           assumption
 445         ]
 446       ]
 447     | unfold f';
 448       simplify;
 449       intro;
 450       apply (ltb_elim (f (S n1)) (f x1));
 451       simplify;
 452       intros;
 453       [ generalize in match (H2 x1);
 454         intro;
 455         change in match n1 with (pred (S n1));
 456         apply le_to_le_pred;
 457         apply H6;
 458         apply le_S;
 459         assumption
 460       | generalize in match (H2 (S n1) (le_n ?));
 461         intro;
 462         generalize in match (not_lt_to_le ? ? H4);
 463         intro;
 464         generalize in match (transitive_le ? ? ? H7 H6);
 465         intro;
 466         cut (f x1 ≠ f (S n1));
 467         [ generalize in match (not_eq_to_le_to_lt ? ? Hcut1 H7);
 468           intro;
 469           unfold lt in H9;
 470           generalize in match (transitive_le ? ? ? H9 H6);
 471           intro;
 472           apply le_S_S_to_le;
 473           assumption
 474         | unfold Not;
 475           intro;
 476           generalize in match (H1 ? ? ? ? H9);
 477           [ intro;
 478             rewrite > H10 in H5;
 479             apply (not_le_Sn_n ? H5)
 480           | apply le_S;
 481             assumption
 482           | apply le_n
 483           ]
 484         ]
 485       ]
 486     ]
 487   | intros 4;
 488     unfold f';
 489     simplify;
 490     apply (ltb_elim (f (S n1)) (f x1));
 491     simplify;
 492     apply (ltb_elim (f (S n1)) (f y));
 493     simplify;
 494     intros;
 495     [ cut (f x1 = f y);
 496       [ apply (H1 ? ? ? ? Hcut);
 497         apply le_S;
 498         assumption
 499       | apply eq_pred_to_eq;
 500         [ apply (ltn_to_ltO ? ? H7)
 501         | apply (ltn_to_ltO ? ? H6)
 502         | assumption
 503         ]
 504       ]
 505     | (* pred (f x1) = f y absurd since y ≠ S n1 and thus f y ≠ f (S n1)
 506          so that f y < f (S n1) < f x1; hence pred (f x1) = f y is absurd *)
 507        cut (y < S n1);
 508        [ generalize in match (lt_to_not_eq ? ? Hcut);
 509          intro;
 510          cut (f y ≠ f (S n1));
 511          [ cut (f y < f (S n1));
 512            [ rewrite < H8 in Hcut2;
 513              unfold lt in Hcut2;
 514              unfold lt in H7;
 515              generalize in match (le_S_S ? ? Hcut2);
 516              intro;
 517              generalize in match (transitive_le ? ? ? H10 H7);
 518              intros;
 519              rewrite < (S_pred (f x1)) in H11;
 520               [ elim (not_le_Sn_n ? H11)
 521               | fold simplify ((f (S n1)) < (f x1)) in H7;
 522                 apply (ltn_to_ltO ? ? H7)
 523               ]
 524            | apply not_eq_to_le_to_lt;
 525              [ assumption
 526              | apply not_lt_to_le;
 527                assumption
 528              ]
 529            ]
 530          | unfold Not;
 531            intro;
 532            apply H9;
 533            apply (H1 ? ? ? ? H10);
 534            [ apply lt_to_le;
 535              assumption
 536            | constructor 1
 537            ]
 538          ]
 539        | unfold lt;
 540          apply le_S_S;
 541          assumption
 542        ]
 543     | (* f x1 = pred (f y) absurd since it implies S (f x1) = f y and
 544          f x1 ≤ f (S n1) < f y = S (f x1) so that f x1 = f (S n1); by
 545          injectivity x1 = S n1 that is absurd since x1 ≤ n1 *)
 546        generalize in match (eq_f ? ? S ? ? H8);
 547        intro;
 548        rewrite < S_pred in H9;
 549        [ rewrite < H9 in H6;
 550          generalize in match (not_lt_to_le ? ? H7);
 551          intro;
 552          unfold lt in H6;
 553          generalize in match (le_S_S ? ? H10);
 554          intro;
 555          generalize in match (antisym_le ? ? H11 H6);
 556          intro;
 557          generalize in match (inj_S ? ? H12);
 558          intro;
 559          generalize in match (H1 ? ? ? ? H13);
 560          [ intro;
 561            rewrite > H14 in H4;
 562            elim (not_le_Sn_n ? H4)
 563          | apply le_S;
 564            assumption
 565          | apply le_n
 566          ]
 567        | apply (ltn_to_ltO ? ? H6)
 568        ]
 569     | apply (H1 ? ? ? ? H8);
 570       apply le_S;
 571       assumption
 572     ]
 573   ]
 574 ].
 575 qed.
 576
 577 theorem finite_enumerable_SemiGroup_to_left_cancellable_to_right_cancellable_to_isMonoid:
 578  ∀G:finite_enumerable_SemiGroup.
 579   left_cancellable ? (op G) →
 580   right_cancellable ? (op G) →
 581    ∃e:G. isMonoid (mk_PreMonoid G e).
 582 intros;
 583 letin f ≝ (λn.ι(G \sub O · G \sub n));
 584 cut (∀n.n ≤ order ? (is_finite_enumerable G) → ∃m.f m = n);
 585 [ letin EX ≝ (Hcut O ?);
 586   [ apply le_O_n
 587   | clearbody EX;
 588     clear Hcut;
 589     unfold f in EX;
 590     elim EX;
 591     clear EX;
 592     letin HH ≝ (eq_f ? ? (repr ? (is_finite_enumerable G)) ? ? H2);
 593     clearbody HH;
 594     rewrite > (repr_index_of ? (is_finite_enumerable G)) in HH;
 595     apply (ex_intro ? ? (G \sub a));
 596     letin GOGO ≝ (refl_eq ? (repr ? (is_finite_enumerable G) O));
 597     clearbody GOGO;
 598     rewrite < HH in GOGO;
 599     rewrite < HH in GOGO:(? ? % ?);
 600     rewrite > (associative ? G) in GOGO;
 601     letin GaGa ≝ (H ? ? ? GOGO);
 602     clearbody GaGa;
 603     clear GOGO;
 604     constructor 1;
 605     [ simplify;
 606       apply (semigroup_properties G)
 607     | unfold is_left_unit; intro;
 608       letin GaxGax ≝ (refl_eq ? (G \sub a ·x));
 609       clearbody GaxGax;
 610       rewrite < GaGa in GaxGax:(? ? % ?);
 611       rewrite > (associative ? (semigroup_properties G)) in GaxGax;
 612       apply (H ? ? ? GaxGax)
 613     | unfold is_right_unit; intro;
 614       letin GaxGax ≝ (refl_eq ? (x·G \sub a));
 615       clearbody GaxGax;
 616       rewrite < GaGa in GaxGax:(? ? % ?);
 617       rewrite < (associative ? (semigroup_properties G)) in GaxGax;
 618       apply (H1 ? ? ? GaxGax)
 619     ]
 620   ]
 621 | intros;
 622   elim (pigeonhole (order ? G) f ? ? ? H2);
 623   [ apply (ex_intro ? ? a);
 624     elim H3;
 625     assumption
 626   | intros;
 627     change in H5 with (ι(G \sub O · G \sub x) = ι(G \sub O · G \sub y));
 628     cut (G \sub (ι(G \sub O · G \sub x)) = G \sub (ι(G \sub O · G \sub y)));
 629     [ rewrite > (repr_index_of ? ? (G \sub O · G \sub x))  in Hcut;
 630       rewrite > (repr_index_of ? ? (G \sub O · G \sub y))  in Hcut;
 631       generalize in match (H ? ? ? Hcut);
 632       intro;
 633       generalize in match (eq_f ? ? (index_of ? G) ? ? H6);
 634       intro;
 635       rewrite > index_of_repr in H7;
 636       rewrite > index_of_repr in H7;
 637       assumption
 638     | apply eq_f;
 639       assumption
 640     ]
 641   | intros;
 642     apply index_of_sur
 643   ]
 644 ].