Ассоциативность (математика)

Ассоциати́вность (сочетательность) — свойство бинарной операции $\circ <!--\; \circ \; -->$$\circ$, заключающееся в возможности осуществлять последовательное применение формулы $(x\circ <!--\; \circ \; -->y)\circ <!--\; \circ \; -->z=x\circ <!--\; \circ \; -->(y\circ <!--\; \circ \; -->z)$$(x\circ y)\circ z=x\circ (y\circ z)$ в произвольном порядке к элементам $x,y,z$$x,\;y,\;z$.

Визуализация ассоциативности $(x\circ <!--\; \circ \; -->y)\circ <!--\; \circ \; -->z=x\circ <!--\; \circ \; -->(y\circ <!--\; \circ \; -->z)$$(x\circ y)\circ z=x\circ (y\circ z)$

Термин ввёл Уильям Гамильтон в 1853 году.

Поскольку для ассоциативных операций результат выражения $x_1\circ <!--\; \circ \; -->x_2\circ <!--\; \circ \; -->\dots <!--\; \dots \; -->\circ <!--\; \circ \; -->x_n$$x_{1}\circ x_{2}\circ \ldots \circ x_{n}$ не зависит от порядка применения, скобки при записи опускаются. Для неассоциативной операции выражение $x_1\circ <!--\; \circ \; -->x_2\circ <!--\; \circ \; -->\dots <!--\; \dots \; -->\circ <!--\; \circ \; -->x_n$$x_{1}\circ x_{2}\circ \ldots \circ x_{n}$ при $n>2$$n>2$ не определено без дополнительных соглашений о порядке применения.

Примеры ассоциативных операций:

• сложение действительных чисел: $(a+b)+c=a+(b+c)$$(a+b)+c=a+(b+c)$
• умножение действительных чисел: $(a\cdot <!--\; \cdot \; -->b)\cdot <!--\; \cdot \; -->c=a\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->c)$$(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• композиция функций: $(H\circ <!--\; \circ \; -->G)\circ <!--\; \circ \; -->F=H\circ <!--\; \circ \; -->(G\circ <!--\; \circ \; -->F)$$(H\circ G)\circ F=H\circ (G\circ F)$

Примером неассоциативной операции является возведение в степень — результат выражения $a^{b^c}$$a^{b^{c}}$ напрямую зависит от расстановки скобок, в общем случае $a^{(b^c)}\ne <!--\; \ne \; -->(a^b{)}^c$$a^{(b^{c})}\neq (a^{b})^{c}$.

Не всякая коммутативная операция ассоциативна — существуют коммутативные магмы^[en] с неассоциативной.

Ассоциативность играет важную роль в общей алгебре: в большинстве рассматриваемых структур бинарные операции ассоциативны (группы, кольца, поля, полурешётки и решётки). Теория полугрупп фактически исследует феномен ассоциативности общеалгебраическими методами. При этом особо рассматриваются и неассоциативные системы, а именно: квазигруппы, лупы, неассоциативные кольца, неассоциативные алгебры^[en]. Их изучение осложнено тем, что многие свойства ассоциативных систем для них не имеют места. Иногда проблемы переносимости свойств на неассоциативные структуры оказываются нетрививиальными (например, открыт вопрос о выполнении теоремы Лагранжа для конечных луп).

В информатике ассоциативность считается полезным свойством, в частности, позволяющим задействовать параллелизм для последовательных применений операции. В то же время многие практические операции (сложение и умножение при работе с числами с плавающей запятой) оказываются неассоциативными.

Свойство естественным образом обобщается на $n$$n$-арный случай: операция $\mathrm{\phi <!--\; \phi \; -->}:<!--\; :\; -->X^n\to <!--\; \to \; -->X$$\varphi \colon X^{n}\to X$ называется ассоциативной, если для всех $i=1,\dots <!--\; \dots \; -->,n$$i = 1, \dots, n$ имеет место тождество:

$\mathrm{\phi <!--\; \phi \; -->}(\mathrm{\phi <!--\; \phi \; -->}(x_1,\dots <!--\; \dots \; -->,x_n),x_{n+1},\dots <!--\; \dots \; -->,x_{2n-<!--\; -\; -->1})=\mathrm{\phi <!--\; \phi \; -->}(x_1,\dots <!--\; \dots \; -->,x_i,\mathrm{\phi <!--\; \phi \; -->}(x_{i+1},x_{i+2},\dots <!--\; \dots \; -->,x_{i+n}),x_{i+n+1},\dots <!--\; \dots \; -->,x_{2n-<!--\; -\; -->1})$$\varphi (\varphi (x_{1},\dots ,x_{n}),x_{n+1},\dots ,x_{2n-1})=\varphi (x_{1},\dots ,x_{i},\varphi (x_{i+1},x_{i+2},\dots ,x_{i+n}),x_{i+n+1},\dots ,x_{2n-1})$.

Ослабленные варианты свойства ассоциативности — степенная ассоциативность, альтернативность, эластичность^[en] — в них изменение очерёдности последовательного применения возможно только для ограниченного набора случаев.

ЛитератураПравить

• Ассоциативность — статья из Математической энциклопедии. О. А. Иванова, Д. М. Смирнов
• Шеврин Л. Н. Глава IV. Полугруппы // Общая алгебра / Под общ. ред. Л. А. Скорнякова. — М.: Наука, 1991. — Т. 2. — С. 11—191. — 480 с. — (Справочная математическая библиотека). — 25 000 экз. — ISBN 5-9221-0400-4.