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"
(→‎Monoid Operating on a Set: correction on definition of faithful)
 
(5 intermediate revisions by 2 users not shown)
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 ==
 +
 
 +
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>.
  
−
* <math>a \times (b \times c) = (a \times b)\times c</math> for all <math>a, b, c \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.
  
−
* 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 say that a monoid's action on <math>S</math> is ''faithful'' if the mapping <math>a\mapsto f_a</math> is [[injective]], i.e., for any distinct <math>a,b\in M</math>, there exists some <math>x\in S</math> for which <math>f_a(x) \neq f_b(x)</math>.
 +
 
 +
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 <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]].
  
−
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.
+
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>.
 +
We may also identify the function <math>f_a</math> with <math>a</math>, thus writing <math>a(x)</math> instead of <math>f_a(x)</math>.
  
 
{{stub}}
 
{{stub}}
 +
 +
[[Category:Abstract algebra]]

Latest revision as of 21:45, 21 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.

We say that a monoid's action on $S$ is faithful if the mapping $a\mapsto f_a$ is injective, i.e., for any distinct $a,b\in M$, there exists some $x\in S$ for which $f_a(x) \neq f_b(x)$.

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)$.

We may also identify the function $f_a$ with $a$, thus writing $a(x)$ instead of $f_a(x)$.

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

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