Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Monoid"

m
(added some)
Line 1: Line 1:
−
A '''monoid''' is a set <math>S</math> with an [[operation]] <math>\times</math> which is [[associative]] and has an [[identity]].  That is, <math>M = (S, \times)</math> is a monoid if and only if
+
A '''monoid''' is a set <math>S</math> closed under an [[operation]] <math>\times</math> which is defined everywhere on <math>S</math>, is [[associative]], and has an [[identity]] in <math>S</math>.  That is, <math>M = (S, \times)</math> is a monoid if and only if
 +
* There is a well-defined element <math>a \times b</math> of <math>S</math>, for all <math>a,b \in S</math>;
 +
* <math>a \times (b \times c) = (a \times b)\times c</math> for all <math>a, b, c \in S</math>;
 +
* There is an element <math>e \in S</math> such that <math>e\times a = a \times e = a</math> for all <math>a \in S</math>.
 +
Alternatively, a monoid can be thought of as a [[group]] without [[inverse with respect to an operation | inverses]], or as an associative [[magma]] with an identity.
 +
 
 +
By abuse of notation, we often identity a monoid with its underlying set.  That is, we often refer to a monoid <math>(S,\times)</math> simply as the monoid <math>S</math>, when there is no risk of confusion.
 +
 
 +
Because the conditions on monoids are so weak, there are very few theorems of "monoid theory."  However, monoids do arise from time to time in the study of [[abstract algebra]], and many objects (such as all groups, as well as any [[ring]] with respect to either of its operations) are in fact monoids.
 +
 
 +
== Monoid Operating on a Set ==
  
−
* <math>a \times (b \times c) = (a \times b)\times c</math> for all <math>a, b, c \in S</math>
+
Let <math>M</math> be a monoid whose law of composition is written multiplicatively and whose identity is <math>e</math>, and let <math>S</math> be a set.  Let <math>S^S</math> be the set of [[function]]s on <math>S</math>.  We call a mapping <math>a \mapsto f_a</math> from <math>M</math> to <math>S^S</math> a ''left operation of <math>M</math> on <math>S</math>'' if <math>f_e</math> is the identity map on <math>S</math> and for all <math>a,b</math> in <math>M</math>,
 +
<cmath> f_{ab} = f_a \circ f_b . </cmath>
 +
(A right operation is defined similarly, except that <math>f_{ab} = f_b \circ f_a</math>.)
 +
In other words, a left operation of <math>M</math> on <math>S</math> is a [[homomorphism]] from the monoid <math>M</math> to the monoid <math>S^S</math>; a right operation is a homomorphism into the opposite monoid of <math>S^S</math>.
  
−
* There is an element <math>e \in S</math> such that <math>e\times a = a \times e = a</math> for all <math>a \in S</math>.
+
We may also say that <math>M</math> acts on <math>S</math>.  A set <math>S</math> with an action of a monoid <math>M</math> on <math>S</math> is called an <math>M</math>-set.
  
 +
Every monoid acts on the set of its elements.
  
−
Alternatively, a monoid can be thought of as a [[group]] without [[inverse with respect to an operation | inverses]].
+
Often one speaks of groups acting on sets.  Since elements groups must have unique inverses, for every <math>a</math> in a group <math>G</math> acting on a set <math>S</math>, the function <math>f_a</math> must be a [[bijection]].
  
 +
If <math>x</math> is an element of <math>S</math>, and <math>a</math> is an element of a monoid <math>M</math> with a left operation on <math>S</math>, we often write <math>f_a(x)</math> simply as <math>ax</math>, when there is no risk of confusion.  Then we may rewrite our criteria thus, for <math>a,b</math> in <math>M</math> and <math>x</math> in <math>S</math>.
 +
* <math>ex = x</math>;
 +
* <math>(ab)x = a(bx)</math>.
  
−
Because the conditions on monoids are so weak, there are very few theorems of "monoid theory."  However, monoids do arise from time to time in the study of [[abstract algebra]], and many objects (such as all groups, as well as any [[ring]] with respect to either of its operations) are in fact monoids.
 
  
 
{{stub}}
 
{{stub}}
 +
 +
[[Category:Abstract algebra]]

Revision as of 22:09, 13 May 2008

A monoid is a set $S$ closed under an operation $\times$ which is defined everywhere on $S$, is associative, and has an identity in $S$. That is, $M = (S, \times)$ is a monoid if and only if

  • There is a well-defined element $a \times b$ of $S$, for all $a,b \in S$;
  • $a \times (b \times c) = (a \times b)\times c$ for all $a, b, c \in S$;
  • There is an element $e \in S$ such that $e\times a = a \times e = a$ for all $a \in S$.

Alternatively, a monoid can be thought of as a group without inverses, or as an associative magma with an identity.

By abuse of notation, we often identity a monoid with its underlying set. That is, we often refer to a monoid $(S,\times)$ simply as the monoid $S$, when there is no risk of confusion.

Because the conditions on monoids are so weak, there are very few theorems of "monoid theory." However, monoids do arise from time to time in the study of abstract algebra, and many objects (such as all groups, as well as any ring with respect to either of its operations) are in fact monoids.

Monoid Operating on a Set

Let $M$ be a monoid whose law of composition is written multiplicatively and whose identity is $e$, and let $S$ be a set. Let $S^S$ be the set of functions on $S$. We call a mapping $a \mapsto f_a$ from $M$ to $S^S$ a left operation of $M$ on $S$ if $f_e$ is the identity map on $S$ and for all $a,b$ in $M$, \[f_{ab} = f_a \circ f_b .\] (A right operation is defined similarly, except that $f_{ab} = f_b \circ f_a$.) In other words, a left operation of $M$ on $S$ is a homomorphism from the monoid $M$ to the monoid $S^S$; a right operation is a homomorphism into the opposite monoid of $S^S$.

We may also say that $M$ acts on $S$. A set $S$ with an action of a monoid $M$ on $S$ is called an $M$-set.

Every monoid acts on the set of its elements.

Often one speaks of groups acting on sets. Since elements groups must have unique inverses, for every $a$ in a group $G$ acting on a set $S$, the function $f_a$ must be a bijection.

If $x$ is an element of $S$, and $a$ is an element of a monoid $M$ with a left operation on $S$, we often write $f_a(x)$ simply as $ax$, when there is no risk of confusion. Then we may rewrite our criteria thus, for $a,b$ in $M$ and $x$ in $S$.

  • $ex = x$;
  • $(ab)x = a(bx)$.


This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Monoid&oldid=25988"