65
$\begingroup$

Does commutativity imply associativity? I'm asking this because I was trying to think of structures that are commutative but non-associative but couldn't come up with any. Are there any such examples?

NOTE: I wasn't sure how to tag this so feel free to retag it.

$\endgroup$
  • 18
    $\begingroup$ Commutative operations that are associative are the exception. But an important exception! Let $x\ast y=|x-y|$. $\endgroup$ – André Nicolas Jun 20 '12 at 20:41
  • $\begingroup$ Not even in the presence of an identity element and an opposite, see this. In fact, William's answer is already in that post ;) $\endgroup$ – Bruno Stonek Jun 20 '12 at 21:58
  • $\begingroup$ The interchange law $(x * y) \cdot (z * w) = (x \cdot z) * (y \cdot w)$, in the presence of a two-sided common unit element, implies commutativity and associativity of $*$ and $\cdot$. (In fact, they have to be the same operation!) $\endgroup$ – Zhen Lin Jun 20 '12 at 22:14
  • 3
    $\begingroup$ See my 3 February 2009 sci.math post A natural example of a commutative, non-associative operator (see Google archive version or Math Forum archive version) for some examples and references. $\endgroup$ – Dave L. Renfro Jun 22 '12 at 21:31

12 Answers 12

81
$\begingroup$

Consider the operation $(x,y) \mapsto xy+1$ on the integers.

$\endgroup$
  • 4
    $\begingroup$ @marlu Could you explain this some more please? It doesn't say why, or (for people like me who don't know much about maths), what that arrow even means. $\endgroup$ – user673679 Jan 12 '15 at 13:13
  • 12
    $\begingroup$ Well, associativity and commutativity are properties of maps $X\times X \to X$ for a set $X$. In other words, such a map takes two elements as an "input" and returns a single element. In my example, the set under consideration is the set of integers and the map sends each pair of integers $(x,y)$ to $xy+1$. Commutativity means $xy + 1 = yx + 1$ for all $x$ and $y$, which is satisfied. Associativity would mean $x(yz+1) + 1 = (xy+1)z+1$ for all $x$, $y$ and $z$, but it's easy to find examples where this equation does not hold, so the operation is not associative. $\endgroup$ – marlu Jan 14 '15 at 4:14
  • $\begingroup$ Short, sweet. Nice. $\endgroup$ – AJFarmar Mar 20 '15 at 20:55
  • 4
    $\begingroup$ But wait, this is unfair — you're considering commutativity under addition, but associativity under both addition and multiplication, they're different operations! ☹ $\endgroup$ – Hi-Angel Jan 14 '16 at 18:28
  • 8
    $\begingroup$ @Hi-Angel: Commutativity and associativity are properties of a single binary operation; in this case, the operation defined by marlu above. Denoting this operation by, say, the symbol $\odot$, it is clearly commutative since $x \odot y = xy+1 = yx+1 = y \odot x$, but not associative since $(x \odot y) \odot z = (xy+1)z+1 = xyz+z+1 \ne xyz+x+1 = x(yz+1)+1 = x \odot (y \odot z)$ whenever $x \ne z$. $\endgroup$ – Ilmari Karonen Mar 4 '18 at 18:11
47
$\begingroup$

A basic example is the "midpoint" binary operation: $a*b = \frac{a+b}{2}$

In general, if $P(u,v)$ is any polynomial in two variables with rational coefficients, then $x*y = P(x+y,xy)$ is rarely associative - I'd be curious under what conditions on $P$ this operation would be associative.

My example is $P(u,v)=\frac{u}{2}$ and Marlu's example is $P(u,v)=1+v$.

$\endgroup$
  • 6
    $\begingroup$ In general, a symmetric function $P(x,y)$ is rarely associative. You could take $P(x,y)=\arctan xy+e^{(x+y)^9}$, too. $\endgroup$ – Mariano Suárez-Álvarez Sep 14 '12 at 16:38
39
$\begingroup$

Arguably the most important example of a commutative but non-associative structure is that of finite-precision floating point numbers under addition. (a + -a) + b is always equal to b but a + (-a + b) can differ from b since the sum -a + b can involve a loss of precision (this is especially true if a and b are nearly but not quite equal, -a + b could work out to 0 even though the corresponding real sum is nonzero). The lack of associativity of floating point arithmetic is a constant complicating factor in numerical analysis.

$\endgroup$
  • 4
    $\begingroup$ This is a nice example, because it reminds us how important these concepts are in practical life, even though we often do not think about them..(+1) $\endgroup$ – Björn Friedrich Jun 14 '16 at 16:46
24
$\begingroup$

The easiest Jordan algebra is symmetric square matrices with the operation $$ A \ast B = (AB + BA)/2, $$ similar to a Lie algebra but with a plus sign.

http://en.wikipedia.org/wiki/Jordan_algebra

$\endgroup$
21
$\begingroup$

Consider the commutative operation $\texttt{vs}$ on the set $\{\textbf{rock}, \textbf{paper}, \textbf{scissors}\}$ abbreviated $\{r,p,s\}$ defined by $$ \begin{array}{c|ccc} \texttt{vs} & r&p&s\\ \hline r & r & p & r \\ p & p & p & s \\ s & r & s & s \end{array}$$ It is not associative since, for example, $$\textbf{paper} \texttt{ vs } (\textbf{scissors} \texttt{ vs } \textbf{rock}) = \textbf{paper}$$ but $$(\textbf{paper} \texttt{ vs } \textbf{scissors}) \texttt{ vs } \textbf{rock} = \textbf{rock}.$$

$\endgroup$
16
$\begingroup$

Let $A = \{e,x,y\}$. Define $\cdot$ on $A$ to be $a\cdot e=a$ for all $a$, $e\cdot a= a$ for all a, and $a\cdot b=e$ for all $a$ and $b$ such that $a\neq e$ and $b\neq e$, (i.e. $a,b \in \{x,y\}$).

This operation is commutative, $e$ is the identity, (everything even has an inverse), but is not associative since $(x \cdot y) \cdot y = e \cdot y = y$ and $x \cdot (y \cdot y) = x \cdot e = x$.

$\endgroup$
11
$\begingroup$

The simplest examples of commutative but nonassociative operations are the NOR and NAND operations (joint denial and alternative denial) in propositional logic. Quoting from my answer to the question A conjecture in equational logic:

Namely, the $2$-element structure $\{a,b\}$, where $aa=b$ and $ab=ba=bb=a$, is commutative but not associative; in fact, for any $x\in\{a,b\}$, we have $$(ax)b=b(xa)=a,$$ $$a(xb)=(bx)a=b.$$ This is the unique (up to isomorphism) binary operation on a $2$-element set which is commutative but not associative; it can be interpreted as either of the truth-functions NOR or NAND.

$\endgroup$
5
$\begingroup$

The NAND is commutative but not associative.

\begin{eqnarray*} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & B & & A \text{ nand } A & (A \text{ nand } A) \text{ nand } B & & A \text{ nand } B & A \text{ nand } (A \text{ nand } B) \\ \hline 0&0& &1&1& &1&1 \\ \hline 0&1& &1&0& &1&1 \\ \hline 1&0& &0&1& &1&0 \\ \hline 1&1& &0&1& &0&1 \\ \hline \end{array} \end{eqnarray*}

$\endgroup$
  • $\begingroup$ Please excuse ... but I went to the trouble of constructing the truth table ... feel free to remove it. $\endgroup$ – Donald Splutterwit Sep 26 '17 at 20:17
  • $\begingroup$ @DonaldSplutterwit I would use three variables instead were I you. $\endgroup$ – Kenny Lau Sep 26 '17 at 20:18
  • $\begingroup$ I already mentioned the examples NAND and NOR in my answer in 2015, so what was your point? $\endgroup$ – bof Aug 19 at 2:14
5
$\begingroup$

The arithmetical, geometrical and harmonic mean operations on $\mathbb{R}$, $\mathbb{R^+}$ and $\mathbb{R_*^+}$ resp.:

$$a*b=\dfrac{a+b}{2}$$

$$a*b=\sqrt{ab}$$

$$a*b=\dfrac{ab}{a+b}$$

Remark: the non-associativity of arithmetical mean has a kind of physical interpretation by placing more weight either on the last or on the first term:

$$(a*b)*c=\dfrac{\tfrac{a+b}{2}+c}{2}=\dfrac{a+b+2c}{4}$$

whereas

$$a*(b*c)=\dfrac{2a+b+c}{4}$$

(none of them being equal to $\dfrac{a+b+c}{3}$ !...)

$\endgroup$
3
$\begingroup$

For $x,y \in \mathbb{Z}$, define $x*y = xy + 1$.

Then * is clearly commutative.

As for associativity, $$a*(b*c) = a*(bc + 1) = a(bc + 1) + 1 = abc + a + 1$$ $$(a*b)*c = (ab + 1)*c = (ab + 1)c + 1 = abc + c + 1$$ so associativity fails for any triple $(a,b,c)$ with $a \ne c$.

Here's another example . . .

For $x,y \in \mathbb{Z}$, define $x y = x^2y^2$.

Once again, commutativity is obvious.

For associativity, $$a*(b*c) = a*(b^2c^2) = a^2(b^2c^2)^2 = a^2b^4c^4$$ $$(a*b)*c = (a^2b^2)*c = (a^2b^2)^2c^2 = a^4b^4c^2$$ so associativity fails if $a,b,c \ne 0$, and $|a| \ne |c|$.

One last example . . .

For $x,y \in \mathbb{Z}$, define $x*y = -x-y$.

Commutativity is clear.

For associativity, $$a*(b*c) = a*(-b-c) = -a-(-b-c) = -a + b + c$$ $$(a*b)*c = (-a-b)*c = -(-a-b)-c = a + b -c $$ so associativity fails if $a \ne c$.

$\endgroup$
1
$\begingroup$

Using mace4 on the assumption x*y=y*x. and goal (x*y)*z=x*(y*z). gives:

% Interpretation of size 2

*(0,0) = 1.
*(0,1) = 0.
*(1,0) = 0.
*(1,1) = 0.

c1 = 0.

c2 = 0.

c3 = 1.

i.e. 0*0=0, 0*1=0, 1*0=0, 1*1=0, with (x,y,z)=(0,0,1) being the counter-example.

(0*0)*1 = 1*1 = 0
0*(0*1) = 0*0 = 1

P.S. Mace4 is a software used for constructing finite models and finding counter-examples.

$\endgroup$
  • $\begingroup$ Sorry, but your answer uses a "mace4" software that is "not very well known" (euphemism)... $\endgroup$ – Jean Marie Sep 26 '17 at 20:03
  • $\begingroup$ @JeanMarie so what? $\endgroup$ – Kenny Lau Sep 26 '17 at 20:04
  • $\begingroup$ So, I give you a [+1] to your answer, which is good... but... $\endgroup$ – Jean Marie Sep 26 '17 at 20:05
  • 1
    $\begingroup$ (Thanks for using French :)) You should say more about "mace4" system you use : we have no idea on the category of software it belongs to for example ... $\endgroup$ – Jean Marie Sep 26 '17 at 20:08
  • 1
    $\begingroup$ @JeanMarie I've added a postscriptum. $\endgroup$ – Kenny Lau Sep 26 '17 at 20:10
0
$\begingroup$

Given ideals $I$ and $J$ in a Lie algebra $\mathfrak{g}$ over a commutative ring $K$, the ideal product $[I,J]$ defined as the image of the composite $$I \otimes_K J \hookrightarrow \mathfrak{g} \otimes_K \mathfrak{g} \xrightarrow{[-, -]} \mathfrak{g}$$ is commutative, but not associative in general. It is easy to see why, because the ideal product is given by $$[I,J] \equiv \{ \Sigma_{i=0}^n [x_i, y_i] \mid \text{$x_i \in I$, $y_i \in J$, $n \in \mathbb{N}$} \},$$ and $[x,y]=-[y,x]$, but the bracket is not associative in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.