Estructura (lógica matemática)

Asignación de fórmulas matemáticas a un significado particular, en álgebra universal y en teoría de modelos

En el álgebra universal y en la teoría de modelos , una estructura consiste en un conjunto junto con una colección de operaciones y relaciones finitas que se definen en él.

El álgebra universal estudia las estructuras que generalizan las estructuras algebraicas como grupos , anillos , cuerpos y espacios vectoriales . El término álgebra universal se utiliza para las estructuras de teorías de primer orden sin símbolos de relación . ^[1] La teoría de modelos tiene un alcance diferente que abarca teorías de primer orden más arbitrarias , incluidas las estructuras fundamentales como los modelos de teoría de conjuntos .

Desde el punto de vista de la teoría de modelos, las estructuras son los objetos utilizados para definir la semántica de la lógica de primer orden , véase también la teoría de la verdad de Tarski o la semántica tarskiana .

En el caso de una teoría dada en la teoría de modelos, una estructura se denomina modelo si satisface los axiomas definitorios de esa teoría, aunque a veces se la desambigua como modelo semántico cuando se analiza la noción en el contexto más general de los modelos matemáticos . Los lógicos a veces se refieren a las estructuras como " interpretaciones ", ^[2] mientras que el término "interpretación" generalmente tiene un significado diferente (aunque relacionado) en la teoría de modelos, véase interpretación (teoría de modelos) .

En la teoría de bases de datos , las estructuras sin funciones se estudian como modelos para bases de datos relacionales , en forma de modelos relacionales .

Historia

En el contexto de la lógica matemática, el término " modelo " fue aplicado por primera vez en 1940 por el filósofo Willard Van Orman Quine , en referencia al matemático Richard Dedekind (1831 - 1916), pionero en el desarrollo de la teoría de conjuntos . ^{[3] [4]} Desde el siglo XIX, uno de los principales métodos para demostrar la consistencia de un conjunto de axiomas ha sido proporcionar un modelo para él.

Definición

Formalmente, una estructura puede definirse como una tripleta que consta de un dominio, una firma y una función de interpretación que indica cómo debe interpretarse la firma en el dominio. Para indicar que una estructura tiene una firma particular, se puede hacer referencia a ella como una -estructura. ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle A,}$ ${\displaystyle \sigma ,}$ ${\displaystyle I}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$

Dominio

El dominio de una estructura es un conjunto arbitrario; también se le llama el 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 . ^{[ cita requerida ] [5]}

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

Firma

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

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

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

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

Función de interpretación

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

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

Ejemplos

La firma estándar para los campos consiste en dos símbolos de función binaria y donde se pueden derivar símbolos adicionales, como un símbolo de función unaria (determinado de forma única por ) y los dos símbolos constantes y (determinados de forma única por y respectivamente). Por lo tanto, una estructura (álgebra) para esta firma consiste en un conjunto de elementos junto con dos funciones binarias, que se pueden mejorar con una función unaria, y dos elementos distinguidos; pero no hay ningún requisito de que satisfaga ninguno de los axiomas de campo. Los números racionales, los números reales y los números complejos , como cualquier otro campo, pueden considerarse como -estructuras de una manera obvia: ${\displaystyle \sigma _{f}}$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle \mathbf {-} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle A}$ ${\displaystyle \mathbb {Q} ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} ,}$ ${\displaystyle \sigma }$ $${\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 con ^[7] y $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ ${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$ $${\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 es: ${\displaystyle I_{\mathcal {Q}}}$

${\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 lleva cada número racional a y ${\displaystyle x}$ ${\displaystyle -x,}$

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

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

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

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

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

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

Subestructuras inducidas y subconjuntos cerrados

${\displaystyle {\mathcal {A}}}$se llama subestructura (inducida) de si ${\displaystyle {\mathcal {B}}}$

• ${\displaystyle {\mathcal {A}}}$y tienen la misma firma ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \sigma ({\mathcal {A}})=\sigma ({\mathcal {B}});}$
• El dominio de está contenido en el dominio de y ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}:}$ ${\displaystyle |{\mathcal {A}}|\subseteq |{\mathcal {B}}|;}$
• Las interpretaciones de todos los símbolos de función y relación coinciden en ${\displaystyle |{\mathcal {A}}|.}$

La notación habitual para esta relación es ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {B}}.}$

Un subconjunto del dominio de una estructura se llama cerrado si es cerrado bajo las funciones de es decir, si se cumple la siguiente condición: para cada número natural, cada símbolo de función -ario (en la signatura de ) y todos los elementos el resultado de aplicar a la -tupla es nuevamente un elemento de ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle n,}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in B,}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle b_{1}b_{2}\dots b_{n}}$ ${\displaystyle B:}$ ${\displaystyle f(b_{1},b_{2},\dots ,b_{n})\in B.}$

Para cada subconjunto existe un subconjunto cerrado más pequeño de que contiene Se denomina subconjunto cerrado generado por o la envoltura de y denotado por o . El operador es un operador de cierre finitario sobre el conjunto de subconjuntos de . ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle B.}$ ${\displaystyle B,}$ ${\displaystyle B,}$ ${\displaystyle \langle B\rangle }$ ${\displaystyle \langle B\rangle _{\mathcal {A}}}$ ${\displaystyle \langle \rangle }$ ${\displaystyle |{\mathcal {A}}|}$

Si y es un subconjunto cerrado, entonces es una subestructura inducida de donde asigna a cada símbolo de σ la restricción a de su interpretación en A la inversa, el dominio de una subestructura inducida es un subconjunto cerrado. ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle B\subseteq A}$ ${\displaystyle (B,\sigma ,I')}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle I'}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {A}}.}$

Los subconjuntos cerrados (o subestructuras inducidas) de una estructura forman una red . El punto de encuentro de dos subconjuntos es su intersección. La unión de dos subconjuntos es el subconjunto cerrado generado por su unión. El álgebra universal estudia en detalle la red de subestructuras de una estructura.

Ejemplos

Sea nuevamente la signatura estándar para los cuerpos. Cuando se consideran como estructuras de la manera natural, 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 de cuerpo. ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ ${\displaystyle \sigma }$

El conjunto de los números enteros da una subestructura aún más pequeña de los números reales que no es un cuerpo. De hecho, los números 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 que consiste en un solo símbolo de relación binaria Los vértices del grafo forman el dominio de la estructura, y para dos vértices y significa que y 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 un grafo que consiste en dos vértices conectados por una arista, y sea el grafo que consiste en los mismos vértices pero sin aristas. es un subgrafo de pero no una subestructura inducida. La noción en teoría de grafos que corresponde a las subestructuras inducidas es la de subgrafos inducidos . ${\displaystyle \sigma }$ ${\displaystyle E.}$ ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle (a,b)\!\in {\text{E}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G,}$

Homomorfismos e incrustaciones

Homomorfismos

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

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

${\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 -ario R de σ y cualesquiera elementos , se cumple la siguiente implicación: ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$

${\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}}}$

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

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

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

A veces se dice que un homomorfismo es fuerte si: ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• Para cada símbolo de relación n -ario R de la teoría de objetos y cualesquiera elementos tales que , existen tales que y ^{[ cita requerida ] [ dudoso – discutir ]} ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in |{\mathcal {B}}|}$ ${\displaystyle (b_{1},b_{2},\dots ,b_{n})\in R^{\mathcal {B}}}$ ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}}$ ${\displaystyle b_{1}=h(a_{1}),\,b_{2}=h(a_{2}),\,\dots ,\,b_{n}=h(a_{n}).}$

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

Incrustaciones

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

• Para cada símbolo de relación n -ario R de σ y cualesquiera elementos , se cumple la siguiente equivalencia: ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$

${\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}}}$

(donde como antes , se refiere a la interpretación del símbolo de relación R de la teoría del objeto σ en la estructura , respectivamente). ${\displaystyle R^{\mathcal {A}}}$ ${\displaystyle R^{\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Por lo tanto, una incrustación es lo mismo que un homomorfismo fuerte que es biunívoco. La categoría σ- Emb de las σ-estructuras y las σ-incrustaciones es una subcategoría concreta de σ- Hom .

Las subestructuras inducidas corresponden a subobjetos en σ- Emb . Si σ tiene solo 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 .

Ejemplo

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 está inducido, la función identidad id:  H  →  G es un homomorfismo. Esta función es, de hecho, un monomorfismo en la categoría σ- Hom , y por tanto H es un subobjeto de G que no es una subestructura inducida.

Problema de homomorfismo

El siguiente problema se conoce como problema de homomorfismo :

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

Todo problema de satisfacción de restricciones (CSP) tiene una traducción al problema de homomorfismo. ^[8] Por lo tanto, la complejidad del CSP se puede estudiar 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 en una base de datos puede ser descrita por otra estructura en la misma firma 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.

Estructuras y lógica de primer orden

A las estructuras se las suele denominar "estructuras de primer orden". Esto es engañoso, ya que nada en su definición las vincula a ninguna lógica específica y, de hecho, son adecuadas como objetos semánticos tanto para fragmentos muy restringidos de lógica de primer orden, como la que se utiliza en el álgebra universal, como para la lógica de segundo orden . En relación con la lógica de primer orden y la teoría de modelos, las estructuras suelen denominarse modelos , incluso cuando la pregunta "¿modelos de qué?" no tiene una respuesta obvia.

Relación de satisfacción

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

Se dice que una estructura es un modelo de una teoría si el lenguaje de es el mismo que el lenguaje de y cada oración en se satisface por Así, por ejemplo, un "anillo" es una estructura para el lenguaje de anillos que satisface cada uno de los axiomas del anillo, y un modelo de la 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. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}.}$

Relaciones definibles

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

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

Definibilidad con parámetros

Se dice que una relación es definible con parámetros (o - definible ) si existe una fórmula con parámetros ^{[ aclaración necesaria ]} tal que sea definible usando Cada elemento de una estructura es definible usando el elemento mismo como parámetro. ${\displaystyle R}$ ${\displaystyle |{\mathcal {M}}|}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R}$ ${\displaystyle \varphi .}$

Algunos autores utilizan definible para significar definible sin parámetros , ^{[ cita requerida ]} mientras que otros autores quieren decir definible con parámetros . ^{[ cita requerida ]} En términos generales, la convención de que definible significa definible sin parámetros es más común entre los teóricos de conjuntos, mientras que la convención opuesta es más común entre los teóricos de modelos.

Definibilidad implícita

Recordemos de lo anterior que una relación -aria en el universo de es explícitamente definible si existe una fórmula tal que ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$ $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$

Aquí la fórmula utilizada para definir una relación debe estar sobre la firma de y por lo tanto no puede mencionarse a sí misma, ya que no está en la firma de Si hay una fórmula en el lenguaje extendido que contiene el lenguaje de y un nuevo símbolo y la relación es la única relación sobre tal que entonces se dice que es implícitamente definible sobre ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}\vDash \varphi ,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$

Según el teorema de Beth , toda relación implícitamente definible es explícitamente definible.

Estructuras de múltiples tipos

Las estructuras definidas anteriormente a veces se denominanestructuras de una sola clase para distinguirlas de las más generalesEstructuras polisémicas . Una estructura polisémica puede tener un número arbitrario de dominios. Losordenamientosson parte de la firma y cumplen la función de nombres para los diferentes dominios.Las firmas polisémicastambién prescriben en qué ordenamientos se definen las funciones y relaciones de una estructura polisémica. Por lo tanto, las aridades de los símbolos de función o de relación deben ser objetos más complicados, como tuplas de ordenamientos, en lugar de números naturales.

Los espacios vectoriales , por ejemplo, pueden considerarse estructuras de dos clases de la siguiente manera. La firma de dos clases de los espacios vectoriales consta de dos clases V (para vectores) y S (para escalares) y los siguientes símbolos de función:

Si V es un espacio vectorial sobre un cuerpo F , la estructura de dos órdenes correspondiente consiste en el dominio vectorial , el dominio escalar y las funciones obvias, como el cero vectorial , el cero escalar o la multiplicación escalar . ${\displaystyle {\mathcal {V}}}$ ${\displaystyle |{\mathcal {V}}|_{V}=V}$ ${\displaystyle |{\mathcal {V}}|_{S}=F}$ ${\displaystyle 0_{V}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{V}}$ ${\displaystyle 0_{S}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{S}}$ ${\displaystyle \times ^{\mathcal {V}}:|{\mathcal {V}}|_{S}\times |{\mathcal {V}}|_{V}\rightarrow |{\mathcal {V}}|_{V}}$

Las estructuras multiclasificadas se utilizan a menudo como una herramienta conveniente, incluso cuando podrían evitarse con un poco de esfuerzo. Pero rara vez se definen de manera rigurosa, porque es sencillo y tedioso (y, por lo tanto, poco gratificante) llevar a cabo la generalización explícitamente.

En la mayoría de los trabajos matemáticos no se presta mucha atención a los tipos. Sin embargo, una lógica de múltiples tipos conduce naturalmente a una teoría de tipos . Como dice Bart Jacobs: "Una lógica es siempre una lógica sobre una teoría de tipos". Este énfasis a su vez conduce a la lógica categórica porque una lógica sobre una teoría de tipos corresponde categóricamente a una categoría ("total"), que captura la lógica, que se encuentra sobre otra categoría ("base"), que captura la teoría de tipos. ^[9]

Otras generalizaciones

Álgebras parciales

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 oraciones de primer orden. El formalismo del álgebra universal es mucho más restrictivo; esencialmente, solo permite oraciones de primer orden que tienen la forma de ecuaciones cuantificadas universalmente entre términos, por ejemplo, x 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 de 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 ⁻¹ . ${\displaystyle \forall }$   ${\displaystyle \forall }$

En el caso de los cuerpos, esta estrategia funciona sólo para la suma. Para la multiplicación, falla porque 0 no tiene un inverso multiplicativo. Un intento ad hoc de lidiar con esto sería definir 0 ⁻¹  = 0. (Este intento falla, esencialmente porque con esta definición 0 × 0 ⁻¹  = 1 no es verdadero.) Por lo tanto, uno se ve naturalmente llevado a permitir funciones parciales, es decir, funciones que se definen sólo en un subconjunto de su dominio. Sin embargo, hay varias formas obvias de generalizar nociones como subestructura, homomorfismo e identidad.

Estructuras para lenguajes tipados

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

Lenguajes de orden superior

Hay más de una semántica posible para la lógica de orden superior , como se analiza en el artículo sobre lógica de segundo orden . Cuando se utiliza una 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 modo que un cuantificador sobre un tipo de orden superior se satisface por el modelo si y solo si es verdadero sin citación. Cuando se utiliza una semántica de primer orden, se agrega una ordenación adicional para cada tipo de orden superior, como en el caso de un lenguaje de primer orden con ordenación múltiple.

Estructuras que son clases propias

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 a veces se denominan modelos de clase para distinguirlas de los "modelos de conjunto" analizados 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 permitió que las estructuras tuvieran una clase propia como su dominio.

Véase también

• Estructura matemática  – Objeto matemático adicional

Notas

1. Algunos autores se refieren a las estructuras como "álgebras" cuando generalizan el álgebra universal para permitir tanto relaciones como funciones.
2. Hodges, Wilfrid (2009). "Modelado funcional y modelos matemáticos". En Meijers, Anthonie (ed.). Filosofía de la tecnología y las ciencias de la ingeniería . Manual de filosofía de la ciencia. Vol. 9. Elsevier. ISBN 978-0-444-51667-1.
3. Oxford English Dictionary, sv "model, n., sense I.8.b", julio de 2023. Oxford University Press. Dedekind señaló que dichas clases constituyen un modelo del sistema tradicional de números reales.[1]
4. Quine, Willard VO (1940). Lógica matemática . Vol. vi. Norton.
5. Un sistema lógico que permite el dominio vacío se conoce como lógica inclusiva .
6. Como consecuencia de estas convenciones, la notación también puede usarse para referirse a la cardinalidad del dominio de En la práctica esto nunca conduce a confusión. ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}.}$
7. Nota: y a la izquierda se refieren a los signos de y a la derecha se refieren a los números naturales de y a la operación unaria menos en ${\displaystyle \mathbf {0} ,\mathbf {1} ,}$ ${\displaystyle \mathbf {-} }$ ${\displaystyle S_{f}.}$ ${\displaystyle 0,1,2,}$ ${\displaystyle -}$ ${\displaystyle N_{0}}$ ${\displaystyle \mathbb {Q} .}$
8. Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Restricciones y álgebra universal", Anales de Matemáticas e Inteligencia Artificial , 24 : 51–67, doi :10.1023/A:1018941030227, S2CID  15244028.
9. Jacobs, Bart (1999), Lógica categórica y teoría de tipos, Elsevier, págs. 1–4, ISBN 9780080528700

Referencias

• Burris, Stanley N.; Sankappanavar, HP (1981), Un curso de álgebra universal, Berlín, Nueva York: Springer-Verlag
• Chang, Chen Chung; Keisler, H. Jerome (1989) [1973], Teoría de modelos , Elsevier, ISBN 978-0-7204-0692-4
• Diestel, Reinhard (2005) [1997], Teoría de grafos, Textos de posgrado en matemáticas, vol. 173 (3.ª ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-3-540-26183-4
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Lógica matemática (2ª ed.), Nueva York: Springer, ISBN 978-0-387-94258-2
• Hinman, P. (2005), Fundamentos de lógica matemática , AK Peters , ISBN 978-1-56881-262-5
• Hodges, Wilfrid (1993), Teoría de modelos , Cambridge: Cambridge University Press , ISBN 978-0-521-30442-9
• Hodges, Wilfrid (1997), Una teoría de modelos más breve , Cambridge: Cambridge University Press , ISBN 978-0-521-58713-6
• Marker, David (2002), Model Theory: An Introduction , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98760-6
• Poizat, Bruno (2000), Un curso de teoría de modelos: Introducción a la lógica matemática contemporánea , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98655-5
• Rautenberg, Wolfgang (2010), Una introducción concisa a la lógica matemática (3.ª ed.), Nueva York : Springer Science+Business Media , doi :10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Rothmaler, Philipp (2000), Introducción a la teoría de modelos , Londres: CRC Press , ISBN 978-90-5699-313-9

Enlaces externos

• Sección de semántica en Lógica clásica (una entrada de la Enciclopedia de filosofía de Stanford)