Término álgebra

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. ${\displaystyle \tau }$ ${\displaystyle n}$ ${\displaystyle \tau _{n}}$ ${\displaystyle \tau }$ ${\displaystyle n}$

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: ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle T(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle T(X)}$

• ${\displaystyle X\cup \tau _{0}\subseteq T(X)}$   — cada símbolo variable de es un término en , al igual que cada símbolo constante de . ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle \tau _{0}}$
• 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. ${\displaystyle n\geq 1}$ ${\displaystyle f\in \tau _{n}}$ ${\displaystyle t_{1},...,t_{n}\in T(X)}$ ${\displaystyle f(t_{1},...,t_{n})\in T(X)}$ ${\displaystyle n}$ ${\displaystyle t_{1},...,t_{n}}$ ${\displaystyle n}$ ${\displaystyle f}$

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] ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle {\mathcal {T}}(X)}$

• El dominio de es . ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle T(X)}$
• Para cada función nula en , se define como la cadena . ${\displaystyle f}$ ${\displaystyle \tau _{0}}$ ${\displaystyle f^{{\mathcal {T}}(X)}()}$ ${\displaystyle f}$
• Para todas y para cada función n -aria y elementos del dominio, se define como la cadena . ${\displaystyle n\geq 1}$ ${\displaystyle f}$ ${\displaystyle \tau }$ ${\displaystyle t_{1},...,t_{n}}$ ${\displaystyle f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})}$ ${\displaystyle f(t_{1},...,t_{n})}$

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 : ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \tau }$ ${\displaystyle g:X\to {\mathcal {A}}}$ ${\displaystyle g}$ ${\displaystyle g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}}$ ${\displaystyle t\in {\mathcal {T}}(X)}$ ${\displaystyle g^{\ast }(t)\in {\mathcal {A}}}$ ${\displaystyle t\in {\mathcal {T}}(X)}$

• Si entonces . ${\displaystyle t\in X}$ ${\displaystyle g^{\ast }(t)=g(t)}$
• Si entonces . ${\displaystyle t=f\in \tau _{0}}$ ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}()}$
• Si dónde y , entonces . ${\displaystyle t=f(t_{1},...,t_{n})}$ ${\displaystyle f\in \tau _{n}}$ ${\displaystyle n\geq 1}$ ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))}$

Ejemplo

Como ejemplo, el tipo inspirado en la aritmética de enteros se puede definir mediante , , y para cada . ${\displaystyle \tau _{0}=\{0,1\}}$ ${\displaystyle \tau _{1}=\{\}}$ ${\displaystyle \tau _{2}=\{+,*\}}$ ${\displaystyle \tau _{i}=\{\}}$ ${\displaystyle i>2}$

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 . ${\displaystyle \tau }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle +}$ ${\displaystyle *}$ ${\displaystyle {\mathcal {A}}_{nat}}$

Para el conjunto de variables de ejemplo , vamos a investigar el término álgebra de tipo over . ${\displaystyle X=\{x,y\}}$ ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$

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 ${\displaystyle T(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$

• ${\displaystyle {\color {red}x}\in T(X)}$, ya que es un símbolo variable; ${\displaystyle x\in X}$
• ${\displaystyle {\color {red}1}\in T(X)}$, ya que es un símbolo constante; por eso ${\displaystyle 1\in \tau _{0}}$
• ${\displaystyle {\color {red}+x1}\in T(X)}$, ya que es un símbolo de función biaria; por lo tanto, a su vez, ${\displaystyle +}$
• ${\displaystyle {\color {red}*+x1x}\in T(X)}$puesto que es un símbolo de función biaria. ${\displaystyle *}$

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 . ${\displaystyle T(X)}$ ${\displaystyle {\color {red}*+x1x}}$ ${\displaystyle (x+1)*x}$ ${\displaystyle x+(1*x)}$ ${\displaystyle {\color {red}+x*1x}}$

Para dar algunos contraejemplos, tenemos, por ejemplo

• ${\displaystyle {\color {red}z}\not \in T(X)}$, ya que no es un símbolo variable admitido ni un símbolo constante admitido; ${\displaystyle z}$
• ${\displaystyle {\color {red}3}\not \in T(X)}$, por la misma razón,
• ${\displaystyle {\color {red}+1}\not \in T(X)}$, ya que es un símbolo de función biario, pero aquí se usa con un solo término argumento (a saber, ). ${\displaystyle +}$ ${\displaystyle {\color {red}1}}$

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. ${\displaystyle T(X)}$ ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle +^{{\mathcal {T}}(X)}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\color {red}+}pq}$ ${\displaystyle *^{{\mathcal {T}}(X)}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\color {red}*}pq}$ ${\displaystyle *^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})}$ ${\displaystyle {\color {red}*+x1x}}$ ${\displaystyle +^{{\mathcal {T}}(X)}}$ ${\displaystyle *^{{\mathcal {T}}(X)}}$

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, ${\displaystyle g:X\to {\mathcal {A}}_{nat}}$ ${\displaystyle g(x)=7}$ ${\displaystyle g(y)=3}$ ${\displaystyle g}$ ${\displaystyle T(X)}$ ${\displaystyle {\mathcal {A}}_{nat}}$

${\displaystyle {\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&g({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ coincides on }}X{\text{ with }}g\\=&7+g^{*}({\color {red}1})&{\text{ by definition of }}g\\=&7+1&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&8&{\text{ according to the well-known arithmetical rules in }}{\mathcal {A}}_{nat}\\\end{array}}}$

De manera similar se obtiene . ${\displaystyle g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56}$

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 ₁ , ...,  t _n ), donde t ₁ , ...,  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 ₁  =  t ₂ , donde t ₁ y t ₂ 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

• Programación de conjuntos de respuestas
• Clonar (álgebra)
• Dominio del discurso / Universo (matemáticas)
• Teorema del árbol de Rabin (la teoría monádica del árbol binario completo infinito es decidible)
• Álgebra inicial
• Tipo de datos abstractos
• Sistema de reescritura de términos

Referencias

1. Wilfrid Hodges (1997). Una teoría del modelo más corto . Prensa de la Universidad de Cambridge . págs.14. ISBN 0-521-58713-1.
2. Franz Baader ; Tobías Nipkow (1998). Reescritura de términos y todo eso. Prensa de la Universidad de Cambridge . pag. 49.ISBN​ 0-521-77920-0.
3. Klaus Denecke; Shelly L. Wismath (2009). Álgebra Universal y Coálgebra. Científico mundial . págs. 21-23. ISBN 978-981-283-745-5.
4. TH Tse (2010). Un marco unificador para modelos de diseño y análisis estructurados: un enfoque que utiliza la semántica de álgebra inicial y la teoría de categorías . Prensa de la Universidad de Cambridge . págs. 46–47. doi :10.1017/CBO9780511569890. ISBN 978-0-511-56989-0.
5. Jean-Yves Béziau (1999). "La estructura matemática de la sintaxis lógica". En Carnielli, Walter Alexandre; D'Ottaviano, Itala ML (eds.). Avances en lógica e informática contemporáneas: actas de la undécima conferencia brasileña sobre lógica matemática, 6 al 10 de mayo de 1996, Salvador, Bahía, Brasil . Sociedad Matemática Estadounidense . pag. 9.ISBN​ 978-0-8218-1364-5. Consultado el 18 de abril de 2011 .
6. Dirk van Dalen (2004). Lógica y Estructura. Saltador . pag. 108.ISBN​ 978-3-540-20879-2.
7. M. Ben-Ari (2001). Lógica Matemática para la Informática. Saltador . págs. 148-150. ISBN 978-1-85233-319-5.
8. Monroe recién nacido (2001). Demostración automatizada de teoremas: teoría y práctica. Saltador . pag. 43.ISBN​ 978-0-387-95075-4.
9. Stanley Burris; HP Sankappanavar (1981). Un curso de álgebra universal. Saltador. págs. 68–69, 71. ISBN 978-1-4613-8132-7.{{cite book}}: CS1 maint: multiple names: authors list (link)
10. Rogelio Dávila. Descripción general de la programación del conjunto de respuestas.
11. Juana Ferrante; Charles W. Rackoff (1979). La complejidad computacional de las teorías lógicas . Springer , Capítulo 8, Teorema 1.2.

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

• Weisstein, Eric W. "Universo Herbrand". MundoMatemático .