Me pregunto cuán difícil puede ser la prueba de identidad (similar a la prueba de identidad de polinomios) para un álgebra libre . Pensé que, en cierto sentido, el problema debía ser siempre semidecidible porque el álgebra libre se define con respecto a las identidades que se desprenden del conjunto de axiomas ecuacionales dados. Entonces, ¿cómo tengo que interpretar la siguiente afirmación de Teoría de Horn ecuacional y universal de retículos modulares :
La red modular libre sobre 4 o más generadores tiene un problema de palabras sin solución.
¿Están hablando del mismo problema de pruebas de identidad que me interesa? ¿Utilizan "irresoluble" en lugar de "semidecidible", porque la semidecidibilidad obviamente ya forma parte de la definición? O bien irresoluble generalmente sólo significa que una de las dos direcciones no es decidible?
0 votos
Problema de palabras irresoluble significa indecidible. Pero una red modular libre está muy lejos de ser libre algebraicamente.
0 votos
Todas las álgebras definidas por una presentación están definidas por las identidades que se derivan de las relaciones. La decidibilidad del problema de la palabra tiene que ver con poder encontrar ciertas ecuaciones algorítmicamente, no con que existan. En ese sentido, el problema de la palabra es siempre decidible, excepto que puede ser independiente de los axiomas (lo que generalmente es) y nadie entiende realmente lo que ocurre en ese caso.
1 votos
@MattSamuel ¿Por qué quieres decir que una red modular libre está muy lejos de ser libre algebraicamente? Parece que se ajusta exactamente a la definición de una álgebra libre . No parece permitirse ningún conjunto de relaciones además de los axiomas ecuacionales, por lo que parece bastante más restringido que un álgebra presentada por un conjunto de generadores y relaciones. (En cuyo caso se permitiría que las relaciones nombraran explícitamente un generador específico, mientras que los axiomas ecuacionales sólo contienen variables universales cuantificadas sin ninguna referencia a los generadores).
1 votos
Los "axiomas ecuacionales" son relaciones. No desaparecen porque todas las álgebras del tipo las satisfacen.
0 votos
@MattSamuel Lo he pensado un poco más y he llegado a la conclusión de que los axiomas ecuacionales y las relaciones son cosas completamente diferentes. Si $a,b,c$ son sus generadores, entonces una relación es una ecuación entre $a,b,c$ que no contiene ninguna variable libre (=variable universalmente cuantificada). Un axioma ecuacional, en cambio, es una ecuación entre variables libres que no contiene ningún generador.
0 votos
Contiene cualquier elemento, que incluye los generadores y más.
0 votos
@MattSamuel En el contexto de la problema de palabras para grupos Se habla de presentación de un grupo lo que significa que un grupo está dado por un conjunto de generadores y un conjunto de relaciones entre esos generadores. En este contexto, no se permite que una relación contenga variables libres. Por lo tanto, podría haber un algoritmo de tiempo polinómico para decidir el problema de palabras para los entramados (incluyendo las relaciones), aunque el problema de palabras para los entramados modulares libres es irresoluble.
0 votos
Para el ordenador, cada elemento es un generador de un álgebra sin axiomas y las relaciones son los axiomas ecuacionales, en los que sólo hay que introducir cada combinación de elementos. Un ordenador parte de la estructura más básica y no considera las variables libres como un concepto especial. Cuando te pones a ello, hay elementos y hay elementos, y no puedes calcular sin referirte a elementos. Si lo ves de otra manera señalando ciertas relaciones como "axiomas" no cambia la computabilidad porque...
0 votos
...la palabra problema no tiene sentido si no se especializa con elementos reales.