# Associative operation

An as­so­ci­a­tive op­er­a­tion $$\bullet : X \times X \to X$$ is a bi­nary op­er­a­tion such that for all $$x, y, z$$ in $$X$$, $$x \bullet (y \bullet z) = (x \bullet y) \bullet z$$. For ex­am­ple, $$+$$ is an as­so­ci­a­tive func­tion, be­cause $$(x + y) + z = x + (y + z)$$ for all val­ues of $$x, y,$$ and $$z$$. When an as­so­ci­a­tive func­tion is used to com­bine many el­e­ments in a row, paren­the­sis can be dropped, be­cause the or­der of ap­pli­ca­tion is ir­rele­vant.

Imag­ine that you’re try­ing to use $$f$$ to com­bine 3 el­e­ments $$x, y,$$ and $$z$$ into one el­e­ment, via two ap­pli­ca­tions of $$f$$. $$f$$ is as­so­ci­a­tive if $$f(f(x, y), z) = f(x, f(y, z)),$$ i.e., if the re­sult is the same re­gard­less of whether you ap­ply $$f$$ to $$x$$ and $$y$$ first (and then ap­ply that re­sult to $$z$$), or whether you ap­ply $$f$$ to $$y$$ and $$z$$ first (and then ap­ply $$x$$ to that re­sult).

Vi­su­al­iz­ing $$f$$ as a phys­i­cal mechanism, there are two differ­ent ways to hook up two copies of $$f$$ to­gether to cre­ate a func­tion $$f_3 : X \times X \times X \to X,$$ which takes three in­puts and pro­duces one out­put: An as­so­ci­a­tive func­tion $$f$$ is one where the re­sult is the same no mat­ter which way the func­tions are hooked up, which means that the re­sult of us­ing $$f$$ twice to turn three in­puts into one out­put yields the same out­put re­gard­less of the or­der in which we com­bine ad­ja­cent in­puts. By similar ar­gu­ment, an as­so­ci­a­tive op­er­a­tor $$f$$ also gives rise (un­am­bigu­ously) to func­tions $$f_4, f_5, \ldots,$$ mean­ing that as­so­ci­a­tive func­tions can be seen as a fam­ily of func­tions on lists.

This jus­tifies the omis­sion of paren­the­sis when writ­ing ex­pres­sions where an as­so­ci­a­tive op­er­a­tor $$\bullet$$ is ap­plied to many in­puts in turn, be­cause the or­der of ap­pli­ca­tion does not mat­ter. For ex­am­ple, mul­ti­pli­ca­tion is as­so­ci­a­tive, so we can write ex­pres­sions such as $$2 \cdot 3 \cdot 4 \cdot 5$$ with­out am­bi­guity. It makes no differ­ence whether we com­pute the re­sult by first mul­ti­ply­ing 2 by 3, or 3 by 4, or 4 by 5.

By con­trast, the func­tion prependx that sticks its in­puts to­gether and puts an x on the front is not as­so­ci­a­tive: prependx(prependx(“a”,”b”),”c”) = “xxabc”, but prependx(“a”,prependx(“b”,”c”))=xaxbc.

Children:

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

• in X, such that

• Fixed, thanks.

• Sugges­tion: Mark this thread as an “ed­i­tor only” com­ment.