Firma (lógica)

Descripción de símbolos no lógicos

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

Definición

Formalmente, una firma (de ordenación simple) 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ímbolos 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 símbolo de función o 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 nulario ( -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 llamafirma algebraica .^[1]ALa firma 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 el álgebra universal la palabratipo oEl tipo de similitud se utiliza a menudo como sinónimo de "firma". En la teoría de modelos, una firmase suele denominar ${\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 entoncesserá. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle \sigma }$ ${\displaystyle |L|}$ ${\displaystyle \aleph _{0}}$

Como la definición formal resulta incómoda para el uso cotidiano, la definición de una firma específica suele abreviarse de manera informal, como en:

"La firma estándar para los grupos abelianos es donde es 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 usuales se usan incluso en conexió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 requerida ]} por lo que los símbolos constantes deben tratarse por separado en lugar de como símbolos de función nulos. Forman un conjunto disjunto del cual no está definida la función aridad . Sin embargo, esto solo sirve para complicar las cosas, especialmente en demostraciones por inducción sobre la estructura de una fórmula, donde debe considerarse un caso adicional. Cualquier símbolo de relación nula, que tampoco está permitido bajo tal definición, puede ser emulado por un símbolo de relación unaria junto con una oración que exprese que su valor es el mismo para todos los elementos. Esta traducción falla solo para estructuras vacías (que a menudo se excluyen por convención). Si se permiten los símbolos nulos, entonces cada 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 uno 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 simple, siendo los vectores la única clasificación. ^[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 la 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 -ario en una estructura con dominio es una función y la interpretación de un símbolo de relación -ario es una relación Aquí denota el producto cartesiano del dominio consigo mismo, y por lo tanto es, de hecho, una función -ario y una relación -ario. ${\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 de múltiples tipos

Para la lógica multiordenada y para las estructuras multiordenadas , las firmas deben codificar información sobre las ordenaciones. La forma más sencilla de hacerlo es mediantetipos 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 contiene 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 (multiordenada) es un triple que consta de ${\displaystyle (S,P,\operatorname {type} )}$

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

Véase también

• Álgebra de términos  : Estructura algebraica generada libremente sobre una firma dada

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 muy grandes (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 retículos . Princeton/Nueva Jersey: Van Nostrand. págs. 173–210.Aquí: p.173.
3. Lógica de múltiples ordenamientos, primer capítulo de Apuntes sobre procedimientos de decisión, escrito por Calogero G. Zarba.

Referencias

• Burris, Stanley N.; Sankappanavar, HP (1981). Un curso de álgebra universal . Springer . ISBN. 3-540-90578-2.Edición gratuita en línea.
• Hodges, Wilfrid (1997). Una teoría de modelos más breve . Cambridge University Press . 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 clasificaciones.
• Baillie, Jean, "Introducción a la especificación algebraica de tipos de datos abstractos".