Associative binary operation

From Groupprops

Jump to: navigation, search

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.

Numerical invariants

The associative law is typically viewed as a universally quantified identity. In this context, we discuss some invariants that can be associated with the identity.

Invariant	Value	Significance
minimum number of variables in terms of which the identity can be expressed	$3$	A magma is associative if and only if the submagma generated by any $3$ elements is associative; nothing smaller than $3$ works
degree of the identity in each variable	$1$	when this identity is viewed for the multiplicative operation of a ring or algebra, it is a linear identity in each variable. In particular, the set of values for each variable such that the identity holds for all values of the other variables is an additive subgroup.

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_1a_2 \dots a_n$ .

Also, the re-parenthesization identities (i.e., all identities that are special cases of generalized associativity) are the only identities that can be proved using associativity.

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. It is also related to the associator identity.

Associator on a non-associative ring and the associator identity

Further information: associator on a non-associative ring

For a non-associative ring $R$ with multiplication $*$ , we can define the associator $a:R \times R \times R \to R$ as:

$a (x, y, z) = ((x * y) * z) - (x * (y * z))$

This is linear in each of its variables.

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.

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

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.

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

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 (or sometimes, the nucleus) of the magma.

Weaker identities

Identities obtained directly by duplicating variables

Algebraic formulation of identity	Name of identity	Name of magma satisfying identity	Name of non-associative ring satisfying identity
$\! x * (x * y) = (x * x) * y$	left-alternativity	left-alternative magma	left-alternative ring
$\! x * (y * y) = (x * y) * y$	right-alternativity	right-alternative magma	right-alternative ring
$\! x * (y * x) = (x * y) * x$	flexibility	flexible magma	flexible ring
$\! x * (x * x) = (x * x) * x$	?	magma in which cubes are well-defined	ring in which cubes are well-defined

Identities obtained from generalized associativity by duplicating variables

We here discuss identities with products of length at most four:

Algebraic formulation of identity	Name of identity	Name of magma satisfying identity	Name of non-associative ring satisfying identity
$\! (x * y) * (x * x) = x * (y * (x * x))$	Jordan's identity	? (if we also assume commutativity, then Jordan magma)	? (if we also assume commutativity, then Jordan ring)
$\! z * (x * (z * y)) = ((z * x) * z) * y$	One of Moufang's identities	?	?
$\! x * (z * (y * z)) = ((x * z) * y) * z$	One of Moufang's identities	?	?
$\! (z * x) * (y * z) = (z * (x * y)) * z$	One of Moufang's identities	?	?

Associative binary operation

From Groupprops

Contents

Definition

Definition with symbols

Related term

Numerical invariants

Facts

Parenthesization can be dropped

Associativity pentagon

Associator on a non-associative ring and the associator identity

Inverses are unique

Related element properties

Left-associative element

Middle-associative element

Right associative element

Associative element

Weaker identities

Identities obtained directly by duplicating variables

Identities obtained from generalized associativity by duplicating variables

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

lookup

Credits

Toolbox

request/feedback

subject wikis