What is a monoid?

[BeuysVonTelekraft]

I've searched on wikipedia and wolfram mathworld, and i have a definiton on a book right in front of me:

 

Definition: A monoid is a pair (M, *) where M is a set and * : M x M -> M is a binary operation with the following properties:

 

After that there are some properties.

 

But I still can't understand it. Can you help me?

 

Thanks in advance.

[the tree]

Do you fully understand the concept of a set?

Do you fully understand the concept of a binary operation?

[BeuysVonTelekraft]

I do understand the concept of set, but not the concept of binary operation.

[the tree]

"A binary operation on a set S [...] maps elements of the Cartesian product S×S to S" _{-- WikiP}

 

The most obvious example of a binary operation would be addition, or possibly multiplication. Although it should cover any function that takes two inputs and gives one output, all from the same set.

Edited November 10, 2011 by the tree

[John Cuthber]

Perhaps it's helpful to make the comparison with a unary function.

Sin(x) only needs one operand: so do x^2 or 1/x. They are unary.

 

On the other hand, addition (for example) needs two numbers.

 

Another rather convoluted difference is that you don't (generally) need to push the "=" button on your calculator to calculate a unary function, but you do with binary functions.

[BeuysVonTelekraft]

I understand now what is a binary operation, now i have a problem with your statement:

 

A binary operation on a set S [...] maps elements of the Cartesian product S×S to S

 

I've read a definition on wikipedia about cartesian product:

 

For example, the Cartesian product of the 13-element set of standard playing card ranks {Ace, King, Queen, Jack, 10, 9, 8, 7, 6, 5, 4, 3, 2} and the four-element set of card suits {♠, ♥, ♦, ♣} is the 52-element set of all possible playing cards: ranks × suits = {(Ace, ♠), (King, ♠), ..., (2, ♠), (Ace, ♥), ..., (3, ♣), (2, ♣)}.

 

And i have this questions:

 

-This kind of mapping make sense to me (the playing cards), but why would I map the elements of the cartesian product SxS to S?

 

-Are there other kinds of binary operation on sets?

 

-Are sets the same thing of lists in programming? I guess so, their nature seems identical.

 

-When he says: (M, *), what's the meaning of *?

 

Thanks in advance.

 

 

 

[the tree]

Why would I map the elements of the cartesian product SxS to S?

Say S were the set of integers, then addition over the integers would be a mapping from SxS to S. Addition is useful, so it is rumored.

 

If you were to draw up a multiplication table then you'd see a fairly obvious example of mapping ZxZ to Z.

 

-Are there other kinds of binary operation on sets?

Other than what?

 

 

-Are sets the same thing of lists in programming? I guess so, their nature seems identical.

No. Not at all. Lists allow for repetition and have an inherent order. Sets do not have repeated elements and a set written in a different order is the same set.

 

-When he says: (M, *), what's the meaning of *?

That's the name of the operation in question. e.g. addition over the integers would be written (Z,+).

[BeuysVonTelekraft]

Say S were the set of integers, then addition over the integers would be a mapping from SxS to S. Addition is useful, so it is rumored.

 

If you were to draw up a multiplication table then you'd see a fairly obvious example of mapping ZxZ to Z.

 

Oh, i got it now.

 

Other than what?

 

The x in the middle of ZxZ indicates this binary operation is a cartesian product, right? So, this is a binary operation, are there other kinds of binary operations that are not cartesian product?

 

That's the name of the operation in question. e.g. addition over the integers would be written (Z,+).

 

Then, the monoid is something that suggest a operation inside a set, right?Could it suggest only binary operations or is it possible to suggest a n-ary operation?

 

Thanks in advance.

 

 

 

[the tree]

The x in the middle of ZxZ indicates this binary operation is a cartesian product, right? So, this is a binary operation, are there other kinds of binary operations that are not cartesian product?

Oh heavens no. The SxS is what * maps from and S is what * maps to.

 

A Cartesian product is technically an example of a binary operation, but for the sake of this discussion - it's not the one that you're talking about.

 

For solid examples of binary operations, you'll find that finite monoids make easily drawn tables.

 

Then, the monoid is something that suggest a operation inside a set, right?

The common vernacular is 'over' the set, but yes, sort of. A monoid is both the set, and the operation.

 

Could it suggest only binary operations or is it possible to suggest a n-ary operation?

That would be something, but it would not be called a monoid.

[BeuysVonTelekraft]

Got it. Now there's another concept on the book: Monoid Homomorphism.

 

Given two monoids [Math] (M, *M)[/Math]and [Math] (N, *N)[/Math], a monoid homomorphism [Math]f : (M, *M) \rightarrow (N, *N)[/Math] is a map of sets [Math] f: M \rightarrow N[/Math]

 

I understand the mapping, and the meaning of the monoid [Math] (M,*)[/Math], but i have no clue of the meaning of [Math](M, *M) [/Math].

 

The homomorphism, as the name suggests, seems to be making both sets having the same elements, am i right?

[the tree]

Notation wise, that's just horrible. And it's quite understandable that you'd be confused.

 

What it's trying to do is to give a more distinct name to the operation. (M,*_M) and (N,*_N) would be two monoids, consisting of a set each and an operation each - the point of calling the operations *_M and *_N is to make it clear that the two operations needn't be the same.

 

 

A homomorphism is a function that preserves structure. You'll see a list of conditions in your text book, but what they amount to is that while each monoid will consist of elements with different names, once you strip that away - if a homomorphism exists between them then they will be equivalent to one another. If you're familiar with the meaning of symmetry, then this is a very similar concept. If not, then you'll just have to work through a lot of examples.

[BeuysVonTelekraft]

I kinda modeled a monoid on Mathematica:

 

 

 

I'm not very sure if i'm right on them. But what would happen in the case of the homomorphism of these monoids?

[the tree]

That depends on what the binary operation is, in each case, that makes them more than just sets. If you can think of a binary operation that maps {(4,4),(4,9),...} to {4,9}, that meets the conditions to make it a monoid - and another for {(8,8),...} then there may or may not be a homomorphism between the monoids that you will have created.

 

To be clear on that, different binary operations can make for different monoids - even with the same set.

 

For instance, let [imath]S=\{ a,b \}[/imath] and take two binary operations, [imath]\circ_1[/imath] and [imath]\circ_2[/imath] that are defined thusly:

 

[math]\begin{array}{c|cc} \circ_1 & a & b \\

\hline

a&a&b\\

b&b&a\\

\end{array}[/math]

 

[math]\begin{array}{c|cc} \circ_2 & a & b \\

\hline

a&a&b\\

b&b&b\\

\end{array}[/math]

 

 

Both [imath](S , \circ_1 )[/imath] and [imath](S , \circ_2 )[/imath] are monoids, but they are non-equivalent because no homomorphism exists between them.

 

Now let [imath]T=\{ c , d \}[/imath] and define [imath]\circ_3[/imath] thusly:

 

[math]\begin{array}{c|cc} \circ_3 & c & d \\

\hline

c&c&d\\

d&d&c\\

\end{array}[/math]

 

There exists a homomorphism between [imath]( T , \circ_3 )[/imath] and [imath]( S , \circ_1 )[/imath], making them equivalent monoids.

Edited November 15, 2011 by the tree

[BeuysVonTelekraft]

Can i say: Map it to n, instead of map it to {4,9}?

 

And, where can i find all possible binary operations? I've searched a little but i can't find it.

 

 

Edited November 15, 2011 by BeuysVonTelekraft

[the tree]

The definition of a monoid requires a binary operation mapping from SxS to S.

 

And, where can i find all possible binary operations? I've searched a little but i can't find it.

Brute force I guess.

[BeuysVonTelekraft]

I guess the word is not "possible", the word is "known".

[the tree]

Of a set S of size |S|=n. It's clear that |SxS|=n², so n³ binary operations mapping SxS to S. The amount that would make a monoid would be less than that (I feel it's getting a little late for combinatronic questions right now). I don't think there would be a means of listing them all other than brute force.

Edited November 15, 2011 by the tree

[BeuysVonTelekraft]

So, if there are lots of possible operations. How will i know what operation should i do?

[DrRocket]

I do understand the concept of set, but not the concept of binary operation.

 

What you have been told is correct, but let's try a slightly different tack.

 

Think of a binary operation as a generalization of multiplication or addition. So, given elements a and b from your set, call it M, a*b is another element and "*" is the binary operation.

 

For a monoid * is required to satisfy the following 2 properties:

 

1. Associativity --- a*(b*c)=(a*b)*c

 

2. Identity element --- There is an element I, called an identity, such that I*a=a*I=a for any a in M

 

 

If in addition "*" satisfies the requirement that

 

3. Invertibility -- for any a in M there is a b in m such that a*b=b*a=I

 

then the monoid is called a group. A typical example of a group are the nxn invertible matrices for some fixed n with entries taken from thev real (or complex) numbers. Groups are one of the vfundamental structures studies in abstract algebra courses. Monoids have less structure, lacking invertibility.

 

If only property 1 is satisfied then your set M is called a semigroup. So a monoid can also be called (and commonly is) a "semigroup with identity".

 

Quite commonly the bibary operation is written simply as multiplication, so as "ab" rather than "a*b".

 

Note that the following property has NOT been required

 

4. Commutativity -- a*b=b*a

 

In general, even when written as simple multiplication, the operation is not assumed to be commutative (think of matrix multiplication). When the operation is commutative the algebraic structure is called "commutative" or " Abelian" (after the famous mathematician Niels Henrik Abel). So one can have an Abelian group, an Abelian semigroup, or an Abelian monoid or equivalently a commutative group, a commutative semigroup or commutative monoid.

[the tree]

So, if there are lots of possible operations. How will i know what operation should i do?

Should? There's no particular criterion to pick between two monoids unless they are for something specific. Edited November 17, 2011 by the tree

[DrRocket]

So, if there are lots of possible operations. How will i know what operation should i do?

 

 

A good surgeon will naturally pick the best operation.

 

Mathematicians work with the operation at hand, or invent one that provides insight in the situation that is presented. Quite often there are several operations available simultaneously, and the result is a richer algebraic structure , like a module, vector space or algebra. But in the case of a monoid one considers a very restrictive case, and only one operation is under consideration.

 

Where is it that you are encountering the concept of a monoid ? Quite typically one's first exposure to abstract algebra is via groups. There is much more that can be said about groups. If you have a particular text that you are reading, please tell us what it is. If not, I can recommend Michael Artin's Algebra.

[BeuysVonTelekraft]

A good surgeon will naturally pick the best operation.

 

Mathematicians work with the operation at hand, or invent one that provides insight in the situation that is presented. Quite often there are several operations available simultaneously, and the result is a richer algebraic structure , like a module, vector space or algebra. But in the case of a monoid one considers a very restrictive case, and only one operation is under consideration.

 

Where is it that you are encountering the concept of a monoid ? Quite typically one's first exposure to abstract algebra is via groups. There is much more that can be said about groups. If you have a particular text that you are reading, please tell us what it is. If not, I can recommend Michael Artin's Algebra.

I am reading it here:

 

 

http://www.amazon.com/Rubato-Composer-Music-Software-Component-Based/dp/3642001475