# Tour:Associative binary operation

**This article adapts material from the main article:** associative binary operation

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)PREVIOUS: Invertible implies cancellative|UP: Introduction two (beginners)|NEXT: Inverse map is involutiveExpected time for this page: 5 minutes

General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

WHAT YOU NEED TO DO: Understand thoroughly theparenthesization can be droppedaspect of an associative binary operation (you don't need to work out the proof). This is crucial to manipulating expressions in groups, monoids, and semigroups.

PONDER: Try proving the statements about left, middle and right associative elements, to get a better understanding of how associativity works.

## Contents

## Definition

### Definition in infix notation

Let be a set and be a binary operation on (viz, is a map ), making a magma. We denote using infix notation, so that its application to is denoted . Then, is said to be **associative** if, for every in , the following identity holds:

where equality holds as elements of .

Note that are allowed to be equal or distinct. In particular, the above holds when all are equal, all are distinct, or two are equal and the third distinct.

*Detailed explanation of expressions and their interpretation*: The left side expression is termed the **left associated expression** for and is interpreted and evaluated as follows. We first consider . Since , we have . We now consider the elements . Since both of these are in , .

The right side expression is termed the **right associated expression** for and is interpreted and evaluated as follows. Since , we have . We consider consider the elements . Since both of these are in , .

If, for a given , the left associated expression and the right associated expression are equal, are said to *associate*. Associativity basically says that *every* ordered triple of elements associates.

### Definition in usual function notation

Let be a set and be a binary operation. We say that is **associative** if it satisfies the following for all :

We see that the condition feels a lot less intuitive in function notation than with the infix notation, which is why infix notation is generally preferred for describing associativity in the context of binary operations.

### 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:

*any* choice of bracketing will give the same result.

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

As an illustration, suppose we want to show that:

Then, we apply associativity in a chain:

For this reason, we always use infix operator symbols for associative binary operations, and often even drop the operator symbol, so that the expression is just written as: .

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.

### Power structure

`Further information: power-associative magma`

In the presence of associativity, it is possible to unambiguously define positive powers of any element. Explicitly, is the -fold product . The powers satisfy the usual laws of powers: and for all . Note that this also implies that all powers of commute with each other.

Note that to define powers, we do not actually need global associativity, but only power-associativity: the submagma generated by any single element must be associative.

### Invertibility

- Equality of left and right inverses in monoid: Associativity can be used to deduce that any left inverse and right inverse with respect to a neutral element must be equal.
- Two-sided inverse is unique if it exists in monoid: Associativity can be used to show uniqueness of two-sided inverses in a monoid.
- Invertible implies cancellative in monoid: Associativity can be used to show that an element with a left inverse is left-cancellative, and an element with a right inverse is right-cancellative.

This page is part of the Groupprops guided tour for beginners. Make notes of any doubts, confusions or comments you have about this page before proceeding.PREVIOUS: Invertible implies cancellative|UP: Introduction two (beginners)|NEXT: Inverse map is involutive