Associativity equation

This article is about the functional equation for binary operations. For the algebraic law itself, see Associative property.

The associativity equation or associativity functional equation is the functional equation

${\displaystyle F(F(x,y),z)=F(x,F(y,z))}$

Associativity equation

A binary operation F is associative when {{{1}}}.
Type	Functional equation
Field	Functional equation Abstract algebra Semigroup theory Fuzzy logic Probability theory
Symbolic statement	General form ${\displaystyle F(F(x,y),z)=F(x,F(y,z))}$

for a function ${\displaystyle F\colon X\times X\to X}$. It characterizes those binary operations ${\displaystyle F}$ on a set ${\displaystyle X}$ that are associative in the usual algebraic sense, and therefore underlies the study of semigroups and many kinds of aggregation operators. When additional regularity conditions (such as continuity and monotonicity) are imposed, the equation has a rich and fairly explicit theory of solutions.

Definition

Let ${\displaystyle X}$ be a non-empty set, and let ${\displaystyle F\colon X\times X\to X}$ be a binary operation. The function ${\displaystyle F}$ is said to satisfy the associativity equation if

${\displaystyle F(F(x,y),z)=F(x,F(y,z))\quad {\text{for all }}x,y,z\in X.}$

Equivalently, if one writes ${\displaystyle x*y=F(x,y)}$, then the equation becomes

${\displaystyle (x*y)*z=x*(y*z)}$

for all ${\displaystyle x,y,z\in X}$, which is precisely the usual associative property of the operation ${\displaystyle *}$. Thus, solutions of the associativity equation are in one-to-one correspondence with associative binary operations on ${\displaystyle X}$, and the pair ${\displaystyle (X,F)}$ forms a semigroup whenever the equation holds.

In the context of functional equations, however, the function ${\displaystyle F}$ is often unknown, and the goal is to determine all operations ${\displaystyle F}$ on a given domain that satisfy the associativity equation together with additional side conditions.

History

An early appearance of an associativity-type functional equation is found in an 1826 paper of Niels Henrik Abel, who studied bivariate functions ${\displaystyle f(x,y)}$ such that ${\displaystyle f(z,f(x,y))}$ is symmetric in its three arguments.^[1]

In the 20th century the associativity equation became a standard object of study in the theory of functional equations, especially through the work of János Aczél. In a 1948 paper on real binary operations and in his later monograph Lectures on Functional Equations and Their Applications, Aczél gave general representation theorems for continuous, strictly monotone solutions of the associativity equation on real intervals.^[2][3]

Subsequent work by many authors refined and extended these results, for example by relaxing strict monotonicity or by imposing additional boundary conditions. Notable contributions include representation theorems for associative functions on compact intervals due to Cho-Hsin Ling, and later systematic treatments by Richard Craigen, Zsolt Páles and Jean-Luc Marichal, among others.^[4][5]

Solutions on real intervals

Continuous strictly increasing solutions

Let ${\displaystyle E}$ be a real interval (finite or infinite) that is open on at least one side, and let ${\displaystyle F\colon E^{2}\to E}$ be continuous and strictly increasing in each argument. A classical theorem (often attributed to Aczél) states that such an ${\displaystyle F}$ is associative if and only if there exists a continuous strictly monotone function ${\displaystyle f\colon E\to \mathbb {R} }$ such that

${\displaystyle F(x,y)=f^{-1}{\bigl (}f(x)+f(y){\bigr )}\quad {\text{for all }}x,y\in E.}$^[2][3][5]

Thus, up to a monotone change of variable, every continuous strictly increasing solution of the associativity equation on a real interval is isomorphic to ordinary addition on a (possibly different) real interval. The choice of ${\displaystyle f}$ is unique up to multiplication by a nonzero constant.

Simple examples include:

• ${\displaystyle F(x,y)=x+y}$ on any interval stable under addition (here ${\displaystyle f(x)=x}$),
• ${\displaystyle F(x,y)=xy}$ on the positive reals (here ${\displaystyle f(x)=\log x}$), and
• more generally, any operation obtained from addition by conjugating with a strictly monotone homeomorphism of the interval.

Such semigroups are sometimes called Aczélian or additively representable.^[5]

Continuous nondecreasing solutions

The classification of continuous associative operations that are merely nondecreasing (rather than strictly increasing) is more involved. For functions ${\displaystyle M\colon [a,b]^{2}\to [a,b]}$ that are continuous, nondecreasing and associative, and satisfy natural boundary conditions expressing the existence of an identity and the absence of non-trivial idempotents, one obtains representation theorems in terms of so-called additive generators.^[6][5]

For example, suppose ${\displaystyle M}$ is continuous, nondecreasing and associative on ${\displaystyle [a,b]}$, and that ${\displaystyle b}$ acts as an identity while <math]a,b[</math> contains no idempotent elements. Then there exists a continuous strictly decreasing function ${\displaystyle f\colon [a,b]\to [0,+\infty ]}$ with ${\displaystyle f(b)=0}$ such that

${\displaystyle M(x,y)=f^{-1}\!{\bigl (}\min(f(x)+f(y),f(a)){\bigr )}}$

for all ${\displaystyle x,y\in [a,b]}$ (up to a natural equivalence on the choice of generator).^[5] Depending on whether ${\displaystyle f(a)}$ is finite or infinite, this yields well-known families of operations related to the product t-norm and the Łukasiewicz t-norm, after a suitable rescaling of the interval.

Dual statements, where ${\displaystyle a}$ is an identity and ${\displaystyle b}$ plays the role of a zero, describe disjunctive associative operations that are closely related to standard t-conorms.^[5]

More generally, continuous nondecreasing associative operations on a compact interval can be built as ordinal sums of such basic blocks together with the pointwise minimum and maximum operations.^[4][5]

Applications

Aggregation functions and fuzzy logic

In fuzzy logic and aggregation function theory, one often studies binary operations ${\displaystyle M\colon [0,1]^{2}\to [0,1]}$ that are associative, monotone and satisfy specific boundary conditions, such as

${\displaystyle M(0,x)=0,\quad M(1,x)=x,}$

or their duals. Continuous associative operations of this type are exactly the continuous t-norms and t-conorms used to model generalized logical conjunction and disjunction, respectively.^[7][5]

The associativity equation, together with monotonicity and continuity assumptions, plays a central role in characterizing these classes of aggregation operators and in studying their generators and ordinal sums.^[5][8]

Foundations of probability and rational belief

In the foundations of Bayesian probability and Cox's theorem, one considers a real-valued plausibility measure on propositions and seeks a binary operation combining plausibilities of the form ${\displaystyle F(x,y)}$ that corresponds to logical conjunction. Requiring this operation to be associative (as conjunction is), monotone and compatible with basic logical constraints leads to the associativity equation for ${\displaystyle F}$. Under suitable regularity assumptions, there exists a monotone re-grading ${\displaystyle w}$ such that

${\displaystyle w(F(x,y))=w(x)\,w(y),}$

so that in the re-graded scale the operation becomes ordinary multiplication and one recovers the usual product rule of probability theory.^[9][10][3]

Semigroup theory and ordered structures

Whenever ${\displaystyle F\colon X\times X\to X}$ satisfies the associativity equation, the pair ${\displaystyle (X,F)}$ is a semigroup. Conversely, many structural results about topological or ordered semigroups can be formulated as functional-equation results about associative operations satisfying continuity, order-preservation or other constraints.^[3][4][5]

For instance, continuous cancellative semigroups on real intervals can often be represented, up to isomorphism, by addition on an interval via a monotone change of variable, as in the strictly increasing case described above.

Generalizations

A number of functional equations generalize or are closely related to the associativity equation, including:

• Generalized associativity, where the right-hand side involves a different operation, such as ${\displaystyle F(F(x,y),z)=G(x,F(y,z))}$, leading to bisymmetry-type equations.^[8]
• Preassociativity, where associativity is required only after certain identifications of arguments, a notion useful in the study of string functions and aggregation operators.^[11]
• n-ary generalizations defining associative operations of higher arity through systems of functional equations.

The associativity equation is also related to other classical functional equations, such as the Abel equation and various translation equations, which describe one-parameter groups of transformations.^[8]

See also

• Associative property
• Functional equation
• Semigroup
• Triangular norm
• Aggregation function
• Abel equation
• Cox's theorem