Asszociativitás
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
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]- 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
[szerkesztés]Jegyzetek
[szerkesztés]- ↑ 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ő: ).
- ↑ 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.