A binary operation * on a set
S that does not satisfy the associative law is called
non-associative. Symbolically, (x*y)*z\ne x*(y*z)\qquad\mbox{for some }x,y,z\in S. For such an operation the order of evaluation
does matter. For example: ;
Subtraction : (5-3)-2 \, \ne \, 5-(3-2) ;
Division : (4/2)/2 \, \ne \, 4/(2/2) ;
Exponentiation : 2^{(1^2)} \, \ne \, (2^1)^2 ;
Vector cross product :\begin{align} \mathbf{i} \times (\mathbf{i} \times \mathbf{j}) &= \mathbf{i} \times \mathbf{k} = -\mathbf{j} \\ (\mathbf{i} \times \mathbf{i}) \times \mathbf{j} &= \mathbf{0} \times \mathbf{j} = \mathbf{0} \end{align} Also although addition is associative for finite sums, it is not associative inside infinite sums (
series). For example, (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots = 0 whereas 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots = 1. Some non-associative operations are fundamental in mathematics. They appear often as the multiplication in structures called
non-associative algebras, which have also an addition and a
scalar multiplication. Examples are the
octonions and
Lie algebras. In Lie algebras, the multiplication satisfies
Jacobi identity instead of the associative law; this allows abstracting the algebraic nature of
infinitesimal transformations. Other examples are
quasigroup,
quasifield,
non-associative ring, and
commutative non-associative magmas.
Nonassociativity of floating-point calculation In mathematics, addition and multiplication of real numbers are associative. By contrast, in computer science, addition and multiplication of
floating point numbers are
not associative, as different rounding errors may be introduced when dissimilar-sized values are joined in a different order. To illustrate this, consider a floating-point representation with a 4-bit
significand: Even though most computers compute with 24 or 53 bits of significand, this is still an important source of rounding error, and approaches such as the
Kahan summation algorithm are ways to minimize the errors. It can be especially problematic in parallel computing.
Notation for non-associative operations In general, parentheses must be used to indicate the
order of evaluation if a non-associative operation appears more than once in an expression (unless the notation specifies the order in another way, like \dfrac{2}{3/4}). However,
mathematicians agree on a particular order of evaluation for several common non-associative operations. This is simply a notational convention to avoid parentheses. A
left-associative operation is a non-associative operation that is conventionally evaluated from left to right, i.e., \left. \begin{array}{l} a*b*c=(a*b)*c \\ a*b*c*d=((a*b)*c)*d \\ a*b*c*d*e=(((a*b)*c)*d)*e\quad \\ \mbox{etc.} \end{array} \right\} \mbox{for all }a,b,c,d,e\in S while a
right-associative operation is conventionally evaluated from right to left: \left. \begin{array}{l} x*y*z=x*(y*z) \\ w*x*y*z=w*(x*(y*z))\quad \\ v*w*x*y*z=v*(w*(x*(y*z)))\quad\\ \mbox{etc.} \end{array} \right\} \mbox{for all }z,y,x,w,v\in S Both left-associative and right-associative operations occur. Left-associative operations include the following: ; Subtraction and division of real numbers :x-y-z=(x-y)-z :x/y/z=(x/y)/z ; Function application :(f \, x \, y) = ((f \, x) \, y) This notation can be motivated by the
currying isomorphism, which enables partial application. Right-associative operations include the following: ;
Exponentiation of real numbers in superscript notation :x^{y^z}=x^{(y^z)}Exponentiation is commonly used with brackets or right-associatively because a repeated left-associative exponentiation operation is of little use. Repeated powers would mostly be rewritten with multiplication: :(x^y)^z=x^{(yz)}Formatted correctly, the superscript inherently behaves as a set of parentheses; e.g. in the expression 2^{x+3} the addition is performed
before the exponentiation despite there being no explicit parentheses 2^{(x+3)} wrapped around it. Thus given an expression such as x^{y^z}, the full exponent y^z of the base x is evaluated first. However, in some contexts, especially in handwriting, the difference between {x^y}^z=(x^y)^z, x^{yz}=x^{(yz)} and x^{y^z}=x^{(y^z)} can be hard to see. In such a case, right-associativity is usually implied. ;
Function definition :\mathbb{Z} \rarr \mathbb{Z} \rarr \mathbb{Z} = \mathbb{Z} \rarr (\mathbb{Z} \rarr \mathbb{Z}) :x \mapsto y \mapsto x - y = x \mapsto (y \mapsto x - y)Using right-associative notation for these operations can be motivated by the
Curry–Howard correspondence and by the
currying isomorphism. Non-associative operations for which no conventional evaluation order is defined include the following. ; Exponentiation of real numbers in infix notation :(x^\wedge y)^\wedge z\ne x^\wedge(y^\wedge z) ;
Knuth's up-arrow operators : a \uparrow \uparrow (b \uparrow \uparrow c) \ne (a \uparrow \uparrow b) \uparrow \uparrow c : a \uparrow \uparrow \uparrow (b \uparrow \uparrow \uparrow c) \ne (a \uparrow \uparrow \uparrow b) \uparrow \uparrow \uparrow c ; Taking the
cross product of three vectors :\vec a \times (\vec b \times \vec c) \neq (\vec a \times \vec b ) \times \vec c \qquad \mbox{ for some } \vec a,\vec b,\vec c \in \mathbb{R}^3 ; Taking the pairwise
average of real numbers :{(x+y)/2+z\over2}\ne{x+(y+z)/2\over2} \qquad \mbox{for all }x,y,z\in\mathbb{R} \mbox{ with }x\ne z. ; Taking the
relative complement of sets :(A\backslash B)\backslash C \neq A\backslash (B\backslash C).(Compare
material nonimplication in logic.) == History ==