Talk:Monoid

Why?

   * Associativity: for all a, b, c in M, (a∗b)∗c = a∗(b∗c)
   * Identity element: there exists an element e in M, such that for all a in M, a∗e = e∗a = a.
One often sees the additional axiom
   * Closure: for all a, b in M, a∗b is in M
though, strictly speaking, this is not necessary as it is implied by the notion of a binary operation.

Why? Doesn't Closure need to be defined for Associativity to be? --Carbonrodney 07:43, 16 November 2006 (UTC)

It's not saying that closure isn't needed, it's saying that we already have it, because we have a binary operation $M\times M\to M$. --Zundark

It seems it would be clearer and more consistent with the definitions of the Group and Category pages if the Closure property was surfaced as a top-level axiom. At the very least "binary operation" should be explicitly prefaced as "closed"- I had to reference http://en.wiki.x.io/wiki/Template:Group-like_structures in order to determine if Monoids were closed or not. --Domohawk

For me, the confusion is coming because of two different symbols × and •. I think we can write S × S → S as S • S → S and closure property will be implicit from definition --Mukesh Tiwari

S × S is the notation for Cartesian product, in other words, the set of pairs of elements of S. It is not intended to denote the same operation as the monoid operation •. Deltahedron (talk) 19:42, 6 September 2014 (UTC)

Computer Examples

could you give some examples related to computer ?

Lists with the concatenation operation, and the empty list is a monoid — Preceding unsigned comment added by 187.191.13.47 (talk) 23:24, 16 April 2013 (UTC)

Uniqueness of identity element

Under what situation is the identity element guaranteed to be unique? My off-the-cuff guess is that a cancellative monoid has a unique identity. Is there more to it than that? (Thanks!)

The identity is unique in every monoid. If e and f are two identities, then e = ef = f, so they are equal. -- Fropuff 15:13, 2004 Jul 29 (UTC)

Fixed Identity under Mappings

Can someone show me an example of when a homomorphism would not preserve the identity (assuming that wasn't given as an axiom)?

In my graduate abstract book, it doesn't state that a homomorphism must preserve identity (only an isomorphism) and leaves it as an exercise to construct an example to illustrate. However, in a different class, I was asked to show that a ring isomorphism preserves multiplicative identities (when present, obviously). As far as I can tell, I didn't make use of the fact that my mapping was bijective (1-1 and onto). Since my rings are additive groups and multiplicative monoids, then there should be no difference, unless the distributive law somehow differentiates the two types of monoids. -- Ub3rm4th 13:05, 2005 Jan 25 (UTC-6)

That is very strange. The whole point of a homomorphism is that it preserves the essential properties of the algebraic structure. If a monoid homomorphism doesn't preserve the identity, then it's just a semigroup homomorphism. --MarkSweep 19:24, 25 Jan 2005 (UTC)

For an example of a homomorphism not preserving the identity, consider a monoid involving a set with an identity element, e, and a non-identity element, say x, where x*x = x. If you define f to map all elements of its domain to this non-identity element, then f is a homomorphism because it satisfies f(ab) = f(a)f(b). The mapping f doesn't preserve the identity because it maps the identity element in its domain to x, the non-identity element. --Mike Fikes (talk) 03:31, 22 April 2008 (UTC)

Yep. Fairly standard terminology (although I'm sure you'll find somebody who disagrees!) is that a monoid homomorphism is a map between monoids which preserves the multiplication and the identity. Since monoids are also semigroups, there is also a notion of a "semigroup homomorphism of monoids", which as it turns out will preserve multiplication but not necessarily the identity. You can easily show that a homomorphic image of a monoid identity will act as a local identity for the image of the map, which is another way of saying that a surjective semigroup homomorphism always preserves an identity if present; hence the result for rings. Cambyses 05:37, 26 Jan 2005 (UTC)

Thank you very much. From my past experiences with wikipedia, I didn't expect answers so soon, so this is the first I've checked. For some reason, I like the answer that it would have to be a "semigroup homomorphism of monoids". My interpretation of homomorphisms was exactly that they preserve the structure of the system, thus I was deeply disturbed. I don't think my book (Hungeford) differentiates between a monoid homomorphism and a semigroup homomorphism of monoids. Much gratitude! -- Ub3rm4th 10:38, 07 Feb 2005 (UTC-6)

Uniqueness of inverses?

If an element in a monoid has an inverse is that inverse unique? Also why?

Yes, associtivity guarantees that inverses, if they exist, are unique. Suppose b and c are both inverses of a. Then

$c=ce=c(ab)=(ca)b=eb=b$

So b = c. -- Fropuff 00:24, 13 January 2006 (UTC)

Why magma in definition?

The term 'magma' is quite unnecessary in encyclopedic definition of monoid. Very few people use this word outside Bourbaki circles. The idea to insert an obscure term in a definition or an explanation - for students etc - is simply ridiculous.

Of course we need an article for magma, but it does not mean we should stick this word everywhere.

I tend to agree. I'll remove it for now. -- Fropuff 03:23, 28 March 2006 (UTC)

Recursively adding an identity?

The fourth example stated:

Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining ee = e and es = s = se for all s ∈ S. This can be done recursively (i.e. if S is monoid with identity e, one obtains a new monoid S ∪ {e′} with identity e′, and so on).

I removed the last sentence because by adjoining an identity e′ to a monoid with identity e simply gives e = e′ and the monoids are isomorphic.

No, that is false. Instead, given a monoid N with identity e (which is of course a semigroup), we can always embed N in a monoid M with identity e′ distinct from e; and if |N| is finite, this embedding cannot yield an isomorphism. (This is never the case if, e.g., we replace "monoid" with "group"). 71.198.111.245 20:05, 2 June 2007 (UTC)

If someone can think of a compelling reason to keep this "recursive" construction method in please say so. TooMuchMath 21:04, 10 April 2006 (UTC)

As far as regards the usefulness of the construction, I agree; except to demonstrate that monoid endomorphisms (which preserve the identity) and monoid homomorphisms aren't coincident. 71.198.111.245 20:05, 2 June 2007 (UTC)

Every monoid contains a group?

Is it true that "every monoid contains a group" as written in the article? For example, if Z+ forms a monoid over multiplication with identity one, what group is made with Z+? I assume that to form a group, that set would need to be augmented with inverses. Maybe the word "contains" is misleading me. I can see how every group contains a monoid, but not vice-versa. - Simian1k 15:24, 13 April 2006 (UTC)

I don't know why the article bothers to mention it, but it's certainly true: every monoid contains at least the trivial group {1}. --Zundark 17:42, 13 April 2006 (UTC)

If you consider all the units in a monoid as a set they form a submonoid (IE the set is closed under *) that is also a group (inverses are present). This is the largest group contained in the monoid.

We need to be a bit careful regarding what we mean by a "group contained in the monoid" here. If we mean "a subset of the monoid M which is a group w.r.t. the identity of M", then there is even a unique subset G of M which is maximal w.r.t. this property. On the other hand, consider the group C_7. As with any semigroup, it can be embedded in a monoid M = C_7 union {e} of order 8. The largest subset which is a group is of order 7; but the set of units has order 1. 71.198.111.245 20:05, 2 June 2007 (UTC)

For some monoids the group of units is trivial, however there are examples where this is not the case. Consider $M=<x,y|x^{5}=1,y^{5}=y^{2},[x,y]=1>$. This is the (monoid) direct product of two cyclic monoids. The submonoid $<x>$ is a group isomorphic to Z/5Z and the submonoid $<y>$ is not a group. The set of units of M is given by the submonoid $<x>$, IE the only elements of M which are invertible are powers of x.

Thank you for clearing that up. --Simian1k 16:01, 14 April 2006 (UTC)

unify or clarify the following statements in the article

These appear to be two different ways of saying the same thing: 1) A monoid satisfies all the axioms of a group with the exception of having inverses. A monoid with inverses is the same thing as a group; 2)If a monoid has the cancellation property and is finite, then it is in fact a group. drefty.mac 08:15, 28 October 2006 (UTC)

They are not really the same thing. Cancellativity is (in general) a necessary but not a sufficient condition for the existence of inverses. So (1) does not immediately imply (2). And (2) is a statement only about finite monoids (it is false if you remove the hypothesis of finiteness) so it can't imply (1) in the general (possibly infinite) case. (Of course in a strict logical sense, any two statements which are provable imply each other, but you know what I mean.... :-). Best wishes, Cambyses 11:21, 23 November 2006 (UTC)

Addition operator

The article states that there is a preordering if and only if there is a z such that x+z=y. But the addition operator is not defined. What am I missing? —Preceding unsigned comment added by 82.235.223.112 (talk)

It's just the binary operation of the commutative monoid. I'll add a note to make this clearer. --Zundark 12:55, 8 May 2007 (UTC)

Add pointer to Magma Definition

One might want to add a pointer to the definition of Magma since it now exists in the Wikipedia. --Gdinolt 17:43, 21 May 2007 (UTC)

Generators / Submonoids

The article states:

Equivalently, a submonoid is a subset N such that N=N*, where the superscript * is the Kleene star. For any subset N of M, the monoid N* is the smallest monoid that contains N.

First, strictly speaking, in the article on Wikipedia the Kleene star forms sets of strings of symbols from sets of symbols. Strings of symbols are not themselves symbols without some sort of (generally not injective) mapping. Of course, the mapping here is pretty obvious from context - if we already know what's going on, which should not be the point of view of the article IMO. A better link than to Kleene star explaining this idea might be free monoid or free object and some sort of discussion of presentation of a monoid similar to the article on presentation of a group.

Secondly, define (M,*) on the set {1,x} as: 1*1 = 1, 1*x = x*1 = x; x*x = x. M is a monoid. Let N = {x}. The semigroup (N,*\N} meets the requirement of being a monoid of order 1. Is "the smallest monoid containing N" meant to be (N,*\N), or is it meant to be (M,*)? Equivalently, is {x} a submonoid of {1,x}? (Note that this confusion cannot arise with subgroups of a group).

All of my comments here seem to revolve around the question of whether there is a preferred identity element 1 which is determined by the fact that we are working in the context of a /particular/ monoid M. Since monoids often are encountered as the multiplicative monoid of a ring with identity 1, I would expect that we usually map the empty string in N* to this 1, and not some other element of M; and that a submonoid N of M must contain 1; and that a group G embedded in M is assumed to be a submonoid of M. But I could be wrong! 71.198.111.245 20:05, 2 June 2007 (UTC)

Actions

The sentence "This is the analogue in monoid theory of a (left) group action" seems a bit out of place in an article on monoids: what is "monoid theory" if not this article? Maybe it was meant to be "group theory"? Actually the article on group theory should refer to this article's treatment of actions, since a group is the same thing as a monoid whose left and right actions are all invertible; the fact that both left and right are invertible allows the element itself to have an inverse. --Vaughan Pratt (talk) 09:07, 24 December 2008 (UTC)

Definition of monoid

Rewrote the definition of monoid to link to binary operation instead of operation. It is not necessary to say how to pronounce a symbol such as "•" but I put one in anyway. I also left out the closure property, which is old fashioned and included in the definition of binary operation. However, I notice that it is also used in the definitions of group and semigroup. Is there some kind of editorial policy about this? SixWingedSeraph (talk) 03:17, 16 November 2009 (UTC)

Im sorry but I have changed your definition back to include closure as one of the axioms. I left in the link to binary operation but I removed text in parenthesis which explains that a binary operation implies closure, as I think that this is just a distraction and makes it more difficult to understand the definition. If you look at the articles on group, semigroup and ring you will see that all of them link to binary operation and at the same time also include the closure axiom in their definitions, even though the term binary operation implies closure. As another example, you can see that Wolfram MathWorld defines a monoid as a "set that is closed under an associative binary operation and has an identity element." And to be honest, the real reason that I was compelled to add back the closure property to this definition is because it completely threw me off. When I looked at your definition (and I admit I did not read it very closely) I noticed that closure property was missing and erroneously assumed that this must mean that the definition of monoid does NOT require closure, which I found to be very surprising and it took me a few minutes of searching to figure out that the closure property was simply missing from the definition of this article. So I humbly submit to you that adding the closure property might be old fashioned but is more user friendly and could prevent some possible confusion. -99.242.17.45 (talk)

Suggestion: Definition and later references should be changed from pair (M,•) to triple (M,•,e). This follows some kind of normalization rules for universal algebras (including heterogenous algebras): Axioms with $\exists$ should be avoided (if possible). As the identity element is unique, it is a constant and should be reffered to in the describing n-tuple (regarding it as a nullary operation). That is, any describing n-tuple does contain the underlying set(s), follwed by the operations (with decreasing n-ary). In our case, these ideas result in a triple (M,•,e). You may also refer to de:Monoid. Kind regards--Ernsts (talk) 20:27, 1 January 2018 (UTC)

find-first monoid, find-last monoid

I can not find any reference to those. I guess that a find-first monoid is a monoid where, if an element is not neutral, it is left-absorbing. I doubt that "idempotent monoid" and "find-first monoid" coincide. An idempotent monoid is a monoid whose binary operation is idempotent. Every find-first monoid is idempotent.

Consider the monoid with the following table of the binary operation:

	*	0	1
*	*	0	1
0	0	0	1
1	1	1	1

(In other words, this is the semigroup $(\{0,1\},\lor )$, turned by the free functor into the monoid.) The monoid is idempotent. 0 is not neutral and is not left-absorbing. The monoid is not find-first. --Beroal (talk) 12:54, 15 January 2011 (UTC)

Monoid congruence definition is lacking

Monoid congruence redirects here, but aside from its use in the section about presentations and the corresponding article on a presentation of a monoid, it is not mentioned. This is a problem, because no definition is given, so the redirect of monoid congruence to this article is really a dead end. Can someone who knows the definition of a monoid congruence please add the definition to this article? Furby100 (talk) 14:47, 26 April 2012 (UTC)

I guess it is a particular case of Congruence relation. I changed that redirection. --Beroal (talk) 15:50, 4 May 2012 (UTC)

The "unit element"

The current article says "A submonoid of a monoid M is a subset N of M containing the unit element", but I don't see a definition for "unit element" that preceeds this. I assume it means "identity element" in this context. Tashiro (talk) 01:19, 7 October 2012 (UTC)

Fixed. — Quondum 05:38, 4 September 2013 (UTC)

Definition of submonoid

I have changed the definition of a submonoid to match that of Jacobson, effectively reversing my earlier change that excluded the requirement that it include the identity of the enclosing monoid. This is in line with a change of semantics from a subset that is a monoid under the monoid's binary operation to a subset that preserves the defined structure of the monoid, with the identity element being regarded as part of the defined structure (as in category theory, where it is regarded as a nullary operation). This is compatible with the definition of a monoid homomorphism in this article, in the sense that the submonoids of a monoid are precisely the images of the monoid endomorphisms.

It may be noted that there are conflicting, but less notable, web definitions such as [1], [2] and [3], which prompted my earlier edit. An article should give due weight to conflicting definitions. I leave it to others to determine whether this conflicting definition deserves more than the footnote that I included. — Quondum 11:42, 26 September 2013 (UTC)

Suggested tweaks to new illustration

I like the new illustration File:Exponentiation as monoid homomorphism.pdf added, but would like to suggest some tweaks to the diagram:

• Since we are dealing with the standard, known operations, the diagram should use the standard symbols, to wit: the monoid under multiplication should have its operation denoted ×, not *.
• Since (N,×) is a monoid and is a suitable codomain for the indicated mapping, there is no benefit in excluding 0. Excluding zero risks creating the impression that 0 must be excluded for some reason, and we should not do so, so I suggest including it in the multiplication table.
• It is sufficient to indicate the mapping on one axis only. I would suggest removing the arrows from the second axis, as the double mapping slows interpretation.

— Quondum 23:14, 9 October 2013 (UTC)

Thanks, Jochen, for updating it as I suggested. I think that works very well. — Quondum 18:45, 10 October 2013 (UTC)

Monoid vs. group

The only difference between monoid and group is that in a group each element is required to have an inverse. There is no "nontrivial theorem" needed to prove this; it is what the definitions currently on Wikipedia say. (The axioms are exactly the same, except for the existence of inverses.) Ebony Jackson (talk) 22:48, 7 December 2013 (UTC)

Please be direct with your language

Subtle coincidence does not make the cut for encylopedic entries, I am going to edit the statement on identity element so that it states "There exists an element e in S such that for every element a in S, the equation e • a = a • e holds" as it makes no sense as written unless the typo was not as I will edit from and the correct statemeant is "There exists an element e in S such that for every element a in S, the equations e • a = a • e = a holes" . -Dirtclustit (talk) 15:03, 10 May 2015 (UTC)

Monoid homomorphisms

In the section about monoid homomorphisms one can read "In contrast, a semigroup homomorphism between groups is always a group homomorphism, as it necessarily preserves the identity."

Can you please explain why this is always the case?--Suitangi (talk) 16:14, 24 July 2018 (UTC)

MapReduce

The whole section on MapReduce is written in vague terms. It's not clear what the monoid is. Also it's not clear whether it is an actual application in the sense that the monoid terminology helps one understand it, or whether it is just something that turns out to be a monoid. Unless a clearer description of the relevance can be given, I would suggest removing the section. Ebony Jackson (talk) 18:12, 2 January 2022 (UTC)

I suggest to make it a subsection of "Monoids in computer science", since "Reduce" is a synonym for "fold", as far as I know. The text should be copy-edited; it could follow some easy-to-grasp application example from "big data", which probably can be found in the MapReduce article. I suspect that the work of Richard Bird, Lambert Meertens etc. on algebraic methods in functional programming (Bird–Meertens formalism) is part of the theoretic foundation of MapReduce, without being recognized or acknowledged by most applied computer scientists. - Jochen Burghardt (talk) 20:07, 2 January 2022 (UTC)

Monoids in computer science

Is the operation "fold" simply taking a sequence to its product? What is the purpose of giving the more complicated displayed equation? Ebony Jackson (talk) 18:14, 2 January 2022 (UTC)

The first answer is "yes".

The second is something like this: Sequences in computer science are often built from the constructors nil:List(A) and cons:A×List(A)→List(A), which goes back to the Lisp programming language ("A" denotes the element type). Then it is natural to define a function, like fold:List(A)→A, recursively over these constructors ("structural recursion"). The "monoid multiplication", i.e. concatenation of two lists, needn't even be considered in this approach. It can, of course, be defined by recursion over nil and cons, too, and is called append in Lisp. - Jochen Burghardt (talk) 19:56, 2 January 2022 (UTC)

Thank you for the reply. Yes, it is pseudo-Lisp. I think the binary operation being used here is not concatentation of elements of M^*, but the binary operation on M. The recursive definition of product of a finite sequence is already given earlier in the article, using less clumsy notation. The section claims "any data structure can be 'folded' in a similar way, given a serialization of its elements", but this cannot be taken at face value - this certainly does not apply to every type listed at the data structure page. I think that the section is trying to say something more than just that one can take the product of a finite sequence of elements of a monoid, since it speaks of binary trees (in terms that are too vague for me to understand). It is also unclear what is meant by "many abstract data types can be endowed with a monoid structure" - what data types are we talking about, what is the underlying set, and what is the binary operation? In the sentence "For instance, many iterative algorithms need to update some kind of running total at each iteration; this pattern may be elegantly expressed by a monoid operation", what does it mean to "express a pattern by a monoid operation"? I don't want to delete the whole section, since certainly monoids do arise in computer science, but the present text is not doing justice to the topic, I feel. Ebony Jackson (talk) 22:33, 2 January 2022 (UTC)

Trace Monoids

So far as I am aware, trace monoids are always infinite. However, $\{1,a,a^{2}\}$ with $a^{3}=a^{2}$ is a finite (partially) commutative monoid which is not a trace monoid. (I came to this article searching for a definition of an abstract trace monoid.) I propose changing "A monoid for which the operation is commutative for some, but not all elements is a trace monoid; trace monoids commonly occur in the theory of concurrent computation" to "One type of monoid for which the operation is commutative for some, but not necessarily all, generators is the trace monoid; trace monoids commonly occur in the theory of concurrent computation". Note that x² • x = x • x² for all monoids, so saying 'element' is not good. --RichardW57m (talk) 16:08, 4 April 2022 (UTC)