Associative binary operation

This article defines a property of binary operations (and hence, of magmas)

Definition

Definition with symbols

Let $S$ be a set and $*$ be a binary operation on $S$ (viz, $*$ is a map $S\times S\to S$). Then, $*$ is said to be associative if, for every $a,b,c$ in $S$, the following identity holds:

$(a*b)*c=a*(b*c)$

The expression on the left side is termed the left associated expression and the expression on the right side is termed the right associated expression. If, for a given $a,b,c$, the left associated expression and the right associated expression are equal, $a,b,c$ are said to associate. Associativity basically says that any ordered triple of elements associates.

Related term

A set equipped with an associative binary operation is termed a semigroup. If, further, there is a neutral element (identity element) for the associative binary operation, the set is termed a monoid.

Facts

Parenthesization can be dropped

For full proof, refer: Associative implies generalized associative

When a binary operation is associative, it turns out that we can drop parenthesization from products of many elements. That is, given an expression of the form:

$a_1*a_2...*a_n$

any choice of bracketing will give the same result.

The result is proved by induction, with the base case ($n=3$) following from the definition of associativity.

As an illustration, suppose we want to show that:

$a_1*(a_2*(a_3*a_4))=((a_1*a_2)*a_3)*a_4$

Then, we apply associativity in a chain:

$a_1*(a_2*(a_3*a_4))=a_1*((a_2*a_3)*a_4)=(a_1*(a_2*a_3))*a_4=((a_1*a_2)*a_3)*a_4$

For this reason, we always use infix operator symbols for associative binary operations, and often even drop the operator symbol, so that the above expression is just written as: $a_1{a}_2...a_n$.

Inverses are unique

In a monoid (that is, a set with associative binary operation having a neutral element) any left inverse and right inverse of an element must be equal. Hence, the inverse of an element, if it exists, must be unique. For full proof, refer: Inverse element#Equality of left and right inverse

Related element properties

Left associative element

An element is said to be left associative with respect to a binary operation if any ordered triple starting with that element associates.

The set of left associative elements in any magma is a subsemigroup, and if the magma contains a neutral element, it is a submonoid.

Middle associative element

An element is said to be middle associative with respect to a binary operation if any ordered triple with that element in the middle, associates.

The set of middle associative elements in any magma is a subsemigroup, and if the magma contains a neutral element, it is a submonoid.

Right associative element

An element is said to be right associative with respect to a binary operation if any ordered triple ending with that element associates.

The set of right associative elements in any magma is a subsemigroup, and if the magma contains a neutral element, it is a submonoid.

Associative element

Further information: associative element An element is said to be associative if it is left, middle and right associative. The set of associative elements forms a submagma (which contains the neutral element if it exists) termed the associative center of the magma.