Prin monoid se intelege un cuplu (M,φ) format din o multime nevida si o lege de compozitie φ pe M, asociativa si cu element neutru. Daca (M,φ) este monoid, se mai spune ca M este sau ca formeaza monoid in raport cu operatia φ. Daca legea de compozitie este data aditiv, multiplicativ,atunci in loc de (M,φ) scriem (M.+), (M,*). Folosind, de exemplu, notatia multiplicativa, definitia monoidului se poate da astfel:

Definitie:

Spunem ca o multime nevida M este monoid in raport cu o lege de compozitie M x M -> M, (x,y) –> xy definita pe M daca sunt satisfacute urmatoarele axiome:

M1) asociativitatea (xy)z = x(y)z, oricare x,y,z din M
M2) element neutru exista un e din M a.i. ex = xe = x oricare ar fi x din M.

Ansamblul de conditii poarta numele de axiomenele monoidului. Elementul e este unic determinat si se numeste elementul neutru al monoidului M.

Daca operatia monoidului M satisface axioma

M3) comutatitivatea xy = yx oricare ar fi x,y din M

atunci spunem ca M este monoid comutativ.

Exemples:

1) Multimea numerelor naturale N formeaza monoid comutativ in raport cu operatia de adunare a numerelor naturale N;

(N,+) monoidul aditiv al numerelor naturale.

(N,*) monoidul multiplicativ al numerelor naturale.

2) Fie E o multime si P(E) multimea tuturor partilor lui E. Multimea vida este elementul neutru.

(M(E),U) si (M(E),∩) sunt monoizi comutativi.

Probleme:

1) Pe multimea N, se considera legea de compozitie data prin x * y = x + y + xy, oricare ar fi x,y din N. Sa se arate ca (N,*) este monoid.

Verificam daca legea de compozitie “*”

este asociativa: (x * y) * z = x * ( y * z)
daca exista Element Neutru.

Proof:

(x * y) * z = (x + y + xy) * z = x + y + xy + z + (x + y + xy)z = x + y + z + xy + xz + yz + xyz
 x * ( y * z) = x * (y + z + yz) = x + y + z + yz + x (y + z + yz) = x + y + z + xy + xz + yz + xyz

Se observa ca elementul neutru este 0 x * 0 = x + 0 + x0 = x, pentru orice x din N

2) Pe multimea R+ = [0,+infinity], se considera legea de compozitie: x * y = (x + y) / (1 + xy). Sa se arate ca (R+, *) este monoid.

legea de compozitie este asociativa
element neutru

Proof:

               x + y
(x * y) * z =  ------ * z =
               1 + xy

  x + y             x + y + z + xyz
  ------- + z       ---------------
  1 + xy            1 + xy
= -----------  =   ----------------
      x + y        1 + xy + xz + yz
  1 + ------ z     ---------------           
      1 + xy        1 + xy
  x + y + z + xyz
= ----------------  
  1 + xy + xz + yz

                   y + z
 x * (y * z) = x * ------
                   1 + yz

    y + z
x + ------
    1 + yz     x + y + z + xyz  
----------- =  ---------------
      y + z    xy + xz + yz + 1
1 + x -----    
      1 + yz             

      Se observa ca 0 este elementul neutru:
      x * 0 = x
      x + y    x + 0
      -----  = ------ = x, oricare ar fi x din R.
      1 + xy   1 + x0

Q.e.d      