# Of the 16 binary operations on a two element set, which ones are commutative, associative, have an identity element, and have inverse?

If you you 16 binary operations

$$(a*a)=a$$ $$(a*b)=a$$ $$(b*a)=a$$ $$(b*b)=a$$

$$(a*a)=a$$ $$(a*b)=b$$ $$(b*a)=a$$ $$(b*b)=b$$

$$(a*a)=b$$ $$(a*b)=a$$ $$(b*a)=b$$ $$(b*b)=a$$

$$(a*a)=b$$ $$(a*b)=b$$ $$(b*a)=b$$ $$(b*b)=a$$

which of them (we can just label them 1-16) are commutative, associative, have an identity element, and have inverses?

My answer is 1-5, 8-9, and 12-16 are all commutative, 1-5, 8-9, and 13 are associative, and 1, 5, and 8 have identity elements and inverses.

My question is 1) are my answers correct and 2) could you please show your work for some of the identity and inverse ones; I did these in my head and am a bit confused because while my book lists and talks about 16 operations it's really 4 ways of combining 4 different operations and when I solved for the inverses and identity elements in my head and such I was realizing that 2 operations were often "linked" and I guess I'm just having trouble formalizing my thoughts so if you could go through some of these (like identity and inverse) thoroughly that would be great.

• You really shouldn't use $\ast$ when denoting multiplication on this site unless you're in math mode. Traditionally websites will interpret $\ast$ as a signifier for indentation. Aug 2, 2015 at 2:25
• This MathJax guide may help you make future questions easier to read: meta.math.stackexchange.com/questions/5020/… Aug 2, 2015 at 2:27
• Also, I think you are meant to read them in blocks of four.. i.e. the first batch of four defines a binary operation; the second batch of four defines another binary operation; etc. Aug 2, 2015 at 2:30
• When you say commutative, do you want to know which groups are commutative? Because if so 8-9 being commutative doesn't make sense. Aug 2, 2015 at 2:52
• You've given us only four binary operations, not $16$. ${}\qquad{}$ Aug 2, 2015 at 4:46

A binary operation on a set $A$ is a function from $A\times A \to A$, which means that it assigns exactly one element of $A$ to every ordered pair in $A \times A$.

In your example, $A=\{a,b\}$, so $$A\times A = \{(a,a),(a,b),(b,b),(b,a)\}$$

You can describe an operation on $A$ by saying exactly where it sends the four pairs (see Cameron Williams's comment).

Thus, for example, the second operation is the one that sends

$$(a,a) \text{ to } a, \text{ written } (a*a)=a\\ (a,b) \text{ to } b, \text{ written }(a*b)=b \\ (b,a) \text{ to } a, \text{ written } (b*a)=a \\ (b,b) \text{ to } b, \text{ written } (b*b)=b$$

To be commutative, an operation must send $(x,y)$ and $(y,x)$ to the same element for all $x,y \in A$. In the operation notation, this means that $$\forall x,y \in A, \; x*y=y* x$$

Is this true for the second operation? There are only two distinct elements, so we just need to check that $a*b =b*a$.

But we have $a*b=a \neq b=b*a$, which means the operation is not commutative.

Now, existence of the identity: the identity is an element that fixes every element in $A$. Is there an element $e$ in $A$ such that $$e *x=x* e=x \quad\forall x \in A?$$

To check this, you need to look at each of the elements in $A$:

The equation $$a*b=a \neq b=b*a$$ tells you that $a$ does not fix $b$ (because $a*b=a$) and that $b$ does not fix $a$ (because $b*a=b$). There are no more elements in $A$, so we can conclude that this operation does not have an identity.

Since it doesn't have an identity, it doesn't have inverses.

To check associativity, you need to check if performing the operation in a different order affects the result, i.e., if different ways of parenthesizing affect the result. The operation is associative if $$(x*y)*z=x*(y*z) \quad \forall x,y,z \in A$$

Note that $x,y,z$ in the definition are not necessarily distinct.

I'll let you check this one; the operation will be associative if all the following hold (just go through each using the definition of the operation, performing what's in parenthesis first):

$$(a*a)*a\overset{?}{=}a*(a*a)$$ $$(b*b)*b\overset{?}{=}b*(b*b)$$ $$(a*b)*a\overset{?}{=}a*(b*a)$$ $$(b*a)*a\overset{?}{=}a*(b*a)$$ $$(a*a)*b\overset{?}{=}a*(a*b)$$ $$(a*b)*b\overset{?}{=}a*(b*b)$$ $$(b*b)*a\overset{?}{=}b*(b*a)$$ $$(b*a)*b\overset{?}{=}b*(a*b)$$

The definitions will become less confusing as you practice them; try checking them for familiar operations on familiar sets. For example, try checking them for addition and subtraction on the integers.

• It sounds like although the author referred to the operations as 1-16, I'm wrong to think that he wants to determine if each of the 16 is commutative, associative, etc.? I should look at just the 4 operations as a whole? That is what's intuitive me, but I really thought the author wanted us to look at it as 16 operations. I'll redo them accordingly and post my responses. Thank you Aug 2, 2015 at 21:51
• Yes, it's four operations; but what do you mean by "should I just look at the 4 operations as a whole?"?. I think your example the one on page 21 of Pinter; the book says that "there are 16 possible operations on the set $A$," but before giving the ones you wrote in your question, it says "Here are a few of the possible operations," and before this he explains that each table gives one operation. Pinter's saying that there are 16 and is showing you 4 of them. Aug 2, 2015 at 21:58
• Ohhh...I thought the 16 operations were the 16 "options" given by the 4 tables on pg 21 for problem set C on pg 24. I did the whole problem wrong. This makes much more sense now. Thank you Aug 2, 2015 at 23:17
• Yup, for that problem you first have to come up with the 12 remaining operations. You're welcome :). Aug 2, 2015 at 23:26