Asszociativitás

A Wikipédiából, a szabad enciklopédiából
(Asszociatív szócikkből átirányítva)

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 egy tetszőleges halmaz és egy rajta értelmezett kétváltozós művelet (szokásos jelölés tetszőleges elemekre a helyett ); ezt akkor mondjuk asszociatívnak, ha tetszőleges elemeire teljesül:[1]

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

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: , szorzás esetében . (Itt mindkét példa esetében tetszőleges természetes, egész, racionális, valós vagy akár komplex szám.)

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

Az általánosított asszociativitás tétele[szerkesztés]

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 db. (nem feltétlenül különböző) elemekre az műveletsorozat bármilyen szabályos zárójelezéssel ugyanazt a rögzített elemet adja; itt .[2]
  • Legyenek tetszőleges A-beli véges sorozatok, ekkor , 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 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[szerkesztés]

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]

Bár nincs szakkönyv, amely ne tekintené-nevezné a halmazműveleteket asszociatívnak, hiszen formálisan érvényes (az unió „asszociativitása”) és 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[szerkesztés]

Lásd még[szerkesztés]

Jegyzetek[szerkesztés]

  1. Megjegyzés: helyett egyszerűen 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 automatikusan így zárójelezendő: ).
  2. E tétel az 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 esetében – automatikusan igaz.