Estructura (lógica matemática)

El dominio de una estructura es un conjunto arbitrario; también se le llama conjunto subyacente de la estructura, su portador (especialmente en álgebra universal), su universo (especialmente en teoría de modelos, cf. universo ) o su dominio de discurso . En la lógica clásica de primer orden, la definición de una estructura prohíbe el dominio vacío . ^{[ 6 ]}

A veces la notación${\displaystyle \operatorname {dom} ({\mathcal {A}})}$o${\displaystyle |{\mathcal {A}}|}$se utiliza para el dominio de${\displaystyle {\mathcal {A}},}$pero a menudo no se hace ninguna distinción notacional entre una estructura y su dominio (es decir, el mismo símbolo)${\displaystyle {\mathcal {A}}}$se refiere tanto a la estructura como a su dominio.) ^{[ 7 ]}

La firma${\displaystyle \sigma =(S,\operatorname {ar} )}$Una estructura consta de:

• un conjunto${\displaystyle S}$de símbolos de función y símbolos de relación , junto con
• una función${\displaystyle \operatorname {ar}$ :\ S\to \mathbb {N} _{0}} que se atribuye a cada símbolo${\displaystyle s}$un número natural${\displaystyle n=\operatorname {ar} (s).}$

El número natural${\displaystyle n=\operatorname {ar} (s)}$de un símbolo${\displaystyle s}$se llama la aridad de${\displaystyle s}$porque es la aridad de la interpretación de${\displaystyle s.}$

Dado que las signaturas que surgen en álgebra a menudo contienen solo símbolos de función, una signatura sin símbolos de relación se denomina signatura algebraica . Una estructura con dicha signatura también se denomina álgebra ; esto no debe confundirse con la noción de álgebra sobre un cuerpo .

La función de interpretación${\displaystyle I}$de${\displaystyle {\mathcal {A}}}$Asigna funciones y relaciones a los símbolos de la firma. A cada símbolo de función${\displaystyle f}$de aridad${\displaystyle n}$se le asigna un${\displaystyle n}$función -aria${\displaystyle f^{\mathcal {A}}=I(f)}$en el dominio. Cada símbolo de relación${\displaystyle R}$de aridad${\displaystyle n}$se le asigna un${\displaystyle n}$relación -aria${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$en el dominio. Un nulo (${\displaystyle =\,0}$-ario) símbolo de función${\displaystyle c}$se denomina símbolo constante , porque su interpretación${\displaystyle I(c)}$puede identificarse con un elemento constante del dominio.

Cuando una estructura (y por lo tanto una función de interpretación) viene dada por el contexto, no se hace ninguna distinción notacional entre un símbolo${\displaystyle s}$y su interpretación${\displaystyle I(s).}$Por ejemplo, si${\displaystyle f}$es un símbolo de función binaria de${\displaystyle {\mathcal {A}},}$uno simplemente escribe${\displaystyle f:{\mathcal {A}}^{2}\to {\mathcal {A}}}$en vez de${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\to |{\mathcal {A}}|.}$

La firma estándar${\displaystyle \sigma _{f}}$para campos consta de dos símbolos de función binaria${\displaystyle \mathbf {+} }$y${\displaystyle \mathbf {\times } }$donde se pueden derivar símbolos adicionales, como un símbolo de función unaria${\displaystyle \mathbf {-} }$(determinado de forma única por${\displaystyle \mathbf {+} }$) y los dos símbolos constantes${\displaystyle \mathbf {0} }$y${\displaystyle \mathbf {1} }$(determinado de forma única por${\displaystyle \mathbf {+} }$y${\displaystyle \mathbf {\times } }$respectivamente). Por lo tanto, una estructura (álgebra) para esta signatura consiste en un conjunto de elementos${\displaystyle A}$junto con dos funciones binarias, que pueden ampliarse con una función unaria, y dos elementos distinguidos; pero no hay ningún requisito de que satisfaga ninguno de los axiomas del campo. Los números racionales${\displaystyle \mathbb {Q} ,}$los números reales${\displaystyle \mathbb {R} }$y los números complejos${\displaystyle \mathbb {C} ,}$como cualquier otro campo, puede ser considerado como${\displaystyle \sigma }$-estructuras de forma obvia: $${\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}$$

En los tres casos tenemos la firma estándar dada por $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ con ^{[ 8 ]}${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$y $${\displaystyle {\begin{alignedat}{3}\operatorname {ar} _{f}&(+)&&=2,\\\operatorname {ar} _{f}&(\times )&&=2,\\\operatorname {ar} _{f}&(-)&&=1,\\\operatorname {ar} _{f}&(0)&&=0,\\\operatorname {ar} _{f}&(1)&&=0.\\\end{alignedat}}}$$

La función de interpretación${\displaystyle I_{\mathcal {Q}}}$es:

${\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$es la suma de números racionales,

${\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$es la multiplicación de números racionales,

${\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} }$es la función que toma cada número racional${\displaystyle x}$a${\displaystyle -x,}$y

${\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} }$es el número${\displaystyle 0,}$y

${\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} }$es el número${\displaystyle 1;}$

y${\displaystyle I_{\mathcal {R}}}$y${\displaystyle I_{\mathcal {C}}}$se definen de manera similar. ^{[ 8 ]}

Pero el anillo${\displaystyle \mathbb {Z} }$de enteros , que no es un campo, también es un${\displaystyle \sigma _{f}}$-estructura de la misma manera. De hecho, no hay ningún requisito de que se cumplan todos los axiomas de campo en un${\displaystyle \sigma _{f}}$-estructura.

Una firma para campos ordenados necesita una relación binaria adicional como por ejemplo:${\displaystyle \,<\,}$o${\displaystyle \,\leq ,\,}$y por lo tanto las estructuras para dicha signatura no son álgebras, aunque por supuesto son estructuras algebraicas en el sentido habitual y amplio de la palabra.

La signatura ordinaria para la teoría de conjuntos incluye una única relación binaria.${\displaystyle \in .}$ Una estructura para esta firma consta de un conjunto de elementos y una interpretación de la misma.${\displaystyle \in }$relación como una relación binaria sobre estos elementos.

Dejar${\displaystyle \sigma =\{+,\times ,-,0,1\}}$volver a ser la firma estándar para campos. Cuando se considera como${\displaystyle \sigma }$En cuanto a las estructuras naturales, los números racionales forman una subestructura de los números reales , y los números reales forman una subestructura de los números complejos . Los números racionales son la subestructura más pequeña de los números reales (o complejos) que también satisface los axiomas del campo.

El conjunto de los enteros proporciona una subestructura aún más pequeña de los números reales que no es un cuerpo. De hecho, los enteros son la subestructura de los números reales generada por el conjunto vacío, utilizando esta signatura. La noción en álgebra abstracta que corresponde a una subestructura de un cuerpo, en esta signatura, es la de un subanillo , en lugar de la de un subcuerpo .

La forma más obvia de definir un grafo es una estructura con una firma.${\displaystyle \sigma }$que consta de un único símbolo de relación binaria${\displaystyle E.}$Los vértices del grafo forman el dominio de la estructura, y para dos vértices${\displaystyle a}$y${\displaystyle b,}$${\displaystyle (a,b)\!\in {\text{E}}}$significa que${\displaystyle a}$y${\displaystyle b}$están conectados por una arista. En esta codificación, la noción de subestructura inducida es más restrictiva que la noción de subgrafo . Por ejemplo, sea${\displaystyle G}$Sea un grafo que consta de dos vértices conectados por una arista, y sea${\displaystyle H}$sea ​​el grafo que consta de los mismos vértices pero sin aristas.${\displaystyle H}$es un subgrafo de${\displaystyle G,}$pero no una subestructura inducida. La noción en teoría de grafos que corresponde a las subestructuras inducidas es la de subgrafos inducidos .

Dadas dos estructuras${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$de la misma signatura σ, un (σ-)homomorfismo de${\displaystyle {\mathcal {A}}}$a${\displaystyle {\mathcal {B}}}$es un mapa${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$que preserva las funciones y las relaciones. Más precisamente:

• Para cada símbolo de función n -aria f de σ y cualquier elemento${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$Se cumple la siguiente ecuación:

${\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))}$.

• Para cada símbolo de relación n -aria R de σ y cualquier elemento${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$Se cumple la siguiente implicación:

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

dónde${\displaystyle R^{\mathcal {A}}}$,${\displaystyle R^{\mathcal {B}}}$es la interpretación del símbolo de relación${\displaystyle R}$en la estructura${\displaystyle {\mathcal {A}}}$,${\displaystyle {\mathcal {B}}}$respectivamente.

Un homomorfismo h de${\displaystyle {\mathcal {A}}}$a${\displaystyle {\mathcal {B}}}$se suele denotar como${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$, aunque técnicamente la función h está entre los dominios${\displaystyle |{\mathcal {A}}|}$,${\displaystyle |{\mathcal {B}}|}$de las dos estructuras${\displaystyle {\mathcal {A}}}$,${\displaystyle {\mathcal {B}}}$.

Para cada signatura σ hay una categoría concreta σ- Hom que tiene σ-estructuras como objetos y σ-homomorfismos como morfismos .

Un homomorfismo${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$A veces se le llama homomorfismo fuerte si también se cumple la implicación inversa anterior. Más precisamente:

• Para cada símbolo de relación n -aria R de σ y cualquier elemento${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$de tal manera que${\displaystyle (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$, entonces hay${\displaystyle a_{1}',a_{2}',\dots ,a_{n}'\in |{\mathcal {A}}|}$de tal manera que${\displaystyle (a_{1}',a_{2}',\dots ,a_{n}')\in R^{\mathcal {A}}}$y${\displaystyle h(a_{1}')=h(a_{1}),\,h(a_{2}')=h(a_{2}),\,\dots ,\,h(a_{n}')=h(a_{n}).}$^{[ 9 ]}

Los homomorfismos fuertes dan lugar a una subcategoría de la categoría σ- Hom que se definió anteriormente.

Un (σ-)homomorfismo${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$se denomina incrustación (σ-) si es inyectiva y

• para cada símbolo de relación n -aria R de σ y cualquier elemento${\displaystyle a_{1},a_{2},\dots ,a_{n}}$Se cumple la siguiente equivalencia:

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

(dónde${\displaystyle R^{\mathcal {A}}}$,${\displaystyle R^{\mathcal {B}}}$es la interpretación del símbolo de relación${\displaystyle R}$en la estructura${\displaystyle {\mathcal {A}}}$,${\displaystyle {\mathcal {B}}}$respectivamente).

Así, una incrustación es lo mismo que un homomorfismo fuerte que es inyectivo. La categoría σ- Emb de σ-estructuras e σ-incrustaciones es una subcategoría concreta de σ- Hom .

Las subestructuras inducidas corresponden a subobjetos en σ- Emb . Si σ solo tiene símbolos de función, σ- Emb es la subcategoría de monomorfismos de σ- Hom . En este caso, las subestructuras inducidas también corresponden a subobjetos en σ- Hom .

Como se ha visto anteriormente, en la codificación estándar de grafos como estructuras, las subestructuras inducidas son precisamente los subgrafos inducidos. Sin embargo, un homomorfismo entre grafos es lo mismo que un homomorfismo entre las dos estructuras que codifican el grafo. En el ejemplo de la sección anterior, aunque el subgrafo H de G no es inducido, la aplicación identidad id: H → G es un homomorfismo. Esta aplicación es, de hecho, un monomorfismo en la categoría σ- Hom , y por lo tanto H es un subobjeto de G que no es una subestructura inducida.   

El siguiente problema se conoce como el problema del homomorfismo :

Dadas dos estructuras finitas${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$de una signatura relacional finita, encontrar un homomorfismo${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$o demostrar que no existe tal homomorfismo.

Cada problema de satisfacción de restricciones (CSP) tiene una traducción al problema de homomorfismo. ^{[ 10 ]} Por lo tanto, la complejidad de CSP puede estudiarse utilizando los métodos de la teoría de modelos finitos .

Otra aplicación se encuentra en la teoría de bases de datos , donde un modelo relacional de una base de datos es esencialmente lo mismo que una estructura relacional. Resulta que una consulta conjuntiva sobre una base de datos puede describirse mediante otra estructura con la misma signatura que el modelo de base de datos. Un homomorfismo del modelo relacional a la estructura que representa la consulta es lo mismo que una solución a la consulta. Esto demuestra que el problema de la consulta conjuntiva también es equivalente al problema del homomorfismo.

Cada estructura de primer orden${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$tiene una relación de satisfacción${\displaystyle {\mathcal {M}}\vDash \phi }$definido para todas las fórmulas${\displaystyle \,\phi }$ en el idioma que consiste en el idioma de${\displaystyle {\mathcal {M}}}$junto con un símbolo constante para cada elemento de${\displaystyle M,}$que se interpreta como ese elemento. Esta relación se define inductivamente utilizando el esquema T de Tarski .

Una estructura${\displaystyle {\mathcal {M}}}$Se dice que es un modelo de una teoría${\displaystyle T}$si el idioma de${\displaystyle {\mathcal {M}}}$es lo mismo que el idioma de${\displaystyle T}$y cada frase en${\displaystyle T}$está satisfecho por${\displaystyle {\mathcal {M}}.}$Así, por ejemplo, un "anillo" es una estructura para el lenguaje de anillos que satisface cada uno de los axiomas de anillos, y un modelo de teoría de conjuntos ZFC es una estructura en el lenguaje de la teoría de conjuntos que satisface cada uno de los axiomas ZFC.

Un${\displaystyle n}$relación -aria${\displaystyle R}$en el universo (es decir, el dominio)${\displaystyle M}$de la estructura${\displaystyle {\mathcal {M}}}$Se dice que es definible (o explícitamente definible, cf. definibilidad de Beth , o${\displaystyle \emptyset }$- definible , o definible con parámetros de${\displaystyle \emptyset }$(véase más abajo) si hay una fórmula${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$de tal manera que $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$ En otras palabras,${\displaystyle R}$es definible si y solo si existe una fórmula${\displaystyle \varphi }$de tal manera que $${\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}$$ es correcto.

Un caso especial importante es la definibilidad de elementos específicos. Un elemento${\displaystyle m}$de${\displaystyle M}$es definible en${\displaystyle {\mathcal {M}}}$si y solo si existe una fórmula${\displaystyle \varphi (x)}$de tal manera que $${\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}$$

Tanto el álgebra universal como la teoría de modelos estudian clases de (estructuras o) álgebras que se definen mediante una signatura y un conjunto de axiomas. En el caso de la teoría de modelos, estos axiomas tienen la forma de enunciados de primer orden. El formalismo del álgebra universal es mucho más restrictivo; esencialmente, solo permite enunciados de primer orden que tienen la forma de ecuaciones cuantificadas universalmente entre términos, por ejemplo${\displaystyle \forall }$ incógnita ${\displaystyle \forall }$y  ( x  + y = y + x ). Una consecuencia es que la elección de una signatura es más significativa en el álgebra universal que en la teoría de modelos. Por ejemplo, la clase de grupos, en la signatura que consiste en el símbolo de función binaria × y el símbolo constante 1, es una clase elemental , pero no es una variedad . El álgebra universal resuelve este problema añadiendo un símbolo de función unaria ⁻¹ .     

En el caso de los campos, esta estrategia solo funciona para la suma. Para la multiplicación, falla porque el 0 no tiene inverso multiplicativo. Un intento ad hoc para solucionar esto sería definir 0 ⁻¹  =  0. (Este intento falla, esencialmente porque con esta definición 0  ×  0 ⁻¹  =  1 no es cierto). Por lo tanto, es natural considerar las funciones parciales, es decir, funciones definidas solo en un subconjunto de su dominio. Sin embargo, existen varias maneras obvias de generalizar nociones como subestructura, homomorfismo e identidad.

En la teoría de tipos , existen muchos tipos de variables, cada una con un tipo . Los tipos se definen inductivamente; dados dos tipos δ y σ, también existe un tipo σ → δ que representa funciones de objetos de tipo σ a objetos de tipo δ. Una estructura para un lenguaje tipado (en la semántica de primer orden ordinaria) debe incluir un conjunto separado de objetos de cada tipo, y para un tipo de función, la estructura debe contener información completa sobre la función representada por cada objeto de ese tipo.

Existen varias semánticas posibles para la lógica de orden superior , como se explica en el artículo sobre lógica de segundo orden . Al utilizar la semántica completa de orden superior, una estructura solo necesita tener un universo para objetos de tipo 0, y el esquema T se extiende de manera que un cuantificador sobre un tipo de orden superior se satisface en el modelo si y solo si es disquotacionalmente verdadero. Al utilizar la semántica de primer orden, se agrega una clasificación adicional para cada tipo de orden superior, como en el caso de un lenguaje de primer orden con múltiples clasificaciones.

En el estudio de la teoría de conjuntos y la teoría de categorías , a veces resulta útil considerar estructuras en las que el dominio del discurso es una clase propia en lugar de un conjunto. Estas estructuras se denominan a veces modelos de clase para distinguirlas de los «modelos de conjunto» mencionados anteriormente. Cuando el dominio es una clase propia, cada símbolo de función y relación también puede representarse mediante una clase propia.

En los Principia Mathematica de Bertrand Russell , también se permitía que las estructuras tuvieran una clase propia como su dominio.