: ''This article is about associativity in [[mathematics]]. For ''associativity'' in central processor unit memory cache architecture see [[CPU cache]]. For ''associativity'' in programming languages see [[operator associativity]].''

In [[mathematics]], '''associativity''' is a property that a [[binary operation]] can have. It means that, within an expression containing two or more of the same associative operators in a row, the order of operations does not matter as long as the sequence of the [[operand]]s is not changed. That is, rearranging the [[parentheses]] in such an expression will not change its value. Consider for instance the equation

: <math>(5+2)+1=5+(2+1)=8</math>

Even though the parentheses were rearranged, the value of the expression was not altered. Since this holds true when performing addition on any [[real number]]s, we say that "addition of real numbers is an associative operation."

Associativity is not to be confused with [[commutativity]]. Commutativity justifies changing the order or sequence of the operands within an expression while associativity does not. For example,

: <math>(5+2)+1=5+(2+1)</math>

is an example of associativity because the parentheses were changed (and consequently the order of operations during evaluation) while the operands 5, 2, and 1 appeared in the exact same order from left to right in the expression.

: <math>(5+2)+1=(2+5)+1</math>

is not an example of associativity because the operand sequence changed when the 2 and 5 switched places.

Associative operations are abundant in mathematics, and in fact most [[algebraic structure]]s explicitly require their binary operations to be associative. However, many important and interesting operations are non-associative; one common example would be the [[vector cross product]].

== Definition ==

Formally, a binary operation <math>*\!\!\!</math> on a [[set]] ''S'' is called '''associative''' if it satisfies the '''associative law''':

: <math>(x*y)*z=x*(y*z)\qquad\mbox{for all }x,y,z\in S.</math>

The evaluation order does not affect the value of such expressions, and it can be shown that the same holds for expressions containing ''any'' number of <math>*\!\!\!</math> operations. Thus, when <math>*\!\!\!</math> is associative, the evaluation order can therefore be left unspecified without causing ambiguity, by omitting the parentheses and writing simply:

: <math>x*y*z.\,</math>

However, it is important to remember that changing the order of operations does not involve or permit changing the actual operations themselves by moving the operands around within the expression.

== Examples ==

Some examples of associative operations include the following.

* In [[arithmetic]], [[addition]] and [[multiplication]] of [[real number]]s are associative; i.e.,
:: <math>

\left.
\begin{matrix}
(x+y)+z=x+(y+z)=x+y+z\quad
\\
(x\,y)z=x(y\,z)=x\,y\,z\qquad\qquad\qquad\quad\ \ \,
\end{matrix}
\right\}
\mbox{for all }x,y,z\in\mathbb{R}.
</math>

* Addition and multiplication of [[complex number]]s and [[quaternion]]s is associative. Addition of [[octonion]]s is also associative, but multiplication of octonions is non-associative.

* The [[greatest common divisor]] and [[least common multiple]] functions act associatively.
:: <math>

\left.
\begin{matrix}
\operatorname{gcd}(\operatorname{gcd}(x,y),z)=
\operatorname{gcd}(x,\operatorname{gcd}(y,z))=
\operatorname{gcd}(x,y,z)\ \quad
\\
\operatorname{lcm}(\operatorname{lcm}(x,y),z)=
\operatorname{lcm}(x,\operatorname{lcm}(y,z))=
\operatorname{lcm}(x,y,z)\quad
\end{matrix}
\right\}\mbox{ for all }x,y,z\in\mathbb{Z}.
</math>

*Because [[linear transformation]]s are functions that can be represented by matrices with [[matrix multiplication]] being the representation of functional composition, one can immediately conclude that matrix multiplication is associative.

* Taking the [[intersection (set theory)|intersection]] or the [[union (set theory)|union]] of [[set]]s:
:: <math>

\left.
\begin{matrix}
(A\cap B)\cap C=A\cap(B\cap C)=A\cap B\cap C\quad
\\
(A\cup B)\cup C=A\cup(B\cup C)=A\cup B\cup C\quad
\end{matrix}
\right\}\mbox{for all sets }A,B,C.
</math>

* If ''M'' is some set and ''S'' denotes the set of all functions from ''M'' to ''M'', then the operation of [[functional composition]] on ''S'' is associative:

:: <math>(f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h\qquad\mbox{for all }f,g,h\in S.</math>

* Slightly more generally, given four sets ''M'', ''N'', ''P'' and ''Q'', with ''h'': ''M'' to ''N'', ''g'': ''N'' to ''P'', and ''f'': ''P'' to ''Q'', then

:: <math>(f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h</math>

: as before. In short, composition of maps is always associative.

* Consider a set with three elements, A, B, and C. The following operation:

{| class="wikitable" style="text-align:center"
| +
|-
! × !! A !! B !! C
|-
! A
| A || A || A
|-
! B
| A || B || C
|-
! C
| A || A || A
|-
|}

is associative. Thus, for example, A(BC)=(AB)C. This mapping is not commutative.

== Non-associativity ==

A binary operation <math>*</math> on a set ''S'' that does not satisfy the associative law is called '''non-associative'''. Symbolically,

: <math>(x*y)*z\ne x*(y*z)\qquad\mbox{for some }x,y,z\in S.</math>

For such an operation the order of evaluation ''does'' matter. [[Subtraction]], [[division (mathematics)|division]] and [[exponentiation]] are well-known examples of non-associative operations:

: <math>

\begin{matrix}
(5-3)-2\ne 5-(3-2)\quad
\\
(4/2)/2\ne 4/(2/2)\qquad\qquad
\\
2^{(1^2)}\ne (2^1)^2.\quad\qquad\qquad
\end{matrix}
</math>
In general, parentheses must be used to indicate the [[order of operations|order of evaluation]] if a non-associative operation appears more than once in an expression. However, [[mathematician]]s agree on a particular order of evaluation for several common non-associative operations. This is simply a syntactical convention to avoid parentheses.

A '''left-associative''' operation is a non-associative operation that is conventionally evaluated from left to right, i.e.,

: <math>

\left.
\begin{matrix}
x*y*z=(x*y)*z\qquad\qquad\quad\,
\\
w*x*y*z=((w*x)*y)*z\quad
\\
\mbox{etc.}\qquad\qquad\qquad\qquad\qquad\qquad\ \ \,
\end{matrix}
\right\}
\mbox{for all }w,x,y,z\in S
</math>
while a '''right-associative''' operation is conventionally evaluated from right to left:

: <math>

\left.
\begin{matrix}
x*y*z=x*(y*z)\qquad\qquad\quad\,
\\
w*x*y*z=w*(x*(y*z))\quad
\\
\mbox{etc.}\qquad\qquad\qquad\qquad\qquad\qquad\ \ \,
\end{matrix}
\right\}
\mbox{for all }w,x,y,z\in S
</math>
Both left-associative and right-associative operations occur; examples are given below.

== More examples ==

Left-associative operations include the following.

* Subtraction and division of real numbers:
:: <math>x-y-z=(x-y)-z\qquad\mbox{for all }x,y,z\in\mathbb{R};</math>
:: <math>x/y/z=(x/y)/z\qquad\qquad\quad\mbox{for all }x,y,z\in\mathbb{R}\mbox{ with }y\ne0,z\ne0.</math>

Right-associative operations include the following.

* [[Exponentiation]] of real numbers:
:: <math>x^{y^z}=x^{(y^z)}.\,</math>

: The reason exponentiation is right-associative is that a repeated left-associative exponentiation operation would be less useful. Multiple appearances could (and would) be rewritten with multiplication:

:: <math>(x^y)^z=x^{(yz)}.\,</math>

Non-associative operations for which no conventional evaluation order is defined include the following.

* Taking the pairwise [[average]] of real numbers:
:: <math>{(x+y)/2+z\over2}\ne{x+(y+z)/2\over2}\ne{x+y+z\over3}\qquad\mbox{for some }x,y,z\in\mathbb{R}.</math>
* Taking the [[complement (set theory)|relative complement]] of sets:
:: <math>(A\backslash B)\backslash C\ne A\backslash (B\backslash C)\qquad\mbox{for some sets }A,B,C.</math>

:: <div style="width: 360px; float: left; margin: 0 2em 0 0; text-align: left;">[[Image:RelativeComplement.png|Venn diagram of the relative complements (A\B)\C and A\(B\C)]]</div>

The green part in the left [[Venn diagram]] represents (''A''\''B'')\''C''. The green part in the right Venn diagram represents ''A''\(''B''\''C'').
<br style="clear: both;" />

* Using right-associative notation for [[material conditional]] can be motivated e.g. by [[Curry-Howard correspondence]]: see e.g. [[Hilbert-style deduction system#Further connections|comparison of the first two axioms of the Hilbert-style deduction system with basic combinators of combinatory logic]].

== See also ==
{{Wiktionary}}

* A [[semigroup]] is a set with a closed associative binary operation.
* [[Commutativity]] and [[distributivity]] are two other frequently discussed properties of binary operations.
* [[Power associativity]] and [[alternativity]] are weak forms of associativity.

[[Category:Abstract algebra]]
[[Category:Elementary algebra]]
[[Category:Binary operations|*Associativity]]
[[Category:Functional analysis]]

[[ar:عملية تجميعية]]
[[bg:Асоциативност]]
[[cs:Asociativita]]
[[da:Associativitet]]
[[de:Assoziativgesetz]]
[[el:Προσεταιριστική ιδιότητα]]
[[es:Asociatividad]]
[[eo:Asocieco]]
[[fr:Associativité]]
[[ko:결합 법칙]]
[[it:Associatività]]
[[he:אסוציאטיביות]]
[[hu:Asszociativitás]]
[[nl:Associativiteit]]
[[ja:結合法則]]
[[pl:Łączność (matematyka)]]
[[pt:Associatividade]]
[[ro:Asociativitate]]
[[ru:Ассоциативная операция]]
[[sk:Asociatívna operácia]]
[[sl:Asociativnost]]
[[sr:Асоцијативност]]
[[sh:Asocijativnost]]
[[fi:Liitännäisyys]]
[[sv:Associativitet]]
[[tr:Birleşme]]
[[zh:结合律]]