Non-associative operations

Question

There are lots of operations that are not commutative.

I'm looking for striking counter-examples of operations that are not associative.

Or may associativity be genuinely built-in the concept of an operation? May non-associative operations be of genuinely lesser importance?

Which role do algebraic structures with non-associative operations play?

There's a big gap between commutative and non-commuative algebraic structures (e.g. Abelian vs. non-Abelian groups or categories). Both kinds of algebraic structures are of equal importance. Does the same hold for assosiative vs. non-associative algebraic structures?

Answer 1

Subtraction:

$$ (1-2)-3 = -4 $$ $$ 1-(2-3) = 2 $$

Answer 2

A simple example, and one that even elementary school students should be able to understand, is averaging.

average(average(a,b),c)

and

average(a,average(b,c))

are, generally, not equal to each other.

Answer 3

Division

$$(1\div2)\div4 = 1/8$$ $$1\div(2\div4) = 2$$

It is my perception that this is one of the main causes of fractions being difficult to grasp for a lot of people.

Answer 4

The Cross Product

For example let $\bf i$, $\bf j$ and $\bf k$ be the unit vectors. The cross product is the unique bilinear product that satisfies the formulae:

$\bf i \times j = \bf k \ \ \ \ \ \ \ \ \ \bf j \times k = \bf i \ \ \ \ \ \ \ \ \ \bf k \times i = \bf j$

$\bf j \times i = \bf -k \ \ \ \ \ \ \bf k \times j = \bf -i \ \ \ \ \ \ \bf i \times k = \bf -j$

$\bf i \times i = \bf 0 \ \ \ \ \ \ \ \ \ \bf j \times j = \bf 0 \ \ \ \ \ \ \ \ \ \bf k \times k = \bf 0$

Now consider the expressions $(\bf i \times i) \times j$ and $\bf i \times (i \times j)$. The first evaluates to $\bf 0 \times j = \bf 0$ while the second evaluates to $\bf i \times k = -j$.

Answer 5

Exponentiation: \begin{align*} \left(2^2\right)^3&=2^6=64\\ 2^\left(2^3\right)&=2^8=256 \end{align*}

Answer 6

In general, we do have:

$$ (A \setminus B) \setminus C \neq A \setminus (B \setminus C)$$ that is, set difference is non-associative, and it is quite an important elementary operation.

Answer 7

How about the Rock-Paper-Scissors binary relation? It is a (commutative!) binary relation on $r, p, $ and $s$ given by the "winning" relations $rp=p$ (paper covers rock), $rs=r$ (rock smashes scissors), and $sp=s$ (scissors cut paper). For ties, we have $r^2=r, p^2=p$ and $s^2=s$.

In it, we have the expressions $r(ps)$ and $(rp)s$, which simplify as follows: $$r(ps)=rs=r$$ and $$(rp)s=ps=s$$

Here, non-associativity and the lack of an always winning position are closely related.

Answer 8

Which role do algebraic structures with non-associative operations play?

Probably the most important such structure is a Lie Algebra. Lie algebras are fundamental to the study of Lie groups, and appear in many other areas of mathematics.

The “product” operation of Lie algebras is called the Lie bracket $[x,y]$, and it is non-associative except for rare, degenerate circumstances. It does satisfy the Jacobi identity

$[x,[y,z]]+[y,[z,x]]+[z,[x,y]]=0$

Non-associative products with this property arise very naturally, often as commutators $[x,y]=xy-yx$ of some other associative, non-commutative operation.

Answer 9

The Cartesian product is actually not associative, since if $A, B, C$ are sets, then

$$(A \times B) \times C = \{ ((a, b), c) : a \in A, b \in B, c \in C \} \\ A \times (B \times C) = \{ (a, (b, c)) : a \in A, b \in B, c \in C \}$$

so $(A \times B) \times C \neq A \times (B \times C)$.

Answer 10

This one may be a stretch, but hey: what about the English language!

Consider the constituent "The guardian of the king's throne".

That could mean "the throne of the guardian of the king" if we associate the words of the original -repeated genitive?- constituent as "(The guardian of the king)'s throne". (I've put the words involving "genitive operation" in bold)

But it could also mean "the guardian of the throne of the king" if we associate the words of the original constituent as "The guardian of (the king's throne)".

This illustrates that in English the genitive operation may not always be nicely associative. I'm sure there are many other good (funnier) examples and better accounts/overviews of (non)associativity in language may be out there!

Answer 11

Take any abelian group $G$ and define $x * y := x - y$. Now,

$$ (x*y)*z = (x-y) - z = x - y - z $$

and

$$ x * (y * z) = x - (y - z) = x - y + z $$

So $*$ will be associative if and only if $2z = 0$ for all $z \in G$. Thus, any abelian group with no $2$-torsion will give rise to such an example.

Answer 12

Similar to the case of set differences and exponentiation, implication is not associative:

$$A\Rightarrow (B \Rightarrow C) \not\equiv (A\Rightarrow B) \Rightarrow C$$

In fact

$$A\Rightarrow (B\Rightarrow C) \equiv A\wedge B \Rightarrow C$$

The "usual" way of looking at implication is not in vitro, but in relation to $\wedge$ (although alternatively there is something called an "implication algebra"). So it is a non-associative operation intimately related to an associative operation (this can be made precise).

Answer 13

Here's the simple example:

In $\Bbb{R}$, define $$a*b=2a+b$$ where the $+$ in the RHS is the usual addition in $\Bbb{R}$

Then $*$ is not associative

$2*(0*1)=2*(2(0)+1)=2*1=2(2)+1=5$

whereas

$(2*0)*1=(2(2)+0)*1=4*1=2(4)+1=9$

Answer 14

Take the space $M_{n\times n}(K)$ of all $n\times n$ matrices over a field $K$ and consider the operation $[M,N]=M.N-N.M$. That operation is non-associative. That's a very natural example. But since an operation on a set $A$ is simply any map from $A\times A$ into $A$, you can easily built lots of examples. For instance, in $\mathbb R$, you define, say, $x\odot y=x+e^y$. It is not associative, of course.

Answer 15

Quite similar to the "cartesian product" example : composition of paths !

Let $X$ be a topological space, $\alpha, \beta : [0,1]\to X$ continuous maps with $\alpha(1)=\beta(0)$, then we may define $\alpha\star\beta : [0,1]\to X$ by concatenating in the obvious way.

However, $\star$ is not associative (on the nose). This is very interesting because while $\alpha\star(\beta\star\gamma)\neq (\alpha\star\beta)\star\gamma$ in general, this equation holds up to path homotopy.

It's very similar to the cartesian product example, because though $A\times (B\times C)\neq (A\times B)\times C$ in general, this equality holds up to natural isomorphism.

As mentioned in the comments below the answer about cartesian products, studying structures that "should" be associative, but aren't associative "on the nose" is a big part of algebraic topology

Answer 16

Take a Steiner Triple System STS(n). It is a set $S$ of n elements with a set of subsets (called blocks) of $3$ elements from $S$ such that every pair of elements in $S$ is in exactly one of the blocks.

For example, the unique (up to isomorphism) STS(7) is $\{a,b,c\} \{a,d,e\} \{a,f,g\} \{b,d,f\} \{b,e,g\} \{c,d,g\} \{c,e,f\}$

Now, given an STS define an operation $*$ on S: $x*x:=x$ for all $x$ in $S$, and $x*y:=z$ where $\{x,y,z\}$ is a block. This operation is not associative.

https://en.wikipedia.org/wiki/Steiner_system

Answer 17

The multiplication of octonions is not associative, and they have many applications in mathematics and physics.

Answer 18

Given an associative (but possibly non-commutative) algebra (over a field with characteristic other than $2$, e.g. $\mathbb R$) we can make it into a so called Jordan algebra by equipping it with the symmetrized product

$$x\circ y := \frac 1 2(xy + yx).$$

Being a Jordan algebra means that $\circ$ is commutative and satisfies the Jordan identity

$$(x\circ y)\circ(x\circ x) = x\circ (y\circ (x\circ x))$$

They have applications to quantum mechanics as (c.f. Jordan operator algebras) but are also studied for their one sake.

Answer 19

Tensor product of (bi)modules over a quasi-bialgebra.

Let $\Bbbk$ be a field and let $(A,m,u,\Delta,\varepsilon,\Phi)$ be a quasi-bialgebra over $\Bbbk$. The category ${_A\mathfrak{M}}$ of left $A$-modules is a monoidal category with tensor product $\otimes:=\otimes_{\Bbbk}$ and unit $\Bbbk$ (the action on $M\otimes N$ is the diagonal one given by $\Delta$). In ${_A\mathfrak{M}}$, $(M\otimes N)\otimes P$ and $M\otimes (N\otimes P)$ are different $A$-modules (this is due to the non-coassociativity of $\Delta$) and you just have an isomorphism $$\alpha_{M,N,P}:(M\otimes N)\otimes P \to M\otimes (N\otimes P),(m\otimes n)\otimes p\mapsto \Phi\cdot(m\otimes (n\otimes p))$$ (the associativity constraint, in fact).

Answer 20

Malcev algebras

Malcev algebras are also an example. A Malcev algebra $A$ over a filed $\Bbbk$ is a vector space with an internal composition law $\cdot$ such that $$x^2=0,\\ x\cdot y=-y\cdot x,\\ J(x,y,z)\cdot x = J(x,y,x\cdot z),$$ where $J(x,y,z)=(x\cdot y)\cdot z+(y\cdot z)\cdot x+(z\cdot x)\cdot y$ (see Sagle, Malcev Algebras, §2).

Answer 21

Neither the Sheffer Stroke (NAND), nor the Pierce arrow (NOR) associate. Both have an important status in logic, as does implication. Reverse implication also does not associate.

I asked somewhat of a related question a few years ago: Is the Ratio of Associative Binary Operations to All Binary Operations on a Set of $n$ Elements Generally Small? Associative binary operations on a finite set are rare in comparison to the class of most binary operations on a finite set (statistically speaking). Additionally, there exist all of the counterxamples in these answers. So, we can't build in the concept of associativity to a general concept of an operation. Doing so would lead to many contradictions.

Given that a goal of the study of abstract algebra lies in studying all concrete algebras by abstract means, the study of non-associative algebras is more important than associative algebras, since non-associative algebras are vastly more common than associative algebras.

Answer 22

Subtraction / Division have been mentoined of course, but let me explain why they are as important or even more important than Addition / Multiplication and arguably only less talked about since we are more comfortable working with associativity.

You can explain what a group is (almost) solely by its division (subtraction in the Abelian case).

A (division) group is thus a set $G$ with a binary operation $/ : G\times G\to G$ s.t.

• $a/a = b/b$,
• $\frac{a/a}{(a/a)/a} = a$,
• $\frac{a}{b/c} = \frac{a}{(c/c)/c)}/b$.

(I used "big fractions" for increased readibility).

A group morphism $f : G\to H$ is then just a function $G\to H$ s.t. $f(a/b) = f(a)/f(b)$.

There is a small "caveat". The "division groups" almost coincide with ordinary groups; just pick $g\in G$ and let $e_G := g/g$, $a\cdot b := a/(e_G/b)$ and $a^{-1} = e_G/a$. This leaves open the possibility of $G$ being empty. So in this theory, there is an "empty group".

If you don't want an "empty group", then we can simply insist on the existence of an identity $e_G$ s.t. $a/a = e_G$ for all $a\in G$.

Answer 23

Sorry I'm late to the party, but reading through these posts I noticed that many demonstrations of a non-associative operation here have the exact same algebraic structure.

Operation

Let $\langle R, \cdot,+\rangle$ be a ring with identity without zero divisors, $\langle H, +\rangle$ be a nontrivial abelian group, and $\phi:R\times H\to H$, denoted $\phi(r,h)=rh$ be a function always obeying

• $1_Rh=h,$
• $(r_1r_2)h=r_1(r_2h),$
• $r(h_1+h_2)=rh_1+rh_2,$
• $r0_H=0_H,$
• $(r_1+r_2)h=r_1h+r_2h,$

Given $r\in R$ with $r\neq1_R,0_R$ and so that there exists some $h$ with $r(1_R-r)h\neq0_H$. Define $*$ on $H\times H$ by $x*y=x+ry$. We can directly compute $$\begin{aligned} ((x*y)*z)-(x*(y*z))&=((x+ry)*z)-(x*(y+rz))\\ &=((x+ry)+rz)-(x+r(y+rz))\\ &=(x+ry+rz)-(x+ry+rrz)\\ &=rz-rrz\\ &=rz+r(-rz)\\ &=r(z-rz)\\ &=r(1_Rz-rz)\\ &=r(1_R-r)z\\ &=((r(1_R-r))z\\ \end{aligned}$$

By design this product is nonzero, so the difference between $*$ evaluations with the two different associations is nonzero. In a group, that means they are not equal, hence $*$ is non-associative.

Examples

• Subtraction in $\mathbb{R}$. Let $R$ and $H$ both be $\mathbb{R}$ with addition, multiplication, and the ring action defined the obvious ways. Choose $r=-1$.
• Subtraction in an arbitrary nontrivial abelian group without 2-torsion. Let $R=\mathbb{N}$, $H$ be that group, $r$ be $-1$, and the ring action be successive addition of an element or its inverse in the obvious way.
• As in the $2a+b$ answer, take $R$ and $H$ to both be $\mathbb{R}$ with all operations defined the obvious ways. Choose $r=2$. Over the reals, we can actually just choose $r$ to be anything other than $1$ or $0$.
• Extending that, let $R$ and $H$ both be the same ring with identity without zero divisors of cardinality at least $3$. Define addition to be the ring addition, multiplication to be the ring multiplication, and the ring action $\phi$ to be the ring's multiplication. Choose $r$ to be anything other than $0$ or $1$.
• We actually get the implication answer out of this formulation as well, viewing $R$ and $H$ both as the set $\{0,1\}$, treating $H$ them both as a boolean algebra to obtain addition and multiplication, defining the ring action to be XOR, and choosing $r=1$.

Answer 24

IEEE-754 floating point, due to the rounding inherent in operations.

a + b involves a rounding step.

It's one of the reasons fused multiply-adds exist.

0.7 + 0.1 + 0.2 from here: https://stackoverflow.com/questions/10371857/is-floating-point-addition-and-multiplication-associative