Associativity

related topics
{math, number, function}
{style, bgcolor, rowspan}

In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value. Consider, for instance, the following equations:

Even though the parentheses were rearranged (the left side requires adding 5 and 2 first, then adding 1 to the result, whereas the right side requires adding 2 and 1 first, then 5), the value of the expression was not altered. Since this holds true when performing addition on any real numbers, 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,

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 exactly the same order from left to right in the expression. In contrast,

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

Associative operations are abundant in mathematics; in fact, many algebraic structures (such as semigroups and categories) 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.

Contents

Definition

Formally, a binary operation *\!\!\! on a set S is called associative if it satisfies the associative law:

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 *\!\!\! operations. Thus, when *\!\!\! is associative, the evaluation order can therefore be left unspecified without causing ambiguity, by omitting the parentheses and writing simply:

However, it is important to remember that changing the order of operations does not involve or permit moving the operands around within the expression; the sequence of operands is always unchanged.

A very different perspective is obtained by rephrasing associativity using functional notation: f(f(x,y),z) = f(x,f(y,z)): when expressed in this form, associativity becomes less obvious.

Associativity can be generalized to n-ary operations. Ternary associativity is (abc)de = a(bcd)e = ab(cde), i.e. the string abcde with any three adjacent elements bracketed. N-ary associativity is a string of length n+(n-1) with any n adjacent elements bracketed.[1]

Full article ▸

related documents
Lagrange inversion theorem
Elementary group theory
Referential transparency (computer science)
Legendre symbol
Consistency
Functional analysis
Axiom of pairing
Statistical independence
Quotient group
Examples of groups
Unicity distance
Nial
Haar measure
Tree (graph theory)
Splitting lemma
Extended real number line
Richard's paradox
Extended Backus–Naur Form
Coprime
Mathematical model
Meromorphic function
P-complete
Real analysis
B-tree
Assignment problem
Queue (data structure)
Ring (mathematics)
Epimorphism
Idempotence
Chomsky hierarchy