Estructura algebraica generada libremente sobre una firma determinada
En álgebra universal y lógica matemática , un término álgebra es una estructura algebraica generada libremente sobre una firma determinada . [1] [2] Por ejemplo, en una firma que consta de una única operación binaria , el término álgebra sobre un conjunto X de variables es exactamente el magma libre generado por X. Otros sinónimos de la noción incluyen álgebra absolutamente libre y álgebra anárquica . [3]
Desde la perspectiva de la teoría de categorías , un término álgebra es el objeto inicial para la categoría de todas las álgebras generadas en X de la misma firma , y este objeto, único hasta el isomorfismo , se llama álgebra inicial ; genera por proyección homomórfica todas las álgebras de la categoría. [4] [5]
Una noción similar es la de un universo de Herbrand en lógica , habitualmente utilizado con este nombre en programación lógica , [6] que se define (con absoluta libertad) a partir del conjunto de constantes y símbolos de función en un conjunto de cláusulas . Es decir, el universo de Herbrand consta de todos los términos fundamentales : términos que no contienen variables.
Una fórmula atómica o átomo se define comúnmente como un predicado aplicado a una tupla de términos; un átomo fundamental es entonces un predicado en el que sólo aparecen términos fundamentales. La base de Herbrand es el conjunto de todos los átomos fundamentales que pueden formarse a partir de símbolos de predicados en el conjunto original de cláusulas y términos en su universo de Herbrand. [7] [8] Estos dos conceptos llevan el nombre de Jacques Herbrand .
Los términos álgebras también desempeñan un papel en la semántica de los tipos de datos abstractos , donde una declaración de tipo de datos abstractos proporciona la firma de una estructura algebraica de orden múltiple y el término álgebra es un modelo concreto de la declaración abstracta.
álgebra universal
Un tipo es un conjunto de símbolos de función, cada uno de los cuales tiene una aridad asociada (es decir, número de entradas). Para cualquier número entero no negativo , denotemos los símbolos de función en aridad . Una constante es un símbolo de función de aridad 0.
Sea un tipo y sea un conjunto de símbolos no vacío, que representa los símbolos variables. (Para simplificar, supongamos que y son disjuntos). Entonces, el conjunto de términos de tipo over es el conjunto de todas las cadenas bien formadas que se pueden construir utilizando los símbolos variables de y las constantes y operaciones de . Formalmente, el conjunto más pequeño es tal que:
- — cada símbolo variable de es un término en , al igual que cada símbolo constante de .
- Para todos y para todos los símbolos y términos de función , tenemos la cadena : términos dados , la aplicación de un símbolo de función aria representa nuevamente un término.
El término álgebra de tipo over es, en resumen, el álgebra de tipo que asigna cada expresión a su representación de cadena. Formalmente, se define de la siguiente manera: [9]
- El dominio de es .
- Para cada función nula en , se define como la cadena .
- Para todas y para cada función n -aria y elementos del dominio, se define como la cadena .
Un término de álgebra se llama absolutamente libre porque para cualquier álgebra de tipo , y para cualquier función , se extiende a un homomorfismo único , que simplemente evalúa cada término a su valor correspondiente . Formalmente, para cada uno :
- Si entonces .
- Si entonces .
- Si dónde y , entonces .
Ejemplo
Como ejemplo, el tipo inspirado en la aritmética de enteros se puede definir mediante , , y para cada .
El álgebra de tipo más conocida tiene los números naturales como dominio e interpreta , , y de la forma habitual; nos referimos a él como .
Para el conjunto de variables de ejemplo , vamos a investigar el término álgebra de tipo over .
En primer lugar, se considera el conjunto de términos de tipo over . Usamos el color rojo para señalar a sus miembros, que de otro modo podrían ser difíciles de reconocer debido a su forma sintáctica poco común. tenemos por ejemplo
- , ya que es un símbolo variable;
- , ya que es un símbolo constante; por eso
- , ya que es un símbolo de función biaria; por lo tanto, a su vez,
- puesto que es un símbolo de función biaria.
De manera más general, cada cadena corresponde a una expresión matemática construida a partir de los símbolos admitidos y escrita en notación de prefijo polaca ; por ejemplo, el término corresponde a la expresión en notación infija habitual . No se necesitan paréntesis para evitar ambigüedades en la notación polaca; por ejemplo, la expresión infija corresponde al término .
Para dar algunos contraejemplos, tenemos, por ejemplo
- , ya que no es un símbolo variable admitido ni un símbolo constante admitido;
- , por la misma razón,
- , ya que es un símbolo de función biario, pero aquí se usa con un solo término argumento (a saber, ).
Ahora que el conjunto de términos está establecido, consideramos el término álgebra de tipo sobre . Esta álgebra utiliza como dominio el cual es necesario definir la suma y la multiplicación. La función de suma toma dos términos y devuelve el término ; de manera similar, la función de multiplicación asigna términos dados y al término . Por ejemplo, se evalúa como el término . Informalmente, las operaciones y son "perezosas" en el sentido de que simplemente registran qué cálculo se debe hacer, en lugar de hacerlo.
Como ejemplo de extensibilidad única de un homomorfismo, considere definido por y . De manera informal, define una asignación de valores a símbolos de variables y, una vez hecho esto, cada término de se puede evaluar de una manera única en . Por ejemplo,
De manera similar se obtiene .
base de herbrand
La firma σ de un lenguaje es una triple < O , F , P > que consta del alfabeto de constantes O , símbolos de función F y predicados P . La base de Herbrand [10] de una firma σ consta de todos los átomos fundamentales de σ : de todas las fórmulas de la forma R ( t 1 , ..., t n ), donde t 1 , ..., t n son términos que contienen no hay variables (es decir, elementos del universo Herbrand) y R es un símbolo de relación n -aria ( es decir, predicado ). En el caso de la lógica con igualdad, también contiene todas las ecuaciones de la forma t 1 = t 2 , donde t 1 y t 2 no contienen variables.
Decidibilidad
Se puede demostrar que las álgebras de términos son decidibles mediante la eliminación de cuantificadores . La complejidad del problema de decisión es NO ELEMENTAL porque los constructores binarios son funciones inyectivas y, por tanto, de emparejamiento. [11]
Ver también
Referencias
Otras lecturas
- Joel Berman (2005). "La estructura de las álgebras libres". En Teoría estructural de autómatas, semigrupos y álgebra universal . Saltador . págs. 47–76. SEÑOR 2210125.
enlaces externos