1.8: La verdad en una estructura

Es en el último momento para unir la sintaxis y la semántica. Tenemos algunas reglas formales sobre lo que constituye un lenguaje, y podemos identificar los términos, fórmulas y oraciones de un idioma. También podemos identificar\(\mathcal{L}\) -estructuras para un idioma determinado\(\mathcal{L}\). En esta sección decidiremos qué significa decir que una\(\mathcal{L}\) -fórmula\(\phi\) es verdadera en una\(\mathcal{L}\) -estructura\(\mathfrak{A}\).

Para iniciar el proceso de vinculación de los símbolos con las estructuras, introduciremos funciones de asignación. Estas funciones de asignación formalizarán lo que significa interpretar un término o una fórmula en una estructura.

Definición 1.7.1. Si\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura, una función de asignación de variables into\(\mathfrak{A}\) es una función\(s\) que asigna a cada variable un elemento del universo\(A\). Entonces una función de asignación de variables en\(\mathfrak{A}\) es cualquier función con dominio\(Vars\) y codominio\(A\).

Las funciones de asignación variable no necesitan ser inyectoras o biyectivas. Por ejemplo, si trabajamos con\(\mathcal{L}_{NT}\) y la estructura estándar\(\mathfrak{N}\), entonces la función\(s\) definida por\(s \left( v_i \right) = i\) es una función de asignación variable, como es la función\(s'\) definida por

\[s' \left( v_i \right) = \: \text{the smallest prime number that does not divide} \: i.\]

Tendremos ocasión de querer fijar el valor de la función de asignación\(s\) para ciertas variables.

Definición 1.7.2. Si\(s\) es una función de asignación de variables en\(\mathfrak{A}\) y\(x\) es una variable y\(a \in A\), entonces\(s \left[ x | a \right]\) es la función de asignación de variables en\(\mathfrak{A}\) definida de la siguiente manera:

\[s \left[ x | a \right] = \begin{cases} s \left( v \right) \: \: \: \text{if} \: v \: \text{is a variable other than} \: x \\ a \: \: \: \: \: \: \: \: \: \: \: \text{if} \: v \: \text{is the variable} \: x \end{cases}\]

Llamamos a la función\(s \left[ x | a \right]\) una \(x\)-modificación de la función de asignación\(s\).

Entonces una\(x\) -modificación de\(s\) es igual\(s\), excepto que la variable\(x\) está asignada a un elemento particular del universo.

Lo que haremos a continuación es extender una función de asignación de variables\(s\) a una función de asignación de términos,\(\bar{s}\). Esta función asignará un elemento del universo a cada término del lenguaje\(\mathcal{L}\).

Definición 1.7.3. Supongamos que\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura y\(s\) es una función de asignación de variables en\(\mathfrak{A}\). La función\(\bar{s}\), llamada función de asignación de términos generada por\(s\), es la función con dominio que consiste en el conjunto de\(\mathcal{L}\) -terms y codomain\(A\) definidos recursivamente de la siguiente manera:

1. Si\(t\) es una variable,\(\bar{s} \left( t \right) = s \left( t \right)\).
2. Si\(t\) es un símbolo constante\(c\), entonces\(\bar{s} \left( t \right) = c^\mathfrak{A}\).
3. Si\(t : \equiv f t_1 t_2 \ldots t_n\), entonces\(\bar{s} \left( t \right) = f^\mathfrak{A} \left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right)\).

Si bien nos interesará primordialmente la verdad de las oraciones, primero describiremos la verdad (o satisfacción) para fórmulas arbitrarias, relativas a una función de asignación.

Definición 1.7.4. Supongamos que\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura,\(\phi\) es una\(\mathcal{L}\) -fórmula, y\(s : Vars \rightarrow A\) es una función de asignación. Diremos que \(\mathfrak{A}\)satisface\(\phi\) con asignación\(s\), y escribiremos\(\mathfrak{A} \models \phi \left[ s \right]\), en las siguientes circunstancias:

1. Si\(\phi : \equiv t_1 t_2\) y\(\bar{s} \left( t_1 \right)\) es el mismo elemento del universo\(A\) que\(\bar{s} \left( t_2 \right)\), o
2. Si\(\phi : \equiv R t_1 t_2 \ldots t_n\) y\(\left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right) \in R^\mathfrak{A}\), o
3. Si\(\phi : \equiv \left( \neg \alpha \right)\) y\(\mathfrak{A} \not\models \alpha \left[ s \right]\), (donde\(\not\models\) significa “no satisface”), o
4. Si\(\phi : \equiv \left( \alpha \lor \beta \right)\) y\(\mathfrak{A} \models \alpha \left[ s \right]\), o\(\mathfrak{A} \models \beta \left[ s \right]\) (o ambos), o
5. Si\(\phi : \equiv \left( \forall x \right) \left( \alpha \right)\) y, para cada elemento\(a\) de\(A\),\(\mathfrak{A} \models \alpha \left[ s \left( x | a \right) \right]\).

Si\(\Gamma\) es un conjunto de\(\mathcal{L}\) -fórmulas, decimos que\(\mathfrak{A}\) satisface\(\Gamma\) con la asignación\(s\), y escribimos\(\mathfrak{A} \models \Gamma \left[ s \right]\) si para cada una\(\gamma \in \Gamma\),\(\mathfrak{A} \models \gamma \left[ s \right]\).

Chafia: Observe que\(\models\) el símbolo no forma parte del lenguaje\(\mathcal{L}\). Más bien,\(\models\) es un símbolo metalingüístico que utilizamos para hablar de fórmulas en el lenguaje y estructuras para el lenguaje.

Chafia: ¡Observe también que por fin hemos atado la sintaxis y semántica de nuestro lenguaje! La definición anterior es el lugar donde formalmente ponemos los significados sobre los símbolos que usaremos, de modo que eso\(\lor\) significa “o” y\(\forall\) significa “para todos”.

Ejemplo 1.7.5. Trabajemos con el lenguaje vacío, así que no\(\mathcal{L}\) tiene símbolos constantes, ni símbolos de función, ni símbolos de relación. Entonces una\(\mathcal{L}\) -estructura es simplemente un conjunto no vacío, y consideremos la\(\mathcal{L}\) -estructura\(\mathfrak{A}\), dónde\(A = \{ \text{Humphrey, Ingrid}\}\). Considera la fórmula\(x = y\) y la función de asignación\(s\), donde\(s \left( x \right)\) está Humphrey y también\(s \left( y \right)\) es Humphrey. Si nos preguntamos si\(\mathfrak{A} \models x = y \left[ s \right]\), tenemos que comprobar si\(bar{s} \left( x \right)\) es el mismo elemento de\(A\) as\(\bar{s} \left( y \right)\). Dado que los dos objetos son idénticos, la fórmula es verdadera.

Para enfatizar esto, la fórmula\(x = y\) puede ser cierta en algunos universos con algunas funciones de asignación. Si bien las variables\(x\) y\(y\) son distintas, la verdad o falsedad de la fórmula depende no de las variables (que no son iguales) sino más bien, de qué elementos de la estructura denotan las variables, los valores de las variables (que son iguales para este ejemplo). Por supuesto, hay otras funciones de asignación y otras estructuras que hacen falsa nuestra fórmula. Estamos seguros de que se te ocurren algunos.

Para hablar de la verdad o falsedad de una oración en una estructura, tomaremos nuestra definición de satisfacción relativa a una función de asignación y probaremos que para las oraciones, la elección de la función de asignación es intrascendente. Entonces diremos que una oración\(\sigma\) es verdadera en una estructura\(\mathfrak{A}\) si y sólo si\(\mathfrak{A} \models \sigma \left[ s \right]\) para alguna (y por lo tanto todas) funciones de asignación de variables\(s\).

Chafia: El siguiente par de pruebas son pruebas por inducción sobre la complejidad de términos o fórmulas. Es posible que desee releer la prueba del Teorema 1.4.2 si les resulta difícil.

Lema 1.7.6. Supongamos que\(s_1\) y\(s_2\) son funciones de asignación de variables en una estructura\(\mathfrak{A}\) tal que\(s_1 \left( v \right) = s_2 \left( v \right)\) para cada variable\(v\) en el término\(t\). Entonces\(\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)\).

Comprobante. Utilizamos la inducción sobre la complejidad del término\(t\). Si\(t\) es un símbolo de variable o constante, el resultado es inmediato. Si\(t : \equiv f t_1 t_2 \ldots t_n\), entonces en\(\bar{s_1} \left( t_i \right) = \bar{s_2} \left( t_i \right)\) cuanto a\(1 \leq i \leq n\) por la hipótesis inductiva, la definición de\(\bar{s_1} \left( t \right)\) y la definición de\(\bar{s_2} \left( t \right)\) son idénticas, y por lo tanto\(\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)\).

Proposición 1.7.7. Supongamos que\(s_1\) y\(s_2\) son funciones de asignación de variables en una estructura\(\mathfrak{A}\) tal que\(s_1 \left( v \right) = s_2 \left( v \right)\) por cada variable libre\(v\) en la fórmula\(\phi\). Entonces\(mathfrak{A} \models \phi \left[ s_1 \right]\) si y sólo si\(\mathfrak{A} \models \phi \left[ s_2 \right]\).

Comprobante. Utilizamos la inducción en la complejidad de\(\phi\). Si\(\phi : \equiv = t_1 t_2\), entonces las variables libres de\(\phi\) son exactamente las variables que ocurren en\(\phi\). Así Lemma 1.7.6 nos dice eso\(\bar{s_1} \left( t_1 \right) = \bar{s_2} \left( t_1 \right)\) y\(\bar{s_1} \left( t_2 \right) = \bar{s_2} \left( t_2 \right)\), es decir, que son el mismo elemento del universo\(A\), así que\(\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_1 \right]\) si y sólo si\(\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_2 \right]\), según sea necesario.

El otro caso base, si\(\phi : \equiv R t_1 t_2 \ldots t_n\), es similar y se deja como parte del Ejercicio 6.

Para iniciar la primera cláusula inductiva, si\(\phi : \equiv \neg \alpha\), observe que las variables libres de\(\phi\) son exactamente las variables libres de\(\alpha\), así\(s_1\) y\(s_2\) acordar las variables libres de\(\alpha\). Por la hipótesis inductiva,\(\mathfrak{A} \models \alpha \left[ s_1 \right]\) si y sólo si\(\mathfrak{A} \models \alpha \left[ s_2 \right]\), y así (por la definición de satisfacción),\(\mathfrak{A} \models \phi \left[ s_1 \right]\) si y sólo si\(\mathfrak{A} \models \phi \left[ s_2 \right]\). La segunda cláusula inductiva, si\(\phi : \equiv \alpha \lor \beta\), es otra parte del Ejercicio 6.

Si\(\phi : \equiv \left( \forall x \right) \left( \alpha \right)\), primero notamos que la única variable que podría ser libre en\(\alpha\) que no es libre en\(\phi\) es\(x\). Así, si\(a \in A\), la asignación funciona\(s_1 \left[ x | a \right]\) y\(s_2 \left[ x | a \right]\) acuerda todas las variables libres de\(\alpha\). Por lo tanto, por hipótesis inductiva, para cada uno\(a \in A\),\(\mathfrak{A} \ = \alpha \left[ s_1 \left[ x | a \right] \right]\) si y sólo si\(\mathfrak{A} \models \alpha \left[ s_2 \left[ x | a \right] \right]\). Entonces, por Definición 1.7.4,\(\mathfrak{A} \models \phi \left[ s_1 \right]\) si y solo si\ (\ mathfrak {A}\ models\ phi\ left [s_2\ right] |). Esto termina la última cláusula inductiva, y nuestra prueba.

Corolario 1.7.8 Si\(\sigma\) es una oración en el idioma\(\mathcal{L}\) y\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura, ya sea\(\mathfrak{A} \models \sigma \left[ s \right]\) para todas las funciones de asignación\(s\), o\(\mathfrak{A} \models \sigma \left[ s \right]\) para ninguna función de asignación\(s\).

Comprobante. No hay variables libres en\(\sigma\), así que si\(s_1\) y\(s_2\) son dos funciones de asignación, coinciden en todas las variables libres de\(\sigma\), simplemente no hay tantas de ellas. Entonces por la Proposición 1.7.7,\(\mathfrak{A} \models \sigma \left[ s_1 \right]\) si y sólo si\(\mathfrak{A} \models \sigma \left[ s_2 \right]\), según sea necesario.

Definición 1.7.9. Si\(\phi\) es una fórmula en el lenguaje\(\mathcal{L}\) y\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura, decimos que\(\mathfrak{A}\) es un modelo de\(\phi\), y escribimos\(\mathfrak{A} \models \phi\), si y sólo si\(\mathfrak{A} \models \phi \left[ s \right]\) para cada función de asignación\(s\). Si\(\Phi\) es un conjunto de\(\mathcal{L}\) -fórmulas, diremos que\(\mathfrak{A}\) modela\(\Phi\), y escribiremos\(\mathfrak{A} \models \Phi\), si y solo si\(\mathfrak{A} \models \phi\) para cada uno\(\phi \in \Phi\).

Observe que si\(\sigma\) es una oración, entonces\(\mathfrak{A} \models \sigma\) si y sólo si\(\mathfrak{A} \models \sigma \left[ s \right]\) para alguna función de asignación\(s\). En este caso diremos que la sentencia\(\sigma\) es verdadera en\(\mathfrak{A}\).

Ejemplo 1.7.10. Vamos a trabajar\(\mathcal{L}_{NT}\), y vamos

\[\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right)\]

ser la estructura estándar. Dejar\(s\) ser la función de asignación de variables que asigna\(v_i\) al número\(2i\). Ahora deja que la fórmula\(\phi \left( v_1 \right)\) sea\(v_1 + v_2 = SSSS0\).

Para demostrarlo\(\mathfrak{N} \models \phi \left[ s \right]\), fíjese que

\[\begin{align} \bar{s} \left( v_1 + v_1 \right) \: &\text{is} \: +^\mathfrak{N} \left( \bar{s} \left( v_1 \right), \bar{s} \left( v_1 \right) \right) \\ &\text{is} \: +^\mathfrak{N} \left( 2, 2 \right) \\ &\text{is} \: 4 \end{align}\]

mientras

\[\begin{align} \bar{s} \left( SSSS0 \right) \: &\text{is} \: S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( 0^\mathfrak{N} \right) \right) \right) \right) \\ &\text{is} \: 4 \end{align}\]

Ahora bien, en el mismo escenario, considere\(\sigma\), la frase

\[\left( \forall v_1 \right) \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_1 \right),\]

que establece que todo está parejo. [Eso es difícil de ver a menos que sepas buscar eso\(\neg \left( \forall v_2 \right) \neg\) y leerlo como\(\left( \exists v_2 \right)\). Véase el último par de párrafos de esta sección.] Sabes que\(\sigma\) es falso en la estructura estándar, pero para mostrar cómo va el argumento formal, deja que\(s\) sea cualquier función de asignación de variables y fíjate que

\[\begin{align} \mathfrak{N} \models \sigma \left[ s \right] \: &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \models \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \not\models \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \text{there is a } b \in \mathbb{N}, \: \mathfrak{N} \models v_1 = v_2 + v_2 \: s \left[ v_1 | a \right] \left[ v_2 | b \right]. \end{align}\]

Ahora bien, si consideramos el caso cuando\(a\) es el número 3, está perfectamente claro que no existe tal\(b\), así lo hemos demostrado\(\mathfrak{N} \not\models \sigma \left[ s \right]\). Entonces, por la Definición 1.7.9, vemos que la oración\(\sigma\) es falsa en la estructura estándar. Como bien sabías.

Cuando te introdujeron en la lógica simbólica, probablemente te dijeron que había cinco conectivos. En las matemáticas que has aprendido recientemente, has estado usando dos cuantificadores. Esperamos que se hayan dado cuenta de que no hemos utilizado todos esos símbolos en este libro, pero ahora es el momento de hacer que esos símbolos estén disponibles. Sin embargo, en lugar de agregar los símbolos a nuestro idioma, los presentaremos como abreviaturas. Esto nos ayudará a mantener nuestras pruebas un poco menos complejas (ya que nuestras pruebas inductivas tendrán menos casos) pero aún así nos permitirá usar los símbolos más familiares, al menos como taquigrafía.

Así, aceptemos utilizar las siguientes abreviaturas en la construcción de\(\mathcal{L}\) -fórmulas: Escribiremos en\(\left( \alpha \land \beta \right)\) lugar de\(\left( \neg \left( \left( \neg \alpha \right) \lor \left( \neg \beta \right) \right) \right)\),\(\left( \alpha \rightarrow \beta \right)\) en lugar de\(\left( \left( \neg \alpha \right) \lor \beta \right)\), y\(\left( \alpha \leftrightarrow \beta \right)\) en lugar de\(\left( \left( \alpha \rightarrow \beta \right) \land \left( \beta \rightarrow \alpha \right) \right)\). También presentaremos nuestro cuantificador existencial faltante como abreviatura, escribiendo\(\left( \exists x \right) \left( \alpha \right)\) en lugar de\(\left( \neg \left( \forall x \right) \left( \neg \alpha \right) \right)\). Es un ejercicio fácil comprobar que los conectivos introducidos\(\land\),\(\rightarrow\), y\(\leftrightarrow\) comportarse como se esperaría que lo hicieran. Así\(\mathfrak{A} \models \left( \alpha \land \beta \right) \left[ s \right]\) si y sólo si ambos\(\mathfrak{A} \models \alpha \left[ s \right]\) y\(\mathfrak{A} \models \beta \left[ s \right]\). El cuantificador existencial es sólo un poco más difícil. Ver Ejercicio 7.

Ejercicios

1. Sugerimos después de la Definición 1.5.3 que la verdad o falsedad de las oraciones\(1 + 1 = 2\) y\(\left( \forall x \right) \left( x + 1 = x \right)\) podría no ser automática. Encuentra una estructura para el lenguaje que ahí se discute que haga\(1 + 1 = 2\) verdadera la oración. Encuentra otra estructura donde\(1 + 1 = 2\) sea falsa. Demuestre sus aseveraciones. Entonces demuestra que puedes encontrar una estructura donde\(\left( \forall x \right) \left( x + 1 = x \right)\) es verdadera, y otra estructura donde es falsa.
2. Que el lenguaje\(\mathcal{L}\) sea\(\{ S, C \}\), donde\(S\) es un símbolo de función unario y\(<\) es un símbolo de relación binaria. \(\phi\)Déjese ser la fórmula\(\left( \forall x \right) \left( \exists y \right) \left( Sx < y \right)\).
   (a) Encontrar una\(\mathcal{L}\) -estructura\(\mathfrak{A}\) tal que\(\mathfrak{A} \models \phi\).
   (b) Encontrar una\(\mathcal{L}\) -estructura\(\mathfrak{B}\) tal que\(\mathfrak{B} \models \left( \neg \phi \right)\).
   (c) Demostrar que su respuesta a la parte (a) o a la parte (b) es correcta.
   (d) Escribir una\(\mathcal{L}\) -oración que sea verdadera en una estructura\(\mathfrak{A}\) si y sólo si el universo\(A\) de\(\mathfrak{A}\) consta exactamente de dos elementos.
3. Consideremos el lenguaje y la estructura del Ejemplo 1.6.4. Escribe dos oraciones no triviales en el idioma, una de las cuales es verdadera en la estructura y una de las cuales (no la negación de la primera) es falsa en la estructura. Justifica tus aseveraciones.
4. Considera la frase\(\sigma\):\(\left( \forall x \right) \left( \exists y \right) \left[ x < y \rightarrow x + 1 \neg y \right]\). Encuentra dos estructuras para un lenguaje adecuado, una de las cuales hace\(\sigma\) realidad, y la otra hace\(\sigma\) falsa.
5. Un poco más de taquigrafía. Supongamos que el lenguaje\(\mathcal{L}\) contiene el símbolo de relación binaria\(\in\), que pretendes usar para significar la relación elementhood (así\(p \in q\) significará que\(p\) es un elemento de\(q\)). A menudo, es el caso que se quiere afirmar que\(\phi \left( x \right)\) es cierto para cada elemento de un conjunto\(b\). Por supuesto, para ello podrías escribir
   \[\left( \forall x \right) \left[ \left( x \in b \right) \rightarrow \phi \left( x \right) \right].\]
   Vamos a abreviar esta fórmula como
   \[\left( \forall x \in b \right) \left( \phi \left( x \right) \right).\]
   De igual manera,\(\left( \exists x \in b \right) \left( \phi \left( x \right) \right)\) será una abreviatura para la fórmula\(\left( \exists x \right) \left[ \left( x \in b \right) \land \phi \left( x \right) \right]\). Observe que esta fórmula tiene una conjunción donde la fórmula anterior tuvo una implicación!. Eso lo hacemos solo para ver si estás prestando atención. (Bueno, si piensas en lo que se supone que significan las abreviaturas, verás que el cambio es necesario. Tendremos que hacer otra cosa solo para ver si estás prestando atención.)
   Ahora supongamos que\(\mathfrak{A}\) es una estructura para el lenguaje de la teoría de conjuntos. Así\(\mathcal{L}\) tiene sólo este símbolo de relación binaria\(\in\),, que se interpreta como la relación elementhood. Supongamos, además, que
   \[A = \{ u, v, w, \{ u \}, \{ u, v \}, \{ u, v, w \} \}.\]
   en particular, noten que no hay elemento\(x\) de\(A\) tal que\(x \in x\). Considera la oración
   \[\left( \forall y \in y \right) \left( \exists x \in x \right) \left( x = y \right).\]
   ¿Esta oración es verdadera o falsa en\(\mathfrak{A}\)?
6. Rellena los datos para completar el comprobante de la Proposición 1.7.7.
7. Demostrar que\(\mathfrak{A} \models \left( \exists x \right) \left( \alpha \right) \left[ s \right]\) si y sólo si hay un elemento\(a \in A\) tal que\(\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]\).