Estructura (lógica matemática)

Mapping of mathematical formulas to a particular meaning, in universal algebra and in model theory

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

El álgebra universal estudia las estructuras que generalizan las estructuras algebraicas como grupos , anillos , campos y espacios vectoriales . El término álgebra universal se usa para estructuras sin símbolos de relación . ^[1]

La teoría de modelos tiene un alcance diferente que abarca teorías 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 que se utilizan para definir la semántica de la lógica de primer orden . Para una teoría dada en la teoría de modelos, una estructura se llama modelo si satisface los axiomas definitorios de esa teoría, aunque a veces se desambigua como modelo semántico cuando se discute la noción en el marco más general de modelos matemáticos . Los lógicos a veces se refieren a las estructuras como interpretaciones . ^[2]

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 .

Definición

Formalmente, una estructura se puede definir como un triple${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$que consta de un dominio A , una firma σ y una función de interpretación I que indica cómo se interpretará la firma en el dominio. Para indicar que una estructura tiene una firma particular σ, uno puede referirse a ella como una estructura σ.

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), o su universo (especialmente en teoría de modelos). En la lógica clásica de primer orden, la definición de una estructura prohíbe el dominio vacío . ^[3]

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 una distinción de notación 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) ^[4].

Firma

La firma ${\displaystyle \sigma =(S,\operatorname {ar} )}$ de 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 {\text{ar:}}\ S\to \mathbb {N} _{0}}$que atribuye a cada símbolo s un número natural ${\displaystyle n=\operatorname {ar} (s)}$que se llama la aridad de s porque es la aridad de la interpretación de 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 I de${\displaystyle {\mathcal {A}}}$asigna funciones y relaciones a los símbolos de la firma. A cada símbolo de función f de aridad n se le asigna una función n -aria${\displaystyle f^{\mathcal {A}}=I(f)}$en el dominio. A cada símbolo de relación R de aridad n se le asigna una relación n -aria${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$en el dominio. Un símbolo de función nular c se llama símbolo constante , porque su interpretación 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 distinción de notación entre un símbolo sy su interpretación I (s) . Por ejemplo, si f es un símbolo de función binaria de${\displaystyle {\mathcal {A}}}$, uno simplemente escribe ${\displaystyle f:{\mathcal {A}}^{2}\rightarrow {\mathcal {A}}}$ en vez de ${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\rightarrow |{\mathcal {A}}|}$.

Ejemplos

La firma estándar σ _f para campos consta de 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 0 y 1 (determinados de forma única por + y × respectivamente). Así, una estructura (álgebra) para esta firma consta de un conjunto de elementos A 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. ElLos números racionales Q , los números reales R y los números complejos C , como cualquier otro campo, se pueden considerar como estructuras σ de una manera obvia:

${\displaystyle {\mathcal {Q}}=(Q,\sigma _{f},I_{\mathcal {Q}})}$

${\displaystyle {\mathcal {R}}=(R,\sigma _{f},I_{\mathcal {R}})}$

${\displaystyle {\mathcal {C}}=(C,\sigma _{f},I_{\mathcal {C}})}$

En los tres casos tenemos la firma estándar dada por

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

con

${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$,   ${\displaystyle \operatorname {ar} _{f}(+)=\operatorname {ar} _{f}(\times )=2,\operatorname {ar} _{f}(-)=1,\operatorname {ar} _{f}(0)=\operatorname {ar} _{f}(1)=0}$. ^[5]

Funciones de interpretación:

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

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

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

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

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

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

Pero el anillo Z de números enteros , que no es un campo, también es una estructura σ _f de la misma manera. De hecho, no hay ningún requisito de que ninguno de los axiomas de campo se mantenga en una estructura σ _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 son, por supuesto, estructuras algebraicas en el sentido habitual y vago de la palabra.

La firma ordinaria para la teoría de conjuntos incluye una sola 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 de estos elementos.

Subestructuras inducidas y subconjuntos cerrados

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

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

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

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

Para cada subconjunto ${\displaystyle B\subseteq |{\mathcal {A}}|}$ hay un subconjunto cerrado más pequeño de ${\displaystyle |{\mathcal {A}}|}$que contiene B . Se llama subconjunto cerrado generado por B , o el casco de B , y se denota por${\displaystyle \langle B\rangle }$ o ${\displaystyle \langle B\rangle _{\mathcal {A}}}$. El operador${\displaystyle \langle \rangle }$es un operador de cierre finitario en el conjunto de subconjuntos de${\displaystyle |{\mathcal {A}}|}$.

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

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 el enrejado de las subestructuras de una estructura en detalle.

Ejemplos

Sea σ = {+, ×, -, 0, 1} nuevamente la firma estándar para los campos. Cuando se consideran como estructuras σ de 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.

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 enteros son la subestructura de los números reales generados por el conjunto vacío, usando esta firma. La noción en álgebra abstracta que corresponde a una subestructura de un campo, en esta firma, es la de un subanillo , en lugar de la de un subcampo .

La forma más obvia para definir un gráfico que es una estructura con una firma σ que consiste en un único binario símbolo de relación E . Los vértices de la gráfica forman el dominio de la estructura, y para dos vértices de un y b ,${\displaystyle (a,b)\!\in {\text{E}}}$  medios que una y b están conectadas 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 G un gráfico que consta de dos vértices conectados por una arista y sea H el gráfico que consta de los mismos vértices pero sin aristas. H es un subgrafo de G , pero no una subestructura inducida. La noción en teoría de grafos que corresponde a subestructuras inducidas es la de subgrafos inducidos.

Homomorfismos e incrustaciones

Homomorfismos

Dadas dos estructuras ${\displaystyle {\mathcal {A}}}$ y ${\displaystyle {\mathcal {B}}}$de la misma firma σ, un homomorfismo (σ-) de${\displaystyle {\mathcal {A}}}$ para ${\displaystyle {\mathcal {B}}}$es un mapa ${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$que preserva las funciones y 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 n símbolo de relación 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\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R}$.

La notación para un homomorfismo h de${\displaystyle {\mathcal {A}}}$ para ${\displaystyle {\mathcal {B}}}$ es ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$.

Para cada firma σ 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 llama fuerte si para cada n -símbolo de relación R y cualquier elemento${\displaystyle b_{1},b_{2},\dots ,b_{n}\in |{\mathcal {B}}|}$ tal que ${\displaystyle (b_{1},b_{2},\dots ,b_{n})\in R}$, existen ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$ tal que ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R}$ y ${\displaystyle b_{1}=h(a_{1}),\,b_{2}=h(a_{2}),\,\dots ,\,b_{n}=h(a_{n}).}$^{[ cita requerida ]} Los fuertes homomorfismos dan lugar a una subcategoría de σ- Hom .

Inserciones

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

• para cada n símbolo de relación 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\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R}$.

Por lo tanto, una incrustación es lo mismo que un homomorfismo fuerte que es uno a uno. La categoría σ- Emb de σ-estructuras y σ-embeddings 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 anteriormente, en la codificación estándar de gráficos como estructuras, las subestructuras inducidas son precisamente los subgráficos 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 está 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 ${\displaystyle {\mathcal {A}}}$ y ${\displaystyle {\mathcal {B}}}$ de una firma 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 en el problema de homomorfismo. ^[6] 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 conjunta 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 muestra que el problema de la consulta conjuntiva también es equivalente al problema del homomorfismo.

Estructuras y lógica de primer orden

En ocasiones, las estructuras se denominan "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 lógica de primer orden, como la que se usa 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 ${\displaystyle {\mathcal {M}}}$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 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 T si el lenguaje de${\displaystyle {\mathcal {M}}}$es el mismo que el lenguaje de T y cada oración en T se satisface por${\displaystyle {\mathcal {M}}}$. Así, por ejemplo, un "anillo" es una estructura para el lenguaje de los anillos que satisface cada uno de los axiomas del anillo, 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.

Relaciones definibles

Una relación n -aria R en el universo M de una estructura${\displaystyle {\mathcal {M}}}$se dice que es definible (o explícitamente definible , o${\displaystyle \emptyset }$- definible ) si hay una fórmula φ ( x ₁ , ..., x _n ) tal que

${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$

En otras palabras, R es definible si y solo si hay una fórmula φ tal 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 m de M se puede definir en${\displaystyle {\mathcal {M}}}$si y solo si hay una fórmula φ ( x ) tal que

${\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}$

Definibilidad con parámetros

Se dice que una relación R es definible con parámetros (o${\displaystyle |{\mathcal {M}}|}$- definible ) si hay una fórmula φ con parámetros de${\displaystyle {\mathcal {M}}}$tal que R es definible usando φ. Cada elemento de una estructura se puede definir utilizando el propio elemento como parámetro.

Algunos autores usan definible para significar definible sin parámetros , ^{[ cita requerida ]} mientras que otros autores se refieren a 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

Recuerde de arriba que una relación n -aria R en el universo M de una estructura${\displaystyle {\mathcal {M}}}$es explícitamente definible si hay una fórmula φ ( x ₁ , ..., x _n ) tal que

${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}}$

Aquí la fórmula φ usada para definir una relación R debe estar sobre la firma de${\displaystyle {\mathcal {M}}}$y entonces φ no puede mencionar a R en sí mismo, ya que R no está en la firma de${\displaystyle {\mathcal {M}}}$. Si hay una fórmula φ en el idioma ampliado que contiene el idioma de${\displaystyle {\mathcal {M}}}$y un nuevo símbolo R , y la relación R es la única relación en${\displaystyle {\mathcal {M}}}$ tal que ${\displaystyle {\mathcal {M}}\vDash \varphi }$, entonces se dice que R es implícitamente definible sobre${\displaystyle {\mathcal {M}}}$.

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

Estructuras de muchos ordenamientos

Las estructuras definidas anteriormente a veces se denominan estructuras de un solo ordenpara distinguirlas de las más generalesestructura de muchos ordenamientos s. Una estructura de muchos ordenamientos puede tener un número arbitrario de dominios. Losgénerosforman parte de la firma y desempeñan el papel de nombres para los diferentes dominios. Las firmas de muchasclases también prescriben en qué clases se definen las funciones y relaciones de una estructura de muchas clases. 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, se pueden considerar como estructuras de dos tipos de la siguiente manera. La firma de dos tipos de espacios vectoriales consta de dos tipos V (para vectores) y S (para escalares) y los siguientes símbolos de función:

+ S y × S de aridad ( S ,  S ;  S ). - S de aridad ( S ;  S ). 0 S y 1 S de aridad ( S ).

+ V de aridad ( V ,  V ;  V ). - V de aridad ( V ;  V ). 0 V de aridad ( V ).

× de aridad ( S ,  V ;  V ).

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

Las estructuras de muchos tipos 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. Una lógica de muchos ordenada conduce sin embargo, 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. ^[7]

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; esencialmente solo permite oraciones de primer orden que tienen la forma de ecuaciones cuantificadas universalmente entre términos, por ejemplo${\displaystyle \forall }$ X ${\displaystyle \forall }$y  ( x  +  y  =  y  +  x ). Una consecuencia es que la elección de una firma es más significativa en el álgebra universal que en la 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 ⁻¹ .

En el caso de los campos, esta estrategia solo funciona para sumar. 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 cierto). Por lo tanto, uno es naturalmente llevado a permitir funciones parciales , es decir, funciones que se definen solo en un subconjunto de su dominio. Sin embargo, hay varias formas obvias de generalizar nociones como subestructura, homomorfismo e identidad.

Estructuras para lenguajes escritos

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 σ a objetos de tipo δ. Una estructura para un lenguaje escrito (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

Hay más de una semántica posible para la lógica de orden superior , como se explica en el artículo sobre lógica de segundo orden . Cuando se usa semántica de orden superior completa, 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 sea satisfecho por el modelo si y solo si es desquotacional verdadero. Cuando se usa 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 muchas clasificaciones.

Estructuras que son clases adecuadas

En el estudio de la teoría de conjuntos y la teoría de categorías , a veces es útil considerar estructuras en las que el dominio del discurso es una clase propiamente dicha en lugar de un conjunto. Estas estructuras a veces se denominan modelos de clase para distinguirlas de los "modelos de conjuntos" discutidos anteriormente. Cuando el dominio es una clase adecuada, cada símbolo de función y relación también puede estar representado por una clase adecuada.

En los Principia Mathematica de Bertrand Russell , también se permitió que las estructuras tuvieran una clase adecuada como su dominio.

Ver también

• Estructura matemática

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. 9 . Elsevier. ISBN 978-0-444-51667-1.
3. Esto es similar a la definición de un número primo en la teoría de números elemental, que se ha elegido cuidadosamente para que elnúmero irreductible 1 no se considere primo. La convención de que el dominio de una estructura puede no estar vacío es particularmente importante en lógica, porque varias reglas de inferencia comunes, en particular, la instanciación universal , no son sólidas cuando se permiten estructuras vacías. Un sistema lógico que permite el dominio vacío se conoce como lógica inclusiva .
4. Como consecuencia de estas convenciones, la notación${\displaystyle |{\mathcal {A}}|}$también puede usarse para referirse a la cardinalidad del dominio de${\displaystyle {\mathcal {A}}}$. En la práctica, esto nunca da lugar a confusión.
5. Nota: 0 , 1 y - a la izquierda se refieren a signos de${\displaystyle S_{f}}$. 0, 1, 2 y - a la derecha se refieren a números naturales de${\displaystyle N_{0}}$y a la operación unaria menos en${\displaystyle Q}$
6. Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Restricciones y álgebra universal", Annals of Mathematics and Artificial Intelligence , 24 : 51–67, doi : 10.1023 / A: 1018941030227 , S2CID 15244028 . 
7. Jacobs, Bart (1999), Teoría de tipos y lógica categórica , 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], Model Theory , Elsevier, ISBN 978-0-7204-0692-4
• Diestel, Reinhard (2005) [1997], Teoría de grafos , Textos de posgrado en matemáticas, 173 (3.a 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 (2a 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: 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), A Concise Introduction to Mathematical Logic (3.a 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 la lógica clásica (una entrada de la Enciclopedia de Filosofía de Stanford )