[BeuysVonTelekraft]

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

Quote

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.

This post has been edited by the tree: 10 November 2011 - 10:17 PM

[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:

Quote

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:

Quote

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]

BeuysVonTelekraft, on 13 November 2011 - 03:35 AM, said:

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.

BeuysVonTelekraft, on 13 November 2011 - 03:35 AM, said:

-Are there other kinds of binary operation on sets?

Other than what?

BeuysVonTelekraft, on 13 November 2011 - 03:35 AM, said:

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

BeuysVonTelekraft, on 13 November 2011 - 03:35 AM, said:

-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]

Quote

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.

Quote

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?

Quote

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]

BeuysVonTelekraft, on 13 November 2011 - 06:30 PM, said:

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.

BeuysVonTelekraft, on 13 November 2011 - 06:30 PM, said:

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.

BeuysVonTelekraft, on 13 November 2011 - 06:30 PM, said:

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 and , a monoid homomorphism is a map of sets

I understand the mapping, and the meaning of the monoid , but i have no clue of the meaning of .

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 and take two binary operations, and that are defined thusly:






Both and are monoids, but they are non-equivalent because no homomorphism exists between them.

Now let and define thusly:



There exists a homomorphism between and , making them equivalent monoids.

This post has been edited by the tree: 15 November 2011 - 12:50 AM

[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.

This post has been edited by BeuysVonTelekraft: 15 November 2011 - 12:51 AM

[the tree]

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

BeuysVonTelekraft, on 15 November 2011 - 12:50 AM, said:

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.

This post has been edited by the tree: 15 November 2011 - 01:05 AM

[BeuysVonTelekraft]

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

[DrRocket]

BeuysVonTelekraft, on 10 November 2011 - 05:08 PM, said:

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]

BeuysVonTelekraft, on 17 November 2011 - 01:24 PM, said:

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.

This post has been edited by the tree: 17 November 2011 - 06:53 PM