Associative binary operation: Difference between revisions

Revision as of 19:36, 27 June 2009

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} \dots a_{n}$ .

Associativity pentagon

Further information: Associativity pentagon

The associativity pentagon is a pentagon whose vertices are the five different ways of associating a product of length four, with an edge between two vertices if moving from one to the other requires a single application of the associative law. This is a cyclic pentagon. The associativity pentagon is significant because, loosely, it generates all relations between the different ways of applying the associativity law to re-parenthesize expressions. It also helps to prove results about the set of left-associative, middle-associative, and right-associative elements.

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: Equality of left and right inverses in monoid

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.

For full proof, refer: Left-associative elements of magma form submagma

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.

@@ Line 37: / Line 37: @@
 <math>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</math>
-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: <math>a_1a_2...a_n</math>.
+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: <math>a_1a_2 \dots a_n</math>.
+===Associativity pentagon===
+{{further|[[Associativity pentagon]]}}
+The associativity pentagon is a pentagon whose vertices are the five different ways of associating a product of length four, with an edge between two vertices if moving from one to the other requires a single application of the associative law. This is a cyclic pentagon. The associativity pentagon is significant because, loosely, it generates all ''relations'' between the different ways of applying the associativity law to re-parenthesize expressions. It also helps to prove results about the set of left-associative, middle-associative, and right-associative elements.
 ===Inverses are unique===