helm/matita/library/algebra/monoids.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/monoids/".
  16
  17 include "algebra/semigroups.ma".
  18
  19 record PreMonoid : Type ≝
  20  { magma:> Magma;
  21    e: magma
  22  }.
  23
  24 notation < "M" for @{ 'pmmagma $M }.
  25 interpretation "premonoid magma coercion" 'pmmagma M =
  26  (cic:/matita/algebra/monoids/magma.con M).
  27
  28 record isMonoid (M:PreMonoid) : Prop ≝
  29  { is_semi_group: isSemiGroup M;
  30    e_is_left_unit:
  31     is_left_unit (mk_SemiGroup ? is_semi_group) (e M);
  32    e_is_right_unit:
  33     is_right_unit (mk_SemiGroup ? is_semi_group) (e M)
  34  }.
  35
  36 record Monoid : Type ≝
  37  { premonoid:> PreMonoid;
  38    monoid_properties:> isMonoid premonoid
  39  }.
  40
  41 notation < "M" for @{ 'semigroup $M }.
  42 interpretation "premonoid coercion" 'premonoid M =
  43  (cic:/matita/algebra/monoids/premonoid.con M).
  44
  45 notation < "M" for @{ 'typeofmonoid $M }.
  46 interpretation "premonoid coercion" 'typeofmonoid M =
  47  (cic:/matita/algebra/monoids/Type_of_Monoid.con M).
  48
  49 notation < "M" for @{ 'magmaofmonoid $M }.
  50 interpretation "premonoid coercion" 'magmaofmonoid M =
  51  (cic:/matita/algebra/monoids/Magma_of_Monoid.con M).
  52
  53 notation "1" with precedence 89
  54 for @{ 'munit }.
  55
  56 interpretation "Monoid unit" 'munit =
  57  (cic:/matita/algebra/monoids/e.con _).
  58
  59 definition is_left_inverse ≝
  60  λM:Monoid.
  61   λopp: M → M.
  62    ∀x:M. (opp x)·x = 1.
  63
  64 definition is_right_inverse ≝
  65  λM:Monoid.
  66   λopp: M → M.
  67    ∀x:M. x·(opp x) = 1.
  68
  69 theorem is_left_inverse_to_is_right_inverse_to_eq:
  70  ∀M:Monoid. ∀l,r.
  71   is_left_inverse M l → is_right_inverse M r →
  72    ∀x:M. l x = r x.
  73  intros;
  74  generalize in match (H x); intro;
  75  generalize in match (eq_f ? ? (λy.y·(r x)) ? ? H2);
  76  simplify; fold simplify (op M);
  77  intro; clear H2;
  78  generalize in match (associative ? (is_semi_group ? (monoid_properties M)));
  79  intro;
  80  rewrite > H2 in H3; clear H2;
  81  rewrite > H1 in H3;
  82  rewrite > (e_is_left_unit ? (monoid_properties M)) in H3;
  83  rewrite > (e_is_right_unit ? (monoid_properties M)) in H3;
  84  assumption.
  85 qed.