Asszociativitás

A matematikában az asszociativitás vagy csoportosíthatóság a kétváltozós (binér/bináris) matematikai műveletek egy tulajdonsága, fontos algebrai azonosság: ha $A$ egy tetszőleges halmaz és $*\!:\ A\times A\rightarrow A$ egy rajta értelmezett kétváltozós művelet (szokásos jelölés tetszőleges $x,y\in A$ elemekre a $*\!(x,y)=c\in A$ helyett $x*y=c$); ezt akkor mondjuk asszociatívnak, ha $A$ tetszőleges $x,y,z$ elemeire teljesül:

$$(x*y)*z=x*(y*z)$$

Ez a függvény fordított lengyel jelöléssel (RPN — Reverse Polish Notation) így írható:

$$x\ y\ z**=y\ z\ x**$$

Például a természetes, valós vagy akár a komplex számokon értelmezett szokásos összeadás és szorzás mind asszociatív: $(a b) c=a (b c)$, szorzás esetében $(a\cdot b)\cdot c=a\cdot (b\cdot c)$. (Itt $a,b,c$ mindkét példa esetében tetszőleges természetes, egész, racionális, valós vagy akár komplex szám.)

Azokat az $(A,*)$ matematikai struktúrákat, melyek $*$ művelete asszociatív, félcsoportoknak nevezzük.

Az általánosított asszociativitás tétele

Az asszociativitás fenti követelménye valójában csak speciális esete a következő tulajdonságnak:

Tétel: Ugyanazt jelentik (ekvivalensek) a következő állítások:

• Az A halmazon értelmezett $*$ kétváltozós művelet asszociatív;
• Tetszőleges $n$ db. (nem feltétlenül különböző) $a_{1},a_{2},\dots ,a_{n}\in A$ elemekre az $a_{1}*a_{2}*\dots *a_{n}:=c\in A$ műveletsorozat bármilyen szabályos zárójelezéssel ugyanazt a rögzített $c$ elemet adja; itt $n\in \mathbb {N} ^{ }$.
• Legyenek $A_{1},A_{2},\dots ,A_{k}$ tetszőleges A-beli véges sorozatok, ekkor $\textstyle \prod (A_{1}\vee A_{2}\vee \ldots \vee A_{k})=\textstyle \prod (A_{1})\cdot \textstyle \prod (A_{2})\cdot \ldots \cdot \textstyle \prod (A_{k})$, ahol $\textstyle \prod$ a sorozatok A-beli produktumát (elemeinek sorrendben való összeszorzását), míg $\vee$ az adott sorrendben való „egyesítésüket” jelöli.

Egységelemes félcsoportban megengedhetjük azt is, hogy a fent említett sorozatok üresek legyenek, azaz nulla tagjuk legyen.

(A fenti állítások igazolása értelemszerűen végzett teljes indukcióval történhet.)

Asszociativitás és Cayley-tábla: a Light-teszt

Egy művelet asszociativitása a művelettáblájáról (Cayley-tábla) általában nem olvasható le olyan könnyen, mint például a kommutativitás. Az asszociativitás megállapítására át kell alakítani a táblázatot, erre alkalmas az ún. Light-féle eljárás.

Megjegyzés a halmazműveletek asszociativitásáról

Bár nincs szakkönyv, amely ne tekintené-nevezné a halmazműveleteket asszociatívnak, hiszen formálisan érvényes $(A\cup B)\cup C=A\cup (B\cup C)$ (az unió „asszociativitása”) és $(A\cap B)\cap C=A\cap (B\cap C)$ is (a metszetképzés „asszociativitása”), meg kell jegyeznünk, hogy az asszociativitás fogalma csak műveletekre van definiálva, a halmazműveletek pedig nem szigorú értelemben vett matematikai műveletek, hiszen műveletet csak valamilyen alaphalmaz felett értelmezhetünk (az összes halmaz halmazáról viszont, aminek a halmazműveletek alaphalmazának kellene lennie, ellentmondásossága miatt nem beszélhetünk). Azok a szakkönyvek, amelyek a halmazműveleteket valamely U halmaz hatványhalmazának elemeire, azaz egy U részhalmazaira szorítkozva definiálják, matematikai szempontból teljesen kifogástalanul járnak el, és ez esetben valóban beszélhetünk a halmazműveletek asszociativitásáról.

További információk

• Alice és Bob - 11. rész: Alice és Bob számelméletet épít
• Alice és Bob - 12. rész: Alice és Bob rendet tesz
• Alice és Bob - 13. rész: Alice és Bob eladósodik

Lásd még

• Kommutativitás
• Disztributivitás