Firma (lógica)

Descripción de símbolos no lógicos.

En lógica , especialmente en lógica matemática , una firma enumera y describe los símbolos no lógicos de un lenguaje formal . En álgebra universal , una firma enumera las operaciones que caracterizan una estructura algebraica . En teoría de modelos , las firmas se utilizan para ambos propósitos. Rara vez se hacen explícitos en tratamientos más filosóficos de la lógica.

Definición

Formalmente, una firma (de orden único) se puede definir como una tupla de 4 donde y son conjuntos disjuntos que no contienen ningún otro símbolo lógico básico, llamados respectivamente ${\displaystyle \sigma =\left(S_{\operatorname {func} },S_{\operatorname {rel} },S_{\operatorname {const} },\operatorname {ar} \right),}$ ${\displaystyle S_{\operatorname {func} }}$ ${\displaystyle S_{\operatorname {rel} }}$

• símbolos de función (ejemplos:), ${\displaystyle +,\times }$
• símbolo de relación o predicados (ejemplos:), ${\displaystyle \,\leq ,\,\in }$
• símbolos constantes (ejemplos:), ${\displaystyle 0,1}$

y una función que asigna un número natural llamado aridad a cada función o símbolo de relación. Un símbolo de función o relación se llama -ario si su aridad es. Algunos autores definen un símbolo de función nula (-ario) como símbolo constante ; de ​​lo contrario, los símbolos constantes se definen por separado. ${\displaystyle \operatorname {ar} :S_{\operatorname {func} }\cup S_{\operatorname {rel} }\to \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle n.}$ ${\displaystyle 0}$

Una firma sin símbolos de función se llamafirma relacional , y una firma sin símbolos de relación se llama firmafirma algebraica . ^[1]Unfirma finita es una firma tal queysonfinitos. De manera más general, lacardinalidadde una firmase define como ${\displaystyle S_{\operatorname {func} }}$ ${\displaystyle S_{\operatorname {rel} }}$ ${\displaystyle \sigma =\left(S_{\operatorname {func} },S_{\operatorname {rel} },S_{\operatorname {const} },\operatorname {ar} \right)}$ ${\displaystyle |\sigma |=\left|S_{\operatorname {func} }\right|+\left|S_{\operatorname {rel} }\right|+\left|S_{\operatorname {const} }\right|.}$

ElEl lenguaje de una firma es el conjunto de todas las oraciones bien formadas construidas a partir de los símbolos de esa firma junto con los símbolos del sistema lógico.

Otras convenciones

En álgebra universal la palabratipo oEl tipo de similitud se utiliza a menudo como sinónimo de "firma". En la teoría de modelos, una firmaa menudo se denomina ${\displaystyle \sigma }$vocabulario , o identificado con ellenguaje (de primer orden) al que proporciona lossímbolos no lógicos. Sin embargo, lacardinalidaddel lenguajesiempre será infinita; sies finito entonceslo será. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle \sigma }$ ${\displaystyle |L|}$ ${\displaystyle \aleph _{0}}$

Como la definición formal es inconveniente para el uso diario, la definición de una firma específica a menudo se abrevia de manera informal, como en:

"La firma estándar para grupos abelianos es donde hay un operador unario". ${\displaystyle \sigma =(+,-,0),}$ ${\displaystyle -}$

A veces, una firma algebraica se considera simplemente una lista de aridades, como en:

"El tipo de similitud para los grupos abelianos es " ${\displaystyle \sigma =(2,1,0).}$

Formalmente, esto definiría los símbolos de función de la firma como algo así como (que es binario), (que es unario) y (que es nulo), pero en realidad los nombres habituales se utilizan incluso en relación con esta convención. ${\displaystyle f_{0}}$ ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$

En lógica matemática , muy a menudo no se permite que los símbolos sean nulos, ^{[ cita necesaria ]} por lo que los símbolos constantes deben tratarse por separado en lugar de como símbolos de funciones nulas. Forman un conjunto disjunto a partir del cual la función de aridad no está definida. Sin embargo, esto sólo sirve para complicar las cosas, especialmente en demostraciones por inducción sobre la estructura de una fórmula, donde se debe considerar un caso adicional. Cualquier símbolo de relación nula, que tampoco está permitido según dicha definición, puede emularse mediante un símbolo de relación unario junto con una oración que exprese que su valor es el mismo para todos los elementos. Esta traducción falla sólo para estructuras vacías (que a menudo están excluidas por convención). Si se permiten símbolos nulares, entonces toda fórmula de lógica proposicional es también una fórmula de lógica de primer orden . ${\displaystyle S_{\operatorname {const} }}$ ${\displaystyle S_{\operatorname {func} },}$ ${\displaystyle \operatorname {ar} }$

Un ejemplo de una firma infinita utiliza y para formalizar expresiones y ecuaciones sobre un espacio vectorial sobre un campo escalar infinito donde cada una denota la operación unaria de multiplicación escalar por De esta manera, la firma y la lógica se pueden mantener ordenadas de forma única, siendo los vectores el único tipo. ^[2] ${\displaystyle S_{\operatorname {func} }=\{+\}\cup \left\{f_{a}:a\in F\right\}}$ ${\displaystyle S_{\operatorname {rel} }=\{=\}}$ ${\displaystyle F,}$ ${\displaystyle f_{a}}$ ${\displaystyle a.}$

Uso de firmas en lógica y álgebra.

En el contexto de la lógica de primer orden , los símbolos de una firma también se conocen como símbolos no lógicos , porque junto con los símbolos lógicos forman el alfabeto subyacente sobre el cual se definen inductivamente dos lenguajes formales : El conjunto de términos sobre el firma y el conjunto de fórmulas (bien formadas) sobre la firma.

En una estructura , una interpretación vincula los símbolos de función y relación a objetos matemáticos que justifican sus nombres: La interpretación de un símbolo de función aria en una estructura con dominio es una función y la interpretación de un símbolo de relación aria es una relación Aquí denota el producto cartesiano del dominio consigo mismo, por lo que es de hecho una función aria y una relación aria. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle A}$ ${\displaystyle f^{\mathbf {A} }:A^{n}\to A,}$ ${\displaystyle n}$ ${\displaystyle R^{\mathbf {A} }\subseteq A^{n}.}$ ${\displaystyle A^{n}=A\times A\times \cdots \times A}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle n}$

Firmas variadas

Para lógica de muchos tipos y para estructuras de muchos tipos , las firmas deben codificar información sobre los tipos. La forma más sencilla de hacerlo es a través detipos de símbolos que desempeñan el papel de aridades generalizadas. ^[3]

Tipos de símbolos

Sea un conjunto (de algún tipo) que no contenga los símbolos o ${\displaystyle S}$ ${\displaystyle \times }$ ${\displaystyle \to .}$

Los tipos de símbolos anteriores son ciertas palabras del alfabeto : los tipos de símbolos relacionales y los tipos de símbolos funcionales para números enteros no negativos y (ya que la expresión denota la palabra vacía). ${\displaystyle S}$ ${\displaystyle S\cup \{\times ,\to \}}$ ${\displaystyle s_{1}\times \cdots \times s_{n},}$ ${\displaystyle s_{1}\times \cdots \times s_{n}\to s^{\prime },}$ ${\displaystyle n}$ ${\displaystyle s_{1},s_{2},\ldots ,s_{n},s^{\prime }\in S.}$ ${\displaystyle n=0,}$ ${\displaystyle s_{1}\times \cdots \times s_{n}}$

Firma

Una firma (multiclasificada) es una tripleta que consta de ${\displaystyle (S,P,\operatorname {type} )}$

• un conjunto de tipos, ${\displaystyle S}$
• un conjunto de símbolos y ${\displaystyle P}$
• un mapa que asocia a cada símbolo en un tipo de símbolo sobre ${\displaystyle \operatorname {type} }$ ${\displaystyle P}$ ${\displaystyle S.}$

Ver también

• Álgebra de términos  : estructura algebraica generada libremente sobre una firma determinada

Notas

1. Mokadem, Riad; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (septiembre de 2007). "Búsqueda rápida de cadenas basada en nGram sobre datos codificados mediante firmas algebraicas" (PDF) . 33ª Conferencia Internacional sobre Bases de Datos de Muy Gran Tamaño (VLDB) . Consultado el 27 de febrero de 2019 .
2. George Grätzer (1967). "IV. Álgebra Universal". En James C. Abbot (ed.). Tendencias en la teoría de la red . Princeton/Nueva Jersey: Van Nostrand. págs. 173-210.Aquí: p.173.
3. Lógica variada, primer capítulo de Apuntes de conferencias sobre procedimientos de decisión, escrito por Calogero G. Zarba.

Referencias

• Burris, Stanley N.; Sankappanavar, HP (1981). Un curso de álgebra universal . Saltador . ISBN 3-540-90578-2.Edición en línea gratuita.
• Hodges, Wilfrid (1997). Una teoría del modelo más corto . Prensa de la Universidad de Cambridge . ISBN 0-521-58713-1.

enlaces externos

• Enciclopedia de Filosofía de Stanford: "Teoría de modelos", por Wilfred Hodges .
• PlanetMath: La entrada "Firma" describe el concepto para el caso en el que no se introducen tipos.
• Baillie, Jean, "Introducción a la especificación algebraica de tipos de datos abstractos".