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

( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) {\displaystyle (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 ∗ ∗ {\displaystyle 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 ) {\displaystyle (a+b)+c=a+(b+c)} , szorzás esetében ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) {\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)} . (Itt a , b , c {\displaystyle 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 , ∗ ) {\displaystyle (A,*)} matematikai struktúrákat, melyek ∗ {\displaystyle *} 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 ∗ {\displaystyle *} kétváltozós művelet asszociatív;
  • Tetszőleges n {\displaystyle n} db. (nem feltétlenül különböző) a 1 , a 2 , … , a n ∈ A {\displaystyle a_{1},a_{2},\dots ,a_{n}\in A} elemekre az a 1 ∗ a 2 ∗ ⋯ ∗ a n := c ∈ A {\displaystyle 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 {\displaystyle c} elemet adja; itt n ∈ N + {\displaystyle n\in \mathbb {N} ^{+}} .[2]
  • Legyenek A 1 , A 2 , … , A k {\displaystyle A_{1},A_{2},\dots ,A_{k}} tetszőleges A-beli véges sorozatok, ekkor ∏ ( A 1 ∨ A 2 ∨ … ∨ A k ) = ∏ ( A 1 ) ⋅ ∏ ( A 2 ) ⋅ … ⋅ ∏ ( A k ) {\displaystyle \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 ∏ {\displaystyle \textstyle \prod } a sorozatok A-beli produktumát (elemeinek sorrendben való összeszorzását), míg ∨ {\displaystyle \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 ∪ B ) ∪ C = A ∪ ( B ∪ C ) {\displaystyle (A\cup B)\cup C=A\cup (B\cup C)} (az unió „asszociativitása”) és ( A ∩ B ) ∩ C = A ∩ ( B ∩ C ) {\displaystyle (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

Jegyzetek

  1. ↑ Megjegyzés: ( x ∗ y ) ∗ z {\displaystyle (x*y)*z} helyett egyszerűen x ∗ y ∗ z {\displaystyle 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 {\displaystyle x*y*z*u} automatikusan így zárójelezendő: ( ( x ∗ y ) ∗ z ) ∗ u {\displaystyle ((x*y)*z)*u} ).
  2. ↑ E tétel az n ≥ 3 {\displaystyle n\geq 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 {\displaystyle n\leq 2} esetében – automatikusan igaz.
  • matematika Matematikaportál • összefoglaló, színes tartalomajánló lap