Estructura (lógica matemática)

Mapeo de fórmulas matemáticas con un significado particular, en álgebra universal y en teoría de modelos.

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

El álgebra universal estudia estructuras que generalizan las estructuras algebraicas como grupos , anillos , campos y espacios vectoriales . El término álgebra universal se utiliza para 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 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 , cf. también la teoría de la verdad de Tarski o la semántica tarskiana .

Para 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 elimina la ambigüedad como modelo semántico cuando se analiza la noción en el marco 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, ver 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, un método principal para demostrar la coherencia de un conjunto de axiomas ha sido proporcionar un modelo para ello.

Definición

Formalmente, una estructura se puede definir como un triple que consta de un dominio , una firma y una función de interpretación que indica cómo se interpretará la firma en el dominio. Para indicar que una estructura tiene una firma particular, podemos referirnos a ella como 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 conjunto subyacente de la estructura, su portador (especialmente en álgebra universal), su universo (especialmente en teoría de modelos, cf. universo ), o su dominio del discurso . En la lógica clásica de primer orden, la definición de estructura prohíbe el dominio vacío . ^{[ cita necesaria ] [5]}

A veces, la notación o se utiliza para el dominio de , pero a menudo no se hace ninguna distinción notación entre una estructura y su dominio (es decir, el mismo símbolo se refiere tanto a la estructura como a su dominio) ^. ${\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 asigna 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 ^{[ se necesita aclaración ]} 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 llama firma algebraica . Una estructura con tal firma también se llama álgebra ; esto no debe confundirse con la noción de álgebra sobre un campo .

Función de interpretación

La función de interpretación asigna funciones y relaciones a los símbolos de la firma. 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 (-aria) se llama símbolo constante , porque su interpretación puede identificarse 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 tanto una función de interpretación) está dada por el contexto, no se hace ninguna distinción notacional entre un símbolo y su interpretación. Por ejemplo, si es una función binaria, el símbolo de uno simplemente 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 consta de dos símbolos de función binaria y de 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 manera única por y respectivamente). Así, una estructura (álgebra) para esta firma consta de un conjunto de elementos junto con dos funciones binarias, que pueden mejorarse con una función unaria, y dos elementos distinguidos; pero no es necesario 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 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

$${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$

^[7] ${\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 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 campo, también es una estructura del mismo modo. De hecho, no existe ningún requisito de que alguno de los axiomas de campo 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 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 flexible 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 consta de 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 tener 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 concuerdan 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 está 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 -aria (en la firma 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 hay un subconjunto cerrado más pequeño que contiene. Se llama subconjunto cerrado generado por o el casco de y denotado por o . El operador es un operador de cierre finito en 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 de su interpretación en Por el contrario, 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 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 firma estándar para los campos. Cuando se consideran estructuras en forma 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 campo. ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ ${\displaystyle \sigma }$

El conjunto de números enteros da una subestructura aún más pequeña de los números reales que no es un campo. De hecho, los números enteros son la subestructura de los números reales generados por el conjunto vacío, utilizando esta firma. La noción en álgebra abstracta que corresponde a una subestructura de un campo, en esta firma, es la de subanillo , más que la de subcampo .

La forma más obvia de definir un gráfico es una estructura con una firma que consta de un único símbolo de relación binaria. Los vértices del gráfico forman el dominio de la estructura, y para dos vértices y significa que y están conectados por un borde. En esta codificación, la noción de subestructura inducida es más restrictiva que la noción de subgrafo . Por ejemplo, sea un gráfico que consta de dos vértices conectados por una arista, y sea el gráfico que consta de 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 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 firma σ, un (σ-)homomorfismo de a es un mapa 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 símbolo de función n -aria f de σ y cualquier elemento , 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 cualquier elemento , 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 normalmente se denota 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 σ hay una categoría concreta σ- Hom que tiene σ-estructuras como objetos y σ-homomorfismos como morfismos .

A veces , un homomorfismo se denomina fuerte si: ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• Para cada símbolo de relación n -ario R de la teoría del objeto y cualquier elemento tal que , existen tales que y ^{[ cita necesaria ] [ dudoso ]} ${\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 defendió 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 cualquier elemento , 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 tanto, una incrustación es lo mismo que un homomorfismo fuerte que es uno a uno. La categoría σ- Emb de σ-estructuras y σ-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 .

Ejemplo

Como se vio arriba, en la codificación estándar de gráficos como estructuras, las subestructuras inducidas son precisamente los subgrafos inducidos. Sin embargo, un homomorfismo entre gráficos es lo mismo que un homomorfismo entre las dos estructuras que codifican el gráfico. En el ejemplo de la sección anterior, aunque el subgrafo H de G no es inducido, el mapa de identidad id:  H  →  G es un homomorfismo. Este mapa 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.

problema de homomorfismo

El siguiente problema se conoce como problema de homomorfismo :

Dadas dos estructuras finitas y de 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}}}$

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

Otra aplicación es 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 describirse mediante 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 muestra que el problema de consulta conjuntiva también es equivalente al problema de homomorfismo.

Estructuras y lógica de primer orden.

A veces se hace referencia a las estructuras como "estructuras de primer orden". Esto es engañoso, ya que nada en su definición los vincula a ninguna lógica específica y, de hecho, son adecuados como objetos semánticos tanto para fragmentos muy restringidos de la lógica de primer orden, como la utilizada 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 a menudo se denominan 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 en el lenguaje que consta del lenguaje de junto con un símbolo constante para cada elemento 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 con Así, por ejemplo, un "anillo" es una estructura para el lenguaje de anillos que satisface cada uno de los axiomas de los 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 de 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, dominio) de la estructura es definible (o explícitamente definible cf. definibilidad Beth , o - definible , o definible con parámetros de cf. más abajo) si existe una fórmula tal que ${\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 sólo 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 hay una fórmula con parámetros ^{[ aclaración necesaria ]} de tal que se pueda definir usando Cada elemento de una estructura se puede definir usando el elemento mismo como parámetro. ${\displaystyle R}$ ${\displaystyle |{\mathcal {M}}|}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R}$ ${\displaystyle \varphi .}$

Algunos autores usan definible en el sentido de definible sin parámetros , ^{[ cita requerida ]} mientras que otros autores quieren decir definible con parámetros . ^{[ cita necesaria ]} 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

Recuerde lo dicho anteriormente 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 variadas

Las estructuras definidas anteriormente a veces se denominanestructuras de un solo orden para distinguirlas de las más generalesestructura variada s. Una estructura multiordenada puede tener un número arbitrario de dominios. Losgénerosson parte de la firma y desempeñan el papel de nombres para los diferentes dominios. Las firmas multiclasificadastambién prescriben en qué clasificaciones se definen las funciones y relaciones de una estructura multiclasificada. 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 clases, en lugar de números naturales.

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

Si V es un espacio vectorial sobre un campo F , la estructura de dos ordenamiento correspondiente consta del dominio vectorial , el dominio escalar y las funciones obvias, como el vector cero , el escalar cero 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 variadas 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 (por lo tanto, poco gratificante) llevar a cabo la generalización explícitamente.

En la mayoría de los esfuerzos matemáticos, no se presta mucha atención a los tipos. Sin embargo, una lógica diversa 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"), capturando la lógica, siendo fibrada sobre otra categoría ("base"), capturando 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 están definidas por una firma 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; Básicamente, sólo permite oraciones de primer orden que tienen la forma de ecuaciones universalmente cuantificadas entre términos, por ejemplo, x y  ( x  +  y  =  y  +  x ). Una consecuencia es que la elección de una firma es más significativa en álgebra universal que en teoría de modelos. Por ejemplo, la clase de grupos, en la firma que consta del 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 agregando un símbolo de función unaria ⁻¹ . ${\displaystyle \forall }$   ${\displaystyle \forall }$

En el caso de campos, esta estrategia funciona sólo para la suma. Para la multiplicación falla porque 0 no tiene inverso multiplicativo. Un intento ad hoc de abordar esto sería definir 0 ⁻¹  = 0. (Este intento falla, esencialmente porque con esta definición 0 × 0 ⁻¹  = 1 no es cierto). 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 mecanografiados

En la teoría de tipos , hay muchos tipos de variables, cada una de las cuales tiene un tipo . Los tipos se definen inductivamente; dados dos tipos δ y σ también hay un tipo σ → δ que representa funciones desde objetos de tipo σ hasta objetos de tipo δ. Una estructura para un lenguaje tipificado (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.

Idiomas de orden superior

Existe 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 semántica completa de orden superior, una estructura sólo necesita tener un universo para objetos de tipo 0, y el esquema T se extiende de modo que el modelo satisface un cuantificador sobre un tipo de orden superior si y sólo si es sin comillas. verdadero. Cuando se utiliza 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 muchos tipos de clasificación.

Estructuras que son clases adecuadas.

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 clases para distinguirlas de los "modelos de conjuntos" analizados anteriormente. Cuando el dominio es una clase propia, cada función y símbolo de relación también puede representarse mediante una clase propia.

En los Principia Mathematica de Bertrand Russell , a las estructuras también se les permitía tener una clase adecuada como dominio.

Ver 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 ciencias de la ingeniería . Manual de Filosofía de la Ciencia. vol. 9. Elsevier. ISBN 978-0-444-51667-1.
3. Diccionario de ingles Oxford, sv "modelo, n., sentido I.8.b", julio de 2023 . Prensa de la Universidad de Oxford. Dedekind señaló el hecho de que tales 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 utilizarse para referirse a la cardinalidad del dominio de En la práctica, esto nunca genera 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, Pedro; Cohén, David; Pearson, Justin (1998), "Restricciones y álgebra universal", Annals of Mathematics and Artificial Intelligence , 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 la 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), Teoría de modelos: una introducción , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98760-6
• Poizat, Bruno (2000), Un curso de teoría de modelos: una 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)