In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the associative property is a property of some
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
s, which means that rearranging the
parentheses in an expression will not change the result. In
propositional logic, associativity is a
valid rule of replacement
In logic, a rule of replacementMoore and Parker is a transformation rule that may be applied to only a particular segment of an logical expression, expression. A logical system may be constructed so that it uses either axioms, rules of inference ...
for
expressions in
logical proofs.
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
operand
In mathematics, an operand is the object of a mathematical operation, i.e., it is the object or quantity that is operated on.
Example
The following arithmetic expression shows an example of operators and operands:
:3 + 6 = 9
In the above examp ...
s is not changed. That is (after rewriting the expression with parentheses and in infix notation if necessary), rearranging the parentheses in such an expression will not change its value. Consider the following equations:
Even though the parentheses were rearranged on each line, the values of the expressions were not altered. Since this holds true when performing addition and multiplication on any
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, it can be said that "addition and multiplication of real numbers are associative operations".
Associativity is not the same as
commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
, which addresses whether the order of two operands affects the result. For example, the order does not matter in the multiplication of real numbers, that is, , so we say that the multiplication of real numbers is a commutative operation. However, operations such as
function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
and
matrix multiplication are associative, but (generally) not commutative.
Associative operations are abundant in mathematics; in fact, many
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s (such as
semigroups and
categories
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
*Categories (Aristotle), ''Categories'' (Aristotle)
*Category (Kant)
...
) explicitly require their binary operations to be associative.
However, many important and interesting operations are non-associative; some examples include
subtraction
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
,
exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
, and the
vector cross product. In contrast to the theoretical properties of real numbers, the addition of
floating point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
numbers in computer science is not associative, and the choice of how to associate an expression can have a significant effect on rounding error.
Definition
Formally, a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
on a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is called associative if it satisfies the associative law:
Here, ∗ is used to replace the symbol of the operation, which may be any symbol, and even the absence of symbol (
juxtaposition) as for
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
.
The associative law can also be expressed in functional notation thus: .
Generalized associative law
If a binary operation is associative, repeated application of the operation produces the same result regardless of how valid pairs of parentheses are inserted in the expression. This is called the generalized associative law. For instance, a product of four elements may be written, without changing the order of the factors, in five possible ways:
*
*
*
*
*
If the product operation is associative, the generalized associative law says that all these expressions will yield the same result. So unless the expression with omitted parentheses already has a different meaning (see below), the parentheses can be considered unnecessary and "the" product can be written unambiguously as
As the number of elements increases, the
number of possible ways to insert parentheses grows quickly, but they remain unnecessary for disambiguation.
An example where this does not work is the
logical biconditional . It is associative; thus, is equivalent to , but most commonly means , which is not equivalent.
Examples
Some examples of associative operations include the following.
\mboxx,y,z\in\mathbb.
, 6= Taking the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
or the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of
sets:
, 7= If is some set and denotes the set of all functions from to , then the operation of
function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
on is associative:
, 8= Slightly more generally, given four sets , , and , with , , and , then
as before. In short, composition of maps is always associative.
, 9= In
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, composition of morphisms is associative by definition. Associativity of functors and natural transformations follows from associativity of morphisms.
, 10= Consider a set with three elements, , , and . The following operation:
is associative. Thus, for example, . This operation is not commutative.
, 11= Because
matrices represent
linear functions, and
matrix multiplication represents function composition, one can immediately conclude that matrix multiplication is associative.
, 12= For
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s (and for any
totally ordered set
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
), the minimum and maximum operation is associative:
Propositional logic
Rule of replacement
In standard truth-functional propositional logic, ''association'', or ''associativity'' are two
valid rules of replacement
In logic, a rule of replacementMoore and Parker is a transformation rule that may be applied to only a particular segment of an logical expression, expression. A logical system may be constructed so that it uses either axioms, rules of inference ...
. The rules allow one to move parentheses in
logical expressions
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
in
logical proofs. The rules (using
logical connectives
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary c ...
notation) are:
and
where "
" is a
metalogical
symbol
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different conc ...
representing "can be replaced in a
proof
Proof most often refers to:
* Proof (truth), argument or sufficient evidence for the truth of a proposition
* Alcohol proof, a measure of an alcoholic drink's strength
Proof may also refer to:
Mathematics and formal logic
* Formal proof, a con ...
with".
Truth functional connectives
''Associativity'' is a property of some
logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
s of truth-functional
propositional logic. The following
logical equivalences demonstrate that associativity is a property of particular connectives. The following (and their converses, since is commutative) are truth-functional
tautologies.
;Associativity of disjunction
:
;Associativity of conjunction
:
;Associativity of equivalence
:
Joint denial is an example of a truth functional connective that is ''not'' associative.
Non-associative operation
A binary operation
on a set ''S'' that does not satisfy the associative law is called non-associative. Symbolically,
For such an operation the order of evaluation ''does'' matter. For example:
;
Subtraction
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
:
;
Division
:
;
Exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
:
;
Vector cross product
:
Also although addition is associative for finite sums, it is not associative inside infinite sums (
series). For example,
whereas
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
octonion
In mathematics, the octonions are a normed division algebra over the real numbers, a kind of hypercomplex number system. The octonions are usually represented by the capital letter O, using boldface or blackboard bold \mathbb O. Octonions have e ...
s and
Lie algebra
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an Binary operation, operation called the Lie bracket, an Alternating multilinear map, alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow ...
s. 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
A non-associative algebra (or distributive algebra) is an algebra over a field where the binary multiplication operation is not assumed to be associative. That is, an algebraic structure ''A'' is a non-associative algebra over a field ''K'' if i ...
, and
commutative non-associative magmas.
Nonassociativity of floating point calculation
In mathematics, addition and multiplication of real numbers is associative. By contrast, in computer science, the addition and multiplication of
floating point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
numbers is ''not'' associative, as rounding errors are introduced when dissimilar-sized values are joined together.
To illustrate this, consider a floating point representation with a 4-bit
mantissa:
Even though most computers compute with 24 or 53 bits of mantissa, this is an important source of rounding error, and approaches such as the
Kahan summation algorithm In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious appro ...
are ways to minimise 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
). However,
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
s 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.,
while a right-associative operation is conventionally evaluated from right to left:
Both left-associative and right-associative operations occur. Left-associative operations include the following:
; Subtraction and division of real numbers
"Using Order of Operations and Exploring Properties"
section 9. Virginia Department of Education.[Bronstein, '' :de:Taschenbuch der Mathematik'', pages 115-120, chapter: 2.4.1.1, ]
:
:
; Function application
:
This notation can be motivated by the currying
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f that ...
isomorphism, which enables partial application.
Right-associative operations include the following:
; Exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
of real numbers in superscript notation
: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:
:Formatted correctly, the superscript inherently behaves as a set of parentheses; e.g. in the expression the addition is performed
before
Before is the opposite of after, and may refer to:
* ''Before'' (Gold Panda EP), 2009
* ''Before'' (James Blake EP), 2020
* "Before" (song), a 1996 song by the Pet Shop Boys
* "Before", a song by the Empire of the Sun from ''Two Vines''
* "Befo ...
the exponentiation despite there being no explicit parentheses wrapped around it. Thus given an expression such as , the full exponent of the base is evaluated first. However, in some contexts, especially in handwriting, the difference between , and can be hard to see. In such a case, right-associativity is usually implied.
; Function definition
:
:Using right-associative notation for these operations can be motivated by the
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct relati ...
and by the currying
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f that ...
isomorphism.
Non-associative operations for which no conventional evaluation order is defined include the following.
; Exponentiation of real numbers in infix notation[Exponentiation Associativity and Standard Math Notation](_blank)
Codeplea. 23 August 2016. Retrieved 20 September 2016.
:
; Knuth's up-arrow operators
:
:
; Taking the cross product
In mathematics, the cross product or vector product (occasionally directed area product, to emphasize its geometric significance) is a binary operation on two vectors in a three-dimensional oriented Euclidean vector space (named here E), and is ...
of three vectors
:
; Taking the pairwise average
In ordinary language, an average is a single number taken as representative of a list of numbers, usually the sum of the numbers divided by how many numbers are in the list (the arithmetic mean). For example, the average of the numbers 2, 3, 4, 7, ...
of real numbers
:
; Taking the relative complement
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
of sets
:.(Compare
material nonimplication
Material nonimplication or abjunction (Latin ''ab'' = "from", ''junctio'' =–"joining") is the negation of material implication. That is to say that for any two propositions P and Q, the material nonimplication from P to Q is true if a ...
in logic.)
History
William Rowan Hamilton
Sir William Rowan Hamilton Doctor of Law, LL.D, Doctor of Civil Law, DCL, Royal Irish Academy, MRIA, Royal Astronomical Society#Fellow, FRAS (3/4 August 1805 – 2 September 1865) was an Irish mathematician, astronomer, and physicist. He was the ...
seems to have coined the term "associative property" around 1844, a time when he was contemplating the non-associative algebra of the octonions
In mathematics, the octonions are a normed division algebra over the real numbers, a kind of hypercomplex number system. The octonions are usually represented by the capital letter O, using boldface or blackboard bold \mathbb O. Octonions have e ...
he had learned about from John T. Graves
John Thomas Graves (4 December 1806 – 29 March 1870) was an Irish jurist and mathematician. He was a friend of William Rowan Hamilton, and is credited both with inspiring Hamilton to discover the quaternions in October 1843 and then discover ...
.
See also
* Light's associativity test In mathematics, Light's associativity test is a procedure invented by F. W. Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. The naive procedure for verification of the associativ ...
* Telescoping series, the use of addition associativity for cancelling terms in an infinite series
* A semigroup is a set with an associative binary operation.
* Commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
and distributivity are two other frequently discussed properties of binary operations.
* Power associativity In mathematics, specifically in abstract algebra, power associativity is a property of a binary operation that is a weak form of associativity.
Definition
An algebra (or more generally a magma) is said to be power-associative if the subalgebra ge ...
, alternativity
In abstract algebra, alternativity is a property of a binary operation. A magma ''G'' is said to be if (xx)y = x(xy) for all x, y \in G and if y(xx) = (yx)x for all x, y \in G. A magma that is both left and right alternative is said to be () ...
, flexibility
Stiffness is the extent to which an object resists deformation in response to an applied force.
The complementary concept is flexibility or pliability: the more flexible an object is, the less stiff it is.
Calculations
The stiffness, k, of a bo ...
and N-ary associativity are weak forms of associativity.
* Moufang identities Moufang is the family name of the following people:
*Christoph Moufang (1817–1890), a Roman Catholic cleric
*Ruth Moufang (1905–1977), a German mathematician, after whom several concepts in mathematics are named:
** Moufang–Lie algebra
** Mo ...
also provide a weak form of associativity.
References
{{reflist
Properties of binary operations
Elementary algebra
Functional analysis
Rules of inference