helm/software/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 include "algebra/semigroups.ma".
  16
  17 record PreMonoid : Type ≝
  18  { magma:> Magma;
  19    e: magma
  20  }.
  21
  22 (* FG: the interpretation goes just after its definition *)
  23 interpretation "Monoid unit" 'neutral = (e ?).
  24
  25 record isMonoid (M:PreMonoid) : Prop ≝
  26  { is_semi_group:> isSemiGroup M;
  27    e_is_left_unit:
  28     is_left_unit (mk_SemiGroup ? is_semi_group) (e M);
  29    e_is_right_unit:
  30     is_right_unit (mk_SemiGroup ? is_semi_group) (e M)
  31  }.
  32
  33 record Monoid : Type ≝
  34  { premonoid:> PreMonoid;
  35    monoid_properties:> isMonoid premonoid
  36  }.
  37
  38 definition is_left_inverse ≝
  39  λM:Monoid.
  40   λopp: M → M.
  41    ∀x:M. (opp x)·x = ⅇ.
  42
  43 definition is_right_inverse ≝
  44  λM:Monoid.
  45   λopp: M → M.
  46    ∀x:M. x·(opp x) = ⅇ.
  47
  48 theorem is_left_inverse_to_is_right_inverse_to_eq:
  49  ∀M:Monoid. ∀l,r.
  50   is_left_inverse M l → is_right_inverse M r →
  51    ∀x:M. l x = r x.
  52  intros;
  53  generalize in match (H x); intro;
  54  generalize in match (eq_f ? ? (λy.y·(r x)) ? ? H2);
  55  simplify; fold simplify (op M);
  56  intro; clear H2;
  57  generalize in match (op_associative ? (is_semi_group ? (monoid_properties M)));
  58  intro;
  59  rewrite > H2 in H3; clear H2;
  60  rewrite > H1 in H3;
  61  rewrite > (e_is_left_unit ? (monoid_properties M)) in H3;
  62  rewrite > (e_is_right_unit ? (monoid_properties M)) in H3;
  63  assumption.
  64 qed.