Estructura (lógica matemática)

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

Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Abril de 2010 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

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

Ver también: Teoría de modelos § Álgebra universal y Álgebra universal § Idea básica

Formalmente, una estructura se puede definir como un triple 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 σ.${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$

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

Firma

Artículo principal: Firma (lógica)

La firma de una estructura consiste en un conjunto de símbolos de función y símbolos de relación junto con una función que atribuye a cada símbolo s un número natural que se llama aridad de s porque es la aridad de la interpretación de s .${\displaystyle \sigma =(S,\operatorname {ar} )}$${\displaystyle S}$${\displaystyle {\text{ar:}}\ S\to \mathbb {N} _{0}}$ ${\displaystyle n=\operatorname {ar} (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

Artículo principal: Interpretación (teoría de modelos)

La función de interpretación I de 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 en el dominio. A cada símbolo de relación R de aridad n se le asigna una relación n -aria 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.${\displaystyle {\mathcal {A}}}$${\displaystyle f^{\mathcal {A}}=I(f)}$${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$

Cuando una estructura (y por 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 , simplemente se escribe en lugar de .${\displaystyle {\mathcal {A}}}$${\displaystyle f:{\mathcal {A}}^{2}\rightarrow {\mathcal {A}}}$${\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 consiste en 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. LaLos 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\}}$,   . ^[5]${\displaystyle \operatorname {ar} _{f}(+)=\operatorname {ar} _{f}(\times )=2,\operatorname {ar} _{f}(-)=1,\operatorname {ar} _{f}(0)=\operatorname {ar} _{f}(1)=0}$

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 y son igualmente definido. ^[5]${\displaystyle I_{\mathcal {R}}}$${\displaystyle I_{\mathcal {C}}}$

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 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 la que 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 .${\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 satisface la siguiente condición: para cada número natural n , cada símbolo de función n -aria f (en la firma de ) y todos los elementos , el resultado de aplicar f a la n tupla es de nuevo un elemento de B : .${\displaystyle B\subseteq |{\mathcal {A}}|}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle b_{1},b_{2},\dots ,b_{n}\in B}$${\displaystyle b_{1}b_{2}\dots b_{n}}$${\displaystyle f(b_{1},b_{2},\dots ,b_{n})\in B}$

Para cada subconjunto no es un subconjunto cerrado más pequeño de los que contiene B . Se llama subconjunto cerrado generado por B , o el casco de B , y se denota por o . El operador es un operador de cierre final en el conjunto de subconjuntos de .${\displaystyle B\subseteq |{\mathcal {A}}|}$${\displaystyle |{\mathcal {A}}|}$${\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 B 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 {\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 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 ,   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${\displaystyle (a,b)\!\in {\text{E}}}$, 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

Ver también: Álgebra universal § Construcciones básicas

Homomorfismos

Dadas dos estructuras y de la misma firma σ, un homomorfismo (σ-) de a es un mapa que conserva 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 -aria 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\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R}$.

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

Inserciones

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

• para cada símbolo de relación n -aria 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\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 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 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

Ver también: Teoría de modelos § Lógica de primer orden ; y teoría de modelos § Axiomatizabilidad, eliminación de cuantificadores y completitud del modelo

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 tiene una relación de satisfacción definida para todas las fórmulas en el lenguaje que consiste en el lenguaje de 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 .${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}\vDash \phi }$${\displaystyle \,\phi }$${\displaystyle {\mathcal {M}}}$

Se dice que una estructura es un modelo de una teoría T si el lenguaje de es el mismo que el lenguaje de T y cada oración en T se satisface con . 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.${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

Relaciones definibles

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

${\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 es definible si y solo si hay una fórmula φ ( x ) tal que${\displaystyle {\mathcal {M}}}$

${\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 - definible ) si hay una fórmula φ con parámetros de tal que R es definible usando φ. Cada elemento de una estructura se puede definir utilizando el propio elemento como parámetro.${\displaystyle |{\mathcal {M}}|}$${\displaystyle {\mathcal {M}}}$

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

Recall from above that an n-ary relation R on the universe M of a structure ${\displaystyle {\mathcal {M}}}$ is explicitly definable if there is a formula φ(x₁,...,x_n) such that

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

Here the formula φ used to define a relation R must be over the signature of ${\displaystyle {\mathcal {M}}}$ and so φ may not mention R itself, since R is not in the signature of ${\displaystyle {\mathcal {M}}}$. If there is a formula φ in the extended language containing the language of ${\displaystyle {\mathcal {M}}}$ and a new symbol R, and the relation R is the only relation on ${\displaystyle {\mathcal {M}}}$ such that ${\displaystyle {\mathcal {M}}\vDash \varphi }$, then R is said to be implicitly definable over ${\displaystyle {\mathcal {M}}}$.

By Beth's theorem, every implicitly definable relation is explicitly definable.

Many-sorted structures

Structures as defined above are sometimes called one-sorted structures to distinguish them from the more general many-sorted structures. A many-sorted structure can have an arbitrary number of domains. The sorts are part of the signature, and they play the role of names for the different domains. Many-sorted signatures also prescribe on which sorts the functions and relations of a many-sorted structure are defined. Therefore, the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.

Vector spaces, for example, can be regarded as two-sorted structures in the following way. The two-sorted signature of vector spaces consists of two sorts V (for vectors) and S (for scalars) and the following function symbols:

+S and ×S of arity (S, S; S). −S of arity (S; S). 0S and 1S of arity (S).

+V of arity (V, V; V). −V of arity (V; V). 0V of arity (V).

× of arity (S, V; V).

If V is a vector space over a field F, the corresponding two-sorted structure ${\displaystyle {\mathcal {V}}}$ consists of the vector domain ${\displaystyle |{\mathcal {V}}|_{V}=V}$, the scalar domain ${\displaystyle |{\mathcal {V}}|_{S}=F}$, and the obvious functions, such as the vector zero ${\displaystyle 0_{V}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{V}}$, the scalar zero ${\displaystyle 0_{S}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{S}}$, or scalar multiplication ${\displaystyle \times ^{\mathcal {V}}:|{\mathcal {V}}|_{S}\times |{\mathcal {V}}|_{V}\rightarrow |{\mathcal {V}}|_{V}}$.

Many-sorted structures are often used as a convenient tool even when they could be avoided with a little effort. But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.

In most mathematical endeavours, not much attention is paid to the sorts. A many-sorted logic however naturally leads to a type theory. As Bart Jacobs puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to categorical logic because a logic over a type theory categorically corresponds to one ("total") category, capturing the logic, being fibred over another ("base") category, capturing the type theory.^[7]

Other generalizations

Partial algebras

Both universal algebra and model theory study classes of (structures or) algebras that are defined by a signature and a set of axioms. In the case of model theory these axioms have the form of first-order sentences. The formalism of universal algebra is much more restrictive; essentially it only allows first-order sentences that have the form of universally quantified equations between terms, e.g. ${\displaystyle \forall }$ x ${\displaystyle \forall }$y (x + y = y + x). One consequence is that the choice of a signature is more significant in universal algebra than it is in model theory. For example, the class of groups, in the signature consisting of the binary function symbol × and the constant symbol 1, is an elementary class, but it is not a variety. Universal algebra solves this problem by adding a unary function symbol ⁻¹.

In the case of fields this strategy works only for addition. For multiplication it fails because 0 does not have a multiplicative inverse. An ad hoc attempt to deal with this would be to define 0⁻¹ = 0. (This attempt fails, essentially because with this definition 0 × 0⁻¹ = 1 is not true.) Therefore, one is naturally led to allow partial functions, i.e., functions that are defined only on a subset of their domain. However, there are several obvious ways to generalize notions such as substructure, homomorphism and identity.

Structures for typed languages

In type theory, there are many sorts of variables, each of which has a type. Types are inductively defined; given two types δ and σ there is also a type σ → δ that represents functions from objects of type σ to objects of type δ. A structure for a typed language (in the ordinary first-order semantics) must include a separate set of objects of each type, and for a function type the structure must have complete information about the function represented by each object of that type.

Higher-order languages

Main article: Second-order logic

There is more than one possible semantics for higher-order logic, as discussed in the article on second-order logic. When using full higher-order semantics, a structure need only have a universe for objects of type 0, and the T-schema is extended so that a quantifier over a higher-order type is satisfied by the model if and only if it is disquotationally true. When using first-order semantics, an additional sort is added for each higher-order type, as in the case of a many sorted first order language.

Structures that are proper classes

In the study of set theory and category theory, it is sometimes useful to consider structures in which the domain of discourse is a proper class instead of a set. These structures are sometimes called class models to distinguish them from the "set models" discussed above. When the domain is a proper class, each function and relation symbol may also be represented by a proper class.

In Bertrand Russell's Principia Mathematica, structures were also allowed to have a proper class as their domain.

See also

• Mathematical structure

Notes

1. Some authors refer to structures as "algebras" when generalizing universal algebra to allow relations as well as functions.
2. Hodges, Wilfrid (2009). "Functional Modelling and Mathematical Models". In Meijers, Anthonie (ed.). Philosophy of technology and engineering sciences. Handbook of the Philosophy of Science. 9. Elsevier. ISBN 978-0-444-51667-1.
3. This is similar to the definition of a prime number in elementary number theory, which has been carefully chosen so that the irreducible number 1 is not considered prime. The convention that the domain of a structure may not be empty is particularly important in logic, because several common inference rules, notably, universal instantiation, are not sound when empty structures are permitted. A logical system that allows the empty domain is known as an inclusive logic.
4. As a consequence of these conventions, the notation ${\displaystyle |{\mathcal {A}}|}$ may also be used to refer to the cardinality of the domain of ${\displaystyle {\mathcal {A}}}$. In practice this never leads to confusion.
5. Note: 0, 1 and − on the left refer to signs of ${\displaystyle S_{f}}$. 0, 1, 2, and - on the right refer to natural numbers of ${\displaystyle N_{0}}$ and to the unary operation minus in ${\displaystyle Q}$
6. Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Constraints and universal algebra", Annals of Mathematics and Artificial Intelligence, 24: 51–67, doi:10.1023/A:1018941030227, S2CID 15244028.
7. Jacobs, Bart (1999), Categorical Logic and Type Theory, Elsevier, pp. 1–4, ISBN 9780080528700

References

• Burris, Stanley N.; Sankappanavar, H. P. (1981), A Course in Universal Algebra, Berlin, New York: Springer-Verlag
• Chang, Chen Chung; Keisler, H. Jerome (1989) [1973], Model Theory, Elsevier, ISBN 978-0-7204-0692-4
• Diestel, Reinhard (2005) [1997], Graph Theory, Graduate Texts in Mathematics, 173 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Mathematical Logic (2nd ed.), New York: Springer, ISBN 978-0-387-94258-2
• Hinman, P. (2005), Fundamentals of Mathematical Logic, A K Peters, ISBN 978-1-56881-262-5
• Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-30442-9
• Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6
• Marker, David (2002), Model Theory: An Introduction, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98760-6
• Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98655-5
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Rothmaler, Philipp (2000), Introduction to Model Theory, London: CRC Press, ISBN 978-90-5699-313-9

External links

• Semantics section in Classical Logic (an entry of Stanford Encyclopedia of Philosophy)