5.9: Estructuras para Lenguas de Primer Orden

Template:MathJaxZach

Los lenguajes de primer orden son, por sí mismos, no interpretados: los símbolos constantes, los símbolos de función y los símbolos predicados no tienen un significado específico asociado a ellos. Los significados se dan especificando la estructura. Especifica el dominio, es decir, los objetos que los símbolos constantes escogen, los símbolos de función operan y los cuantificadores se encuentran en el rango. Además, especifica qué símbolos constantes escogen qué objetos, cómo un símbolo de función asigna objetos a objetos y a qué objetos se aplican los símbolos de predicado. Las estructuras son la base de nociones semánticas en la lógica, e.g., la noción de consecuencia, validez, satisfacción. Se les llama de diversas maneras “estructuras”, “interpretaciones” o “modelos” en la literatura.

Definición\(\PageIndex{1}\): Structures

Una estructura\(\Struct M\), para un lenguaje\(\Lang{L}\) de lógica de primer orden consta de los siguientes elementos:

1. Dominio: un conjunto no vacío,\(\Domain M\)

2. Interpretación de símbolos constantes: para cada símbolo constante\(c\) de\(\Lang{L}\), un elemento\(\Assign{c}{M} \in \Domain M\)

3. Interpretación de símbolos predicados: para cada símbolo de predicado\(n\) -lugar\(R\) de\(\Lang{L}\) (distinto de\(\eq[][]\)), una relación\(n\) -lugar\(\Assign{R}{M} \subseteq \Domain{M}^n\)

4. Interpretación de símbolos de función: para cada símbolo\(f\) de función\(n\) -place de\(\Lang{L}\), una función\(n\) -place\(\Assign{f}{M} \colon \Domain{M}^n \to \Domain{M}\)

Ejemplo\(\PageIndex{1}\)

Una estructura\(\Struct M\) para el lenguaje de la aritmética consiste en un conjunto, un elemento de\(\Domain M\)\(\Assign{\Obj 0}{M}\), como interpretación del símbolo constante\(\Obj 0\), una función de un solo lugar\(\Assign{\Obj \prime}{M} \colon \Domain{M} \to \Domain M\), dos funciones de dos lugares\(\Assign{\Obj +}{M}\) y\(\Assign{\Obj \times}{M}\), ambos\(\Domain M^2 \to \Domain M\), y una relación de dos lugares\(\Assign{\Obj <}{M} \subseteq \Domain{M}^2\).

Un ejemplo obvio de tal estructura es el siguiente:

1. \(\Domain N = \Nat\)

2. \(\Assign{\Obj 0}{N} = 0\)

3. \(\Assign{\Obj \prime}{N}(n) = n + 1\)para todos\(n \in \Nat\)

4. \(\Assign{\Obj +}{N}(n, m) = n + m\)para todos\(n, m \in \Nat\)

5. \(\Assign{\Obj \times}{N}(n, m) = n\cdot m\)para todos\(n, m \in \Nat\)

6. \(\Assign{\Obj <}{N} = \Setabs{\tuple{n, m}}{n \in \Nat, m \in \Nat, n < m}\)

La estructura\(\Struct N\) para\(\Lang L_A\) así definida se llama el modelo estándar de aritmética, porque interpreta las constantes no lógicas de\(\Lang L_A\) exactamente cómo se esperaría.

Sin embargo, hay muchas otras estructuras posibles para\(\Lang L_A\). Por ejemplo, podríamos tomar como dominio el conjunto\(\Int\) de enteros en lugar de\(\Nat\), y definir las interpretaciones de\(\Obj 0\),,,\(\Obj \prime\),\(\Obj +\)\(\Obj \times\), en\(\Obj <\) consecuencia. Pero también podemos definir estructuras para las\(\Lang L_A\) que no tienen nada que ver ni remotamente con los números.

Ejemplo\(\PageIndex{2}\)

Una estructura\(\Struct M\) para el lenguaje\(\Lang L_Z\) de la teoría de conjuntos requiere solo una relación de conjunto y un solo lugar de dos. Entonces técnicamente, por ejemplo, el conjunto de personas más la relación “\(x\)es mayor que\(y\)” podría usarse como estructura para\(\Lang L_Z\), así como\(\Nat\) junto con\(n \ge m\) para\(n, m \in \Nat\).

Una estructura particularmente interesante para\(\Lang L_Z\) en la que los elementos del dominio son realmente conjuntos, y la interpretación de\(\Obj \in\) realmente es la relación “\(x\)es un elemento de\(y\)” es la estructura\(\Struct{ {HF} }\) de conjuntos hereditariamente finitos:

1. \(\Domain{ { {HF} } } = \emptyset \cup \Pow{\emptyset} \cup \Pow{\Pow{\emptyset}} \cup \Pow{\Pow{\Pow{\emptyset}}} \cup \dots\);

2. \(\Assign{\Obj \in}{ { {HF} } } = \Setabs{\tuple{x, y}}{x, y \in \Domain{ { {HF} } }, x \in y}\).

Las estipulaciones que hacemos en cuanto a lo que cuenta como estructura impactan nuestra lógica. Por ejemplo, la elección de evitar dominios vacíos asegura, dado el relato habitual de satisfacción (o verdad) para las oraciones cuantificadas,\(\lexists{x}{(A(x) \lor \lnot A(x))}\) es decir, válido, es decir, una verdad lógica. Y la estipulación de que todos los símbolos constantes deben referirse a un objeto en el dominio asegura que la generalización existencial es un patrón sonoro de inferencia:\(A(a)\), por lo tanto\(\lexists{x}{A(x)}\). Si permitimos que los nombres se refieran fuera del dominio, o que no se refirieran, entonces estaríamos en camino hacia una lógica libre, en la que la generalización existencial requiere una premisa adicional:\(A(a)\) y\(\lexists{x}{\eq[x][a]}\), por lo tanto\(\lexists{x}{A(x)}\).