114
$\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$
5
  • 30
    $\begingroup$ Commutative operations that are associative are the exception. But an important exception! Let $x\ast y=|x-y|$. $\endgroup$ Commented Jun 20, 2012 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$ Commented Jun 20, 2012 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
    Commented Jun 20, 2012 at 22:14
  • 4
    $\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$ Commented Jun 22, 2012 at 21:31
  • $\begingroup$ Good old mod arithmetic: Take $n\ge 2$. Then defining $x\ast y := (x\operatorname{mod} n^2)(y\operatorname{mod} n^2)$, we have that $0 = (n\ast n)\ast 1\ne n\ast(n\ast 1) = n^2$. $\endgroup$
    – Atom
    Commented Apr 21, 2022 at 23:03

13 Answers 13

126
$\begingroup$

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

$\endgroup$
4
  • 13
    $\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
    Commented Jan 12, 2015 at 13:13
  • 26
    $\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
    Commented Jan 14, 2015 at 4:14
  • 9
    $\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
    Commented Jan 14, 2016 at 18:28
  • 25
    $\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$ Commented Mar 4, 2018 at 18:11
66
$\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$
1
  • 10
    $\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$ Commented Sep 14, 2012 at 16:38
65
$\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$
3
  • 7
    $\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$ Commented Jun 14, 2016 at 16:46
  • 1
    $\begingroup$ Yea. Sure, is easy to work with mathematical real numbers. But floating point representations can cause problems - see, for example, The Patriot Missile Failure. $\endgroup$ Commented Sep 19, 2019 at 13:34
  • $\begingroup$ (a + -a) + b is also not always equal to b. Consider a = inf, then the result is NaN. Also depending on your definition of 'equality', if a = 0 and b is -0 then the result is 0 - with a different sign than b. $\endgroup$
    – orlp
    Commented Feb 8 at 20:10
60
$\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$
1
  • $\begingroup$ which is why you don't play rock paper scissors with three people at once $\endgroup$
    – No Name
    Commented May 27 at 14:01
27
$\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$
17
$\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$
15
$\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$
1
  • $\begingroup$ Perhaps nonobviously $\texttt{XOR}$ (exclusive disjunction) is associative---this is arguably easier to see if you identify it with $+$ on $\Bbb Z / (2 \Bbb Z)$. $\endgroup$ Commented Feb 21 at 18:26
9
$\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$
3
  • 1
    $\begingroup$ Please excuse ... but I went to the trouble of constructing the truth table ... feel free to remove it. $\endgroup$ Commented Sep 26, 2017 at 20:17
  • $\begingroup$ @DonaldSplutterwit I would use three variables instead were I you. $\endgroup$
    – Kenny Lau
    Commented Sep 26, 2017 at 20:18
  • 1
    $\begingroup$ I already mentioned the examples NAND and NOR in my answer in 2015, so what was your point? $\endgroup$
    – bof
    Commented Aug 19, 2019 at 2:14
8
$\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$
5
$\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$
3
$\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$
9
  • $\begingroup$ Sorry, but your answer uses a "mace4" software that is "not very well known" (euphemism)... $\endgroup$
    – Jean Marie
    Commented Sep 26, 2017 at 20:03
  • $\begingroup$ @JeanMarie so what? $\endgroup$
    – Kenny Lau
    Commented Sep 26, 2017 at 20:04
  • $\begingroup$ So, I give you a [+1] to your answer, which is good... but... $\endgroup$
    – Jean Marie
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 at 20:08
  • 1
    $\begingroup$ @JeanMarie I've added a postscriptum. $\endgroup$
    – Kenny Lau
    Commented Sep 26, 2017 at 20:10
2
$\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$
1
$\begingroup$

For our example the carrier set will be the set ${\Bbb Z}^{\Bbb Z}$ of all functions from $\Bbb Z$ to $\Bbb Z$.

For any two function $f, g \in {\Bbb Z}^{\Bbb Z}$ we can form the pointwise sum, $f + g: n \mapsto f(n) + g(n)$.

We have the (left) bilateral shift operator $T$ on ${\Bbb Z}^{\Bbb Z}$,

$\tag 1 T: (a_k)_{k=-\infty}^\infty \mapsto (a_{k+1})_{k=-\infty}^\infty$

We define a binary operation $\oplus$ on the set ${\Bbb Z}^{\Bbb Z}$ as follows,

$\tag 2 (f,g) \mapsto f \oplus g = T \circ (f+g)$

This binary operation is commutative but not associative; it satisfies

$\tag 3 f \oplus g = h \oplus k \; \text{ iff } \; f + g = h + k$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .