Asszociativitás

A Wikipédiából, a szabad enciklopédiából

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×A→A egy rajta értelmezett kétváltozós művelet (szokásos jelölés tetszőleges x,y∈A elemekre a *(x,y)=c∈A helyett x*y=c); ezt akkor mondjuk asszociatívnak, ha az A tetszőleges x,y,z elemeire teljesül:

(x*y)*z = x*(y*z)  .[1]

Ez a függvény- (vagy prefix-) jelöléssel így írható:

*(*(x,y),z) = *(x,*(y,z))

Például a természetes, valós vagy akár a komplex számokon értelmezett szokásos összeadás és szorzás mind-mind asszociatív: (a+b)+c = a+(b+c), szorzás esetében (a·b)·c = a·(b·c). (Itt a, b és 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[szerkesztés | forrásszöveg szerkesztése]

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. különböző) a1, a2, …, an∈A elemekre az a1*a2*…*an :=c∈A műveletsorozat bármilyen szabályos zárójelezéssel ugyanazt a rögzített c elemet adja; itt n∈N+ értelemszerűen nemnegatív természetes számok.[2]
    • Legyenek A1, A2, …, Ak tetszőleges A-beli véges sorozatok, ekkor Π(A1∨A2∨…∨Ak) = Π(A1) · Π(A2) · … · Π(Ak), ahol Π a sorozatok A-beli produktumát (elemeinek sorrendben való összeszorzását); míg ∨ 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 db. taguk 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Bár nincs szakkönyv, amely ne tekintené-nevezné a halmazműveleteket asszociatívnak, hiszen formálisan érvényes mind (A∪B)∪C = A∪(B∪C) (az unió „asszociativitása” és (A∩B)∩C = A∩(B∩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 teljesern kifogástalanul járnak el, és ez esetben valóban beszélhetünk a halmazműveletek asszociativitásáról.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Megjegyzés: (x*y)*z helyett egyszerűen x*y*z is írható annak a szokásos zárójelezési konvenciónak az értelmében, miszerint a zárójelek nélküli, egy műveletet tartalmazó műveletsorozatokat balról jobbra kell kiolvasni és csoportosítani (tehát például x*y*z*u automatikusan így zárójelezendő:   (((x*y)*z)*u)  ).
  2. E tétel az n≥3 kikötés nélkül is értelmes, és – a lehetséges nem-triviális szabályos zárójelezések kisszámú (1) volta miatt n≤2 esetében – automatikusan igaz.