Decir que tengo la mesa de operación de un magma. Quiero saber si la operación es asociativa. Sin embargo, la asociatividad se define para una operación en 3 elementos y trata de la tabla de operación solamente con dos. Así que no es claro cómo determinar si la operación es asociativa sólo mirando la tabla. ¿Es posible, o uno sólo tiene que probar cada combinación de tres elementos por fuerza bruta?
Respuestas
¿Demasiados anuncios?
Adam Tuttle
Puntos
7982
En ausencia de cualquier otra información, entonces, sí, es necesario comprobar cada triple. Hay un teorema (debido a la G. Szasz) que afirma que en cualquier conjunto con, al menos, cuatro elementos, no es una operación binaria para el que no es exactamente un no-asociativo triple. (De hecho, no son tales operaciones en los tres elementos de los conjuntos también; $10$ de ellos, hasta el isomorfismo.)
Una referencia para el Szasz teorema es:
@ARTICLE{Szasz1953,
AUTHOR = {G. Szasz},
TITLE = {{D}ie {U}nabh\"{a}ngigkeit der {A}ssoziativit\"{a}tsbedingungen},
JOURNAL = {Acta Sci. Math. Szeged},
VOLUME = {15},
YEAR = {1953},
PAGES = {20--28},
LANGUAGE = {German},
REVIEW = {\MR{56575 (15,95d) 09.1X}},
}
Debo añadir que no he visto este papel. (Nunca he encontrado en internet, y no leo alemán de todos modos.) Sin embargo, la prueba no es difícil. Suponga que tiene un conjunto $S$ con cuatro elementos distintos $a$, $u$, $v$ y $w$. Definir la operación binaria $\cdot$ $S$ poniendo $a\cdot a = u$, $a\cdot u = v$, y $x\cdot y = w$, para todos los pares de $(x,y)$ otros de $(a,a)$$(a,u)$. Entonces es fácil ver que $(a\cdot a)\cdot a\neq a\cdot(a\cdot a)$. A continuación, es tedioso, pero completamente primaria para comprobar (caso por caso, si se quiere) que todos los otros triple no asociado.
MJD
Puntos
37705
En Rajagopalan y Schulman "Verificación de Identidades" (1997), un algoritmo que se da es que probabilísticamente se comprueba si una determinada operación $\circ$ sobre un conjunto $S$ es asociativa. Si la operación es no asociativo, la prueba detecta este hecho con cualquier probabilidad de $\delta$ en $$O(\kappa n^2\log\delta^{-1})$$ time, where $n=|S|$ and$\kappa$ is the time to calculate $\circ$ for one pair of arguments. A variant of the algorithm will generate a specific triple $\langle a,b,c\rangle$ for which $(a\circ b)\circ c\na\circ (b\circ c)$, when one exists, in time $$O(\kappa n^2\log n\log \delta^{-1}).$$
Este algoritmo funciona de la arbitrarias de las operaciones. A diferencia de la Luz de la prueba, funciona incluso para "noncancellative" de operaciones, donde las ecuaciones $x\circ a = b$ $a\circ x = b$ no tienen soluciones para todos los $a,b$.
El documento también muestra que si la operación $\circ$ es cancellative, uno puede calcular un pequeño ($O(\log n)$)establece que la genera en el tiempo $O(n^2)$, y, a continuación, aplicar la Luz de prueba para verificar de manera determinista asociatividad en el tiempo total $O(\kappa n^2\log n)$.
jmans
Puntos
3018
AngryHacker
Puntos
150
Un método para la estructuración de la comprobación de la asociatividad es la Luz de la asociatividad de la prueba. No mejora la velocidad del algoritmo (ni puede, como la respuesta de Santiago muestra), pero que debería hacer menos bizco.
Más sobre este tema puede encontrarse en esta respuesta.
Dimitri Wetzel
Puntos
117
Como alguien ya escribió, hay algunas pruebas que se pueden hacer (esta página de la wikipedia enlaces a la misma otras citado por @yatima2975).
Personalmente, estoy interesado en estas cuestiones, pero sólo yo sé las condiciones suficientes sobre la tabla de Cayley, la asociatividad.
Si puede ayudar, este es un simple borrador de la secuencia de comandos de Matlab para comprobar la asociatividad por la fuerza bruta (ver @James, la respuesta también):
disp('ASSOCIATIVITY TEST FOR A FINITE MAGMA OF ORDER n, WITH ELEMENTS 1,2,...,n, WHOSE CAYLEY TABLE IS GIVEN.');
n=input('Insert the order of the groupoid, n: ');
A=zeros(n);
for i=1:n
r=zeros(1,n);
r=input('Insert Cayley table line as [a_1,...,a_n]: ');
A(i,:)=r;
end
disp('The Cayley table is:');
disp(A);
B=zeros(n,n,n);
for i=1:n
for j=1:n
for k=1:n
if A(A(i,j),k)==A(i,A(j,k))
B(i,j,k)=1;
end
end
end
end
if B==ones(n,n,n)
disp('*** THIS MAGMA IS A SEMIGROUP ***');
else
disp('*** THIS MAGMA IS NOT A SEMIGROUP ***');
end
