1.10: Implicación lógica

A primera vista parece que una gran parte de las matemáticas se puede desglosar en responder preguntas de la forma: Si sé que esta afirmación es cierta, ¿es necesariamente el caso de que esta otra afirmación sea cierta? En esta sección formalizaremos esa pregunta.

Definición 1.9.1. Supongamos que\(\Delta\) y\(\Gamma\) son conjuntos de\(\mathcal{L}\) -fórmulas. Diremos que \(\Delta\)lógicamente implica\(\Gamma\) y escribiremos\(\Delta \models \Gamma\) si por cada\(\mathcal{L}\) -estructura\(\mathfrak{A}\), si\(\mathfrak{A} \models \Delta\), entonces\(\mathfrak{A} \models \Gamma\).

Esta definición es un poco complicada. Dice que si\(\Delta\) es cierto en\(\mathfrak{A}\), entonces\(\Gamma\) es cierto en\(\mathfrak{A}\). Recuerde,\(\Delta\) para ser verdad en\(\mathfrak{A}\), debe darse el caso que\(\mathfrak{A} \models \Delta \left[ s \right]\) para cada asignación función\(s\). Ver Ejercicio 4.

Si\(\Gamma = \{ \gamma \}\) es un conjunto que consiste en una sola fórmula, vamos a escribir\(\Delta \models \gamma\) en lugar de la oficial\(\Delta \models \{ \gamma \}\).

Definición 1.9.2. Se dice que una\(\mathcal{L}\) fórmula\(\phi\) es válida si\(\emptyset \models \phi\), en otras palabras, si\(\phi\) es verdadera en cada\(\mathcal{L}\) estructura con cada función de asignación\(s\). En este caso, escribiremos\(\models \phi\).

Chafia: No parece que sea fácil comprobar si\(\Delta \models \Gamma\). Hacerlo directamente significaría que tendríamos que examinar cada posible\(\mathcal{L}\) -estructura y cada función de asignación posible\ (s\, de las cuales habrá muchas.

También estoy seguro de que te has dado cuenta de que este símbolo de doble giro\(\models\),, está recibiendo mucho uso. Sólo recuerda que si hay una estructura a la izquierda,\(\mathfrak{A} \models \sigma\), estamos discutiendo la verdad en una sola estructura. Si hay un conjunto de oraciones a la izquierda\(\Gamma \models \sigma\), entonces estamos discutiendo implicaciones lógicas.

Ejemplo 1.9.3. Dejar\(\mathcal{L}\) ser el lenguaje que consiste en un solo símbolo de relación binaria,\(P\), y dejar que\(\sigma\) sea la oración\(\left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right)\). Demostramos que\(\sigma\) es válido.

Así que vamos\(\mathfrak{A}\) a ser cualquier\(\mathcal{L}\) -estructura y dejar\(s : Vars \rightarrow A\) ser cualquier función de asignación. Debemos demostrar que

\[\mathfrak{A} \models \left[ \left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right) \right] \left[ s \right].\]

Supongamos que\(\mathfrak{A} \models \left( \exists y \forall x P \left( x, y \right) \right) \left[ s \right]\), sabemos que hay un elemento del universo,\(A\), tal que\(\mathfrak{A} \models \forall x P \left( x, y \right) \left[s \left[ y | a \right] \right]\). Y así, nuevamente por la definición de satisfacción, sabemos que si\(b\) es algún elemento de\(A\),\(\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ y | a \right] \right) \left[ x | b \right] \right]\). Si perseguimos a través de la definición de satisfacción (Definición 1.7.4) y de las diversas funciones de asignación, esto significa que para nuestro fijo\(a\), el par ordenado\(\left( b, a \right) \in P^\mathfrak{A}\) para cualquier elección de\(b \in A\).

Tenemos que demostrarlo\(\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]\). Como la declaración de interés es universal, debemos demostrar que, si\(c\) es un elemento arbitrario de\(A\)\(\mathfrak{A} \models \exists y P \left( x, y \right) \left[ s \left[ x | c \right] \right]\),, lo que significa que debemos producir un elemento del universo,\(d\), tal que\(\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ x | c \right] \right) \left[ y | d \right] \right]\). Nuevamente, a partir de la definición de satisfacción esto quiere decir que debemos encontrar\(d \in A\) tal que\(\left( c, d \right) \in P^\mathfrak{A}\). Afortunadamente, tenemos tal\(d\) en la mano, es decir\(a\). Como sabemos,\(\left( c, a \right) \in P^\mathfrak{A}\), lo hemos demostrado\(\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]\), y estamos terminados.

Ejercicios

1. Demuéstralo\(\{ \alpha, \alpha \rightarrow \beta \} \models \beta\) para cualquier fórmula\(\alpha\) y\(\beta\). Traducir este resultado en everyday Inglés. O noruego, si lo prefieres.
2. Demostrar que la fórmula\(x = x\) es válida. Demostrar que la fórmula no\(x = y\) es válida. ¿Qué puedes probar sobre la fórmula\(\neg x = y\) en términos de validez?
3. Supongamos que\(\phi\) es una\(\mathcal{L}\) fórmula -y\(x\) es una variable. Demostrar que\(\phi\) es válido si y sólo si\(\left( \forall x \right) \left( \phi \right)\) es válido. Así, si\(\phi\) tiene variables libres\(x\),\(y\), y\(z\),\(\phi\) será válido si y sólo si\(\forall x \forall y \forall z \phi\) es válido. A la sentencia\(\forall x \forall y \forall z \phi\) se le llama el cierre universal de\(\phi\).
4. a) Supongamos que\(\models \left( \phi \rightarrow \psi \right)\). \(\phi \models \psi\)Demuéstralo.
   b) Supongamos que\(\phi\) es\(x < y\) y\(\psi\) es\(z < w\). \(\phi \models \psi\)Demuéstralo pero\(\not\models \left( \phi \rightarrow \psi \right)\). (El corte a través\(\models\) significa “no implica lógicamente”.)
   
   [Este ejercicio muestra que las dos formas posibles de definir la equivalencia lógica no son equivalentes. La forma fuerte de la definición dice eso\(\phi\) y\(\psi\) son lógicamente equivalentes si\(\models \left( \phi \rightarrow \psi \right)\) y\(\models \left( \psi \rightarrow \phi \right)\). La forma débil de la definición establece que\(\phi\) y\(\psi\) son lógicamente equivalentes si\(\phi \models \psi\) y\(\psi \models \phi\).]