In
mathematics, the associative property is a property of some
binary operations, which means that rearranging the
parentheses
A bracket is either of two tall fore- or back-facing punctuation marks commonly used to isolate a segment of text or data from its surroundings. Typically deployed in symmetric pairs, an individual bracket may be identified as a 'left' or 'r ...
in an expression will not change the result. In
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
, associativity is a
valid rule of replacement 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
operands 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 numbers, it can be said that "addition and multiplication of real numbers are associative operations".
Associativity is not the same as
commutativity, 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 and
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
are associative, but (generally) not commutative.
Associative operations are abundant in mathematics; in fact, many
algebraic structures (such as
semigroups
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
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)
*Category (Kant)
* Categories (Peirce)
* ...
) explicitly require their binary operations to be associative.
However, many important and interesting operations are non-associative; some examples include
subtraction,
exponentiation, and the
vector 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 d ...
. In contrast to the theoretical properties of real numbers, the addition of
floating point 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 on a
set 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
Juxtaposition is an act or instance of placing two elements close together or side by side. This is often done in order to compare/contrast the two, to show similarities or differences, etc.
Speech
Juxtaposition in literary terms is the showin ...
) as for
multiplication.
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
In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective (\leftrightarrow) used to conjoin two statements and to form the statement " if and only if ", where is known as th ...
. 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 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 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, 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
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
represent
linear function
In mathematics, the term linear function refers to two distinct but related notions:
* In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For dist ...
s, and
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
represents function composition, one can immediately conclude that matrix multiplication is associative.
, 12= For
real numbers (and for any
totally ordered set), 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. The rules allow one to move parentheses in
logical expressions in
logical proofs. The rules (using
logical connectives notation) are:
and
where "
" is a
metalogic
Metalogic is the study of the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems.Harry GenslerIntroduction to Logic Routledge, ...
al
symbol representing "can be replaced in a
proof with".
Truth functional connectives
''Associativity'' is a property of some
logical connectives of truth-functional
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
. The following
logical equivalence
In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of p and q is sometimes expressed as p \equiv q, p :: q, \textsfpq, or p \iff q, depending o ...
s 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
:
;
Division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
:
;
Exponentiation
:
;
Vector 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 d ...
:
Also although addition is associative for finite sums, it is not associative inside infinite sums (
series
Series may refer to:
People with the name
* Caroline Series (born 1951), English mathematician, daughter of George Series
* George Series (1920–1995), English physicist
Arts, entertainment, and media
Music
* Series, the ordered sets used in ...
). For example,
whereas
Some non-associative operations are fundamental in mathematics. They appear often as the multiplication in structures called
non-associative algebra
A non-associative algebra (or distributive algebra) is an algebra over a field where the binary operation, binary multiplication operation is not assumed to be associative operation, associative. That is, an algebraic structure ''A'' is a non-ass ...
s, which have also an addition and a
scalar multiplication
In mathematics, scalar multiplication is one of the basic operations defining a vector space in linear algebra (or more generally, a module in abstract algebra). In common geometrical contexts, scalar multiplication of a real Euclidean vector b ...
. Examples are the
octonions and
Lie algebras. In Lie algebras, the multiplication satisfies
Jacobi identity
In mathematics, the Jacobi identity is a property of a binary operation that describes how the order of evaluation, the placement of parentheses in a multiple product, affects the result of the operation. By contrast, for operations with the associ ...
instead of the associative law; this allows abstracting the algebraic nature of
infinitesimal transformation
In mathematics, an infinitesimal transformation is a limiting form of ''small'' transformation. For example one may talk about an infinitesimal rotation of a rigid body, in three-dimensional space. This is conventionally represented by a 3×3 s ...
s.
Other examples are
quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
,
quasifield In mathematics, a quasifield is an algebraic structure (Q,+,\cdot) where + and \cdot are binary operations on Q, much like a division ring, but with some weaker conditions. All division rings, and thus all fields, are quasifields.
Definition
A qu ...
,
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 ...
, and
commutative non-associative magmas
In mathematics, there exist magma (algebra), magmas that are commutative but not associative. A simple example of such a magma may be derived from the children's game of rock, paper, scissors. Such magmas give rise to non-associative algebras.
A m ...
.
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 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 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
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
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 isomorphism, which enables partial application.
Right-associative operations include the following:
; Exponentiation 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 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 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[Exponentiation Associativity and Standard Math Notation](_blank)
Codeplea. 23 August 2016. Retrieved 20 September 2016.
:
; Knuth's up-arrow operators
:
:
; Taking the cross product of three vectors
:
; Taking the pairwise average of real numbers
:
; Taking the relative complement of sets
:.(Compare material nonimplication in logic.)
History
William Rowan Hamilton seems to have coined the term "associative property" around 1844, a time when he was contemplating the non-associative algebra of the octonions he had learned about from John T. Graves.
See also
* Light's associativity test
* Telescoping series
In mathematics, a telescoping series is a series whose general term t_n can be written as t_n=a_n-a_, i.e. the difference of two consecutive terms of a sequence (a_n).
As a consequence the partial sums only consists of two terms of (a_n) after c ...
, the use of addition associativity for cancelling terms in an infinite series
Series may refer to:
People with the name
* Caroline Series (born 1951), English mathematician, daughter of George Series
* George Series (1920–1995), English physicist
Arts, entertainment, and media
Music
* Series, the ordered sets used in ...
* A semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
is a set with an associative binary operation.
* Commutativity and distributivity
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmeti ...
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, 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
In algebra, ''n''-ary associativity is a generalization of the associative law
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the ...
are weak forms of associativity.
* Moufang identities also provide a weak form of associativity.
References
{{reflist
Properties of binary operations
Elementary algebra
Functional analysis
Rules of inference