Overenie asociatívnosti z tabuľky

[Martin Sleziak]

Mala by som dotaz k testovaniu asociativity v tomto type príkladov. Predpokladajme, že naša (M,+) nie je identická (alebo si nevšimneme, že je identická) s nejakou (X, +), o ktorej by sme vedeli, že je grupa, a teda že (M,+) by bola grupa. Vieme otestovať asociativitu aj inak než testovaním všetkých možností? Ja som vo svojom riešení tohto príkladu tiež využila len otestovanie všetkých prípadov, ktoré môžu nastať, lebo nič lepšie (ak také niečo existuje) mi nenapadlo.

Asi stručná odpoveď je, že ak máme zadanú iba tabuľku, tak kontrolu asociatívnosti nevieme vymyslieť nejako výrazne efektívnejšie ako kontrolou všetkých trojíc (prinajmenšom čo sa týka počtu potrebných operácií, možno pri veľkej tabuľke by sa oplatilo porozmýšľať ako to prehľadnejšie zapísať).

V typických príkladoch aké sa môžu objaviť na písomkách či v domácich úlohách sa asi takéhoto niečoho netreba obávať - tam tabuľky nebudú príliš veľké. (A ak by sa predsa objavila nejaká úloha kde je dôležité si niečo všimnúť, tak zadanie bude pravdepodobne obsahovať nejaký hint.)

Čosi sa dá ušetriť tým, ak si všimneme že ak jeden z týchto troch prvkov je neutrálny prvok tak $(x*y)*z=x*(y*z)$ určite platí. (A zostávajú overiť trojice kde dosadzujem prvky okrem neutrálneho.)

Ak je zadaná operácia komutatívna (čo ľahko vidno z tabuľky), tak ešte môžeme ušetriť pár ďalších trojíc, ktoré nemusíme rátať. Napríklad z komutatívnosti hneď vidno, že sa budú zhodovať výsledky pre takéto trojice: $x*(x*x)=(x*x)*x$ alebo $(x*y)*x=x*(y*x)$.
Takisto v prípade komutatívnej operácie overujeme viacero trojíc naraz. Ak sme už skontrolovali že $x*(y*z)=(x*y)*z$, tak hneď máme zadarmo to že asociatívnosť platí keď otočíme poradie, t.j. $z*(y*x)=(z*y)*x$.

Ak by si o tomto niekto chcel prečítať viac, tak pridám aj nejaké linky:

• Light's associativity test (Wikipedia)
• Is there an easy way to see associativity or non-associativity from an operation's table? (Mathematics Stack Exchange)

Ak sa pozriete na tieto linky, tak zistíte, že ešte by sa dalo o čosi viac ušetriť tým, ak by sme kontrolovali asociatívnosť iba pre prvky ktoré sú generátormi. Tým sa myslí to, že ostatné prvky už viem dostať z nich pomocou danej operácie.

Inak povedané, ak som overil asociatívnosť pre všetky trojice obsahujúce $a$, $b$; tak už nemusím kontrolovať trojice obsahujúce $a*b$, $b*a$, $a*b*a$ a podobne.

Spoiler:

Trochu detailnejšie: Ak mám operáciu $*$ na množine $X$, tak to že $a,b,c\in X$ sú generátory znamená, že každý prvok sa dá zapísať v tvare $x=x_1*x_2*\dots*x_n$, kde každé $x_i$ je niektorý z prvkov $a$, $b$, $c$. (Pripomeniem, že zátvorky vo výrazoch tvaru $x_1*x_2*\dots*x_n$ písať nemusím - zovšeobecnený asociatívny zákon mi hovorí, že každé uzátvorkovanie pre asociatívnu operáciu dá to isté.)
Ak sa potom pozerám na rôzne uzátvorkovania $x*y*z$, tak je to to isté ako pozrieť sa na dve konkrétne uzátvorkovania $(x_1*x_2*\dots*x_n)*(y_1*y_2*\dots*y_s)*(z_1*z_2*\dots*z_t)$.