Monoid: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Jitse Niesen
(→‎Examples: I think you mean that the set of all functions X -> X form a monoid)
imported>Richard Pinch
(added on inverse and pseudoinverse elements)
Line 10: Line 10:
A ''[[commutative]] monoid'' is one which satisfies the further property that <math>x \star y = y \star x</math> for all ''x'' and ''y'' in ''M''.  Commutative monoids are often written additively.
A ''[[commutative]] monoid'' is one which satisfies the further property that <math>x \star y = y \star x</math> for all ''x'' and ''y'' in ''M''.  Commutative monoids are often written additively.


An element ''x'' of a monoid is ''invertible'' if there exists an element ''y'' such that <math>x \star y = y \star x = I</math>: the inverse may be written as <math>x^{-1}</math>.  The product of invertible elements is invertible,
An element ''x'' of a monoid is ''invertible'' if there exists an element ''y'' such that <math>x \star y = y \star x = I</math>: this is the ''inverse element'' for x and may be written as <math>x^{-1}</math>: by associativity an element can have at most one inverse (note that <math>x = y^{-1}</math> as well).  The identity element is self-inverse and the product of invertible elements is invertible,


:<math>(xy)^{-1} = y^{-1} x^{-1} \, </math>
:<math>(xy)^{-1} = y^{-1} x^{-1} \, </math>


and so the invertible elements form a group, the ''unit group'' of ''M''.
so the invertible elements form a group, the ''unit group'' of ''M''.
 
A ''pseudoinverse'' for ''x'' is an element <math>x^{+}</math> such that <math>x x^{+} x = x</math>.  The inverse, if it exists, is a pseudoinverse, but a pseudoinverse may exists for a non-invertible element.


A ''submonoid'' of ''M'' is a subset ''S'' of ''M'' which contains the identity element ''I'' and is closed under the binary operation.
A ''submonoid'' of ''M'' is a subset ''S'' of ''M'' which contains the identity element ''I'' and is closed under the binary operation.

Revision as of 11:02, 23 December 2008

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

In algebra, a monoid is a set equipped with a binary operation satisfying certain properties similar to but less stringent than those of a group. A motivating example of a monoid is the set of positive integers with multiplication as the operation.

Formally, a monoid is set M with a binary operation satisfying the following conditions:

  • M is closed under ;
  • The operation is associative
  • There is an identity element such that
for all x in M.

A commutative monoid is one which satisfies the further property that for all x and y in M. Commutative monoids are often written additively.

An element x of a monoid is invertible if there exists an element y such that : this is the inverse element for x and may be written as : by associativity an element can have at most one inverse (note that as well). The identity element is self-inverse and the product of invertible elements is invertible,

so the invertible elements form a group, the unit group of M.

A pseudoinverse for x is an element such that . The inverse, if it exists, is a pseudoinverse, but a pseudoinverse may exists for a non-invertible element.

A submonoid of M is a subset S of M which contains the identity element I and is closed under the binary operation.

A monoid homomorphism f from monoid to is a map from M to N satisfying

  • ;

Examples

  • The non-negative integers under addition form a commutative monoid, with zero as identity element.
  • The positive integers under multiplication form a commutative monoid, with one as identity element.
  • The set of all maps from a set to itself forms a monoid, with function composition as the operation and the identity map as the identity element.
  • Square matrices under matrix multiplication form a monoid, with the identity matrix as the identity element: this monoid is not in general commutative.
  • Every group is a monoid, by "forgetting" the inverse operation.

Cancellation property

A monoid satisfies the cancellation property if

and

A monoid is a submonoid of a group if and only if it satisfies the cancellation property.

Free monoid

The free monoid on a set G of generators is the set of all words on G, the finite sequences of elements of G, with the binary operation being concatenation (juxtaposition). The identity element is the empty (zero-length) word. The free monoid on one generator g may be identified with the monoid of non-negative integers