# Non-associative, non-commutative binary operation with a identity

Can you give me few examples of binary operation that it is not associative, not commutative but has an identity element?

• Does it have to be both a left- and right- identity? – Mitch Mar 14 '11 at 14:34
• Vafa, maybe you should hand in your assignment before you post it here. – Gerry Myerson Mar 15 '11 at 0:23
• @Gerry Myerson: If I have posted one question from the assignment here, it does not mean that I am going to copy verbatim solutions from here into my solution of the assignment. In fact, as you will see in my solution, I have given a different example. I posted the question here because I was interested to see other binary operations that I could not think of. Next if I ever wanted to copy solutions from here into my solution manual, I would not be that stupid to ask the question with my real name and identity. (if this is ever what you meant.) – Vafa Khalighi Mar 15 '11 at 1:34
• @Mitch: Yes, so if e is your identity and a is an element of your binary operation, then you should get $ae=ea=a$. – Vafa Khalighi Mar 15 '11 at 1:56
• Vafa, I have read the comment you wrote to me. I can't answer there, so I'll answer here. FIRST, hand in your assignment; THEN, post questions from it online. Better: wait until all your classmates have handed in their assignments before you post assignment questions to a public website. I'm sure if you think about it, you'll see that this is the only sensible way to go about it. If your curiosity must be satisfied and you can't wait until everyone else has handed the assignment in, then come ask me f – Gerry Myerson Mar 15 '11 at 3:51

Here are a couple easy examples, I'll leave it to you to verify their properties.

The natural numbers where $n\ast m=n^m$.

The integers where $n\ast m=n-m$.

The real numbers without zero where $x \ast y = \frac{x}{y}$.

• $n*m=n^m$ has no identity element. call your identity, $I$, then $n^I=n$ gives $I=1$ but $I^n=n$ gives $I=n^\frac{1}{n}$, if $n=2$, then this $I$ is no longer a natural number (in fact, for ecah $n$, you get a different $I$) and since Identity element should be unique, your identity element does not exist. – Vafa Khalighi Mar 15 '11 at 2:12
• With $n*m=n-m$, from $n-I=n$, you get $I=0$ but with $I-n=n$, you get $I=2n$ and so the identity does not exist. – Vafa Khalighi Mar 15 '11 at 2:16
• Similarly with $x*y=\frac{x}{y}$, if $\frac{I}{x}=x$, you get $I=x^2$ but if $\frac{x}{I}=x$, then you get $I=1$. Hence identity does not exist. – Vafa Khalighi Mar 15 '11 at 2:18
• That's a good point, I was just thinking in terms of left and right identities. – JSchlather Mar 15 '11 at 19:27
• No, that was a great help. Thank you. – Vafa Khalighi Mar 16 '11 at 12:52

Pick any non-associative, non-commutative operation $\star$ on a set $X$. Now pick a new element $1$ which is not in $X$, let $Y=X\cup\{1\}$, and define a new operation $\bullet$ on $Y$ extending $\star$ and such that $$1\bullet x=x\bullet1=x$$ for all $x\in X$, and $1\bullet1=1$.

• Is this one example, or many? I'm not sure... – Ross Millikan Mar 14 '11 at 13:55
• How can you possibly be not sure? It is obviously a family of examples, parametrized by the pair $(X,\star)$. – Mariano Suárez-Álvarez Mar 14 '11 at 16:43
• I was teasing. I agree it is a family of examples, but that is one family. – Ross Millikan Mar 14 '11 at 17:19
• I already knew this. but thanks anyway – Vafa Khalighi Mar 15 '11 at 7:25
• Follow-up question: prove the family of examples given here is non-empty. – Marc van Leeuwen Jan 18 '14 at 11:36

The previous examples are all perfectly good, of course, but I thought I would add a rather low-brow way to see that such examples must be easy to generate.

Let $S$ be a finite set, and let's label its elements $x_1,\ldots,x_n$. To define a binary operation $\star: S \times S \rightarrow S$ is equivalent to filling in all the entries of an $n \times n$ matrix $M = \{m_{ij} \}$ with elements of $S$. In particular, since we have $n^2$ entries to fill out and $n$ possible choices for each entry, the total number of such matrices -- i.e., the total number of binary operations on $S$ -- is $n^{n^2}$. This is a pretty big number even when $n$ is rather small.

Suppose we wish to enforce that the first element $x_1$ is a two-sided identity for our operation $\star$. Then what we need is that for all $i,j \in \{1,\ldots,n\}$, $m_{1j} = x_j$ and $m_{i1} = x_i$. In other words, the first row and first column of the matrix are entirely determined, but this leaves us with $n^2 - 2n + 1 = (n-1)^2$ entries left to choose.

It is clear that the operation is commutative iff the matrix is symmetric, i.e., $m_{ij} = m_{ji}$ for all $i,j$. It is easy to give a precise count of the number of symmetric matrices with first row and first column as determined above and even easier to see that, as long as $n \geq 3$, most such matrices are not of this form.

Finally we come to associativity. This is harder to see directly from the matrix, but it is easy to see that we have an awful lot of choices that will result in non-associative operations. For instance, let us say for the sake of argument that $x_2 \star x_3 = x_4$ and $x_3 \star x_4 = x_5$ (all elements distinct): up to relabelling the elements, this is in some sense the generic situation. Then we find

$(x_2 \star x_3) \star x_4) = x_4 \star x_4$

whereas

$x_2 \star (x_3 \star x_4) = x_2 \star x_5$.

Now for a randomly defined binary operation, the chance that these two products are equal is only $\frac{1}{n}$. In any case, we can certainly define them to have different values even among $x_1,\ldots,x_5$ and get a nonassociative binary operation.

If you like counting things, it is a fun exercise to see what you can prove about how many of the $n^{(n-1)^2}$ binary operations on $S$ having $x_1$ as an identity are commutative, or associative, or both, or neither. If $X_n$ is the number of such operations (having $x_1$ as an identity) which are neither commutative nor associative, it should be easy to show that $\lim_{n \rightarrow \infty} \frac{X_n}{n^{(n-1)^2}} = 1$, i.e., that "with probability $1$" a randomly chosen such operation is neither commutative nor associative. I have no doubt that such results appear in the literature, with explicit bounds. If someone knows a nice argument leading to an asymptotic or exact formula for $X_n$, I would be interested to see it.

• This is an interesting question that I like to spend some time to think about it; but after finishing my assignments. Thanks for your inputs – Vafa Khalighi Mar 15 '11 at 8:06
• Nice answer. It is somewhat more difficult to enumerate matrices that encode non-associative operations. But you don't need that to find the limit. Note that X_n of non-commutative and non-associative matrices contains Y_n, the non-commutative matrices. And for every commutative matrix, we have half a matrix of free variables, or n^(n-2 choose 2) non-commutative matrices. So indeed as n grows large we find that the likelihood of getting a non-commutative matrix grows like 1 - 1/(n-2 choose 2) ~ 1 - n^(-2) – RussellStewart May 3 '14 at 23:27

the octonions! more generally (multiplication in) further algebras coming from the cayley-dickson construction.

Here's an example of an abelian group without associativity, inspired by an answer to this question. Consider the game of rock-paper-scissors: $R$ is rock, $P$ is paper, $S$ is scissors, and $1$ is fold/draw/indeterminate. Let $\ast$ be the binary operation "play".

\begin{array}{r|cccc} \ast & 1 & R & P & S\\ \hline 1& 1 & R & P & S \\ R & R& 1 & P & R\\ P & P& P & 1 & S\\ S & S& R & S & 1 . \end{array}

The mutliplication table above defines a set of elements, with a binary operation, that is commutative and non-associative. Also, each element has an inverse (itself), and the identity exists.

Since the assignment is over, I can send my solution. This is an example: $$x*y=\begin{cases} x&\text{if }y=0;\\ |x|+y&\text{if }y\not=0. \end{cases}$$

• what's the point of adding y if it is zero! Are you sure this was what you meant? – ogerard May 25 '11 at 12:32

An example of non-associative and non-commutative groupoid with identity is any non-commutative loop and, in particular, this one, finite, of order $$12$$.