2.7: Propiedades de Nuestro Sistema Deductivo

Habiendo pasado por toda la molestia de establecer nuestro sistema deductivo, ahora probaremos algunas cosas tanto dentro como sobre ese sistema. Primero, demostraremos que podemos demostrar, en nuestro sistema deductivo, que la igualdad es una relación de equivalencia.

Teorema 2.7.1.

1. \(\vdash x = x\).
2. \(\vdash x = y \rightarrow y = x\).
3. \(\vdash \left( x = y \land y = z \right) \rightarrow x = z\).

Prueba. Demostramos que podemos encontrar deducciones que establecen que\(=\) es reflexivo, simétrico y transitivo a su vez.

1. Este es un axioma lógico de tipo (E1).
2. Aquí está la deducción necesaria. Observe que las anotaciones fuera a la derecha se listan únicamente como una ayuda al lector.
   \[\left[ x = y \land x = x \right] \rightarrow \left[ x = x \rightarrow y = x \right] \tag{E3}\]
   \[x = x \tag{E1}\]
   \[x = y \rightarrow y = x. \tag{PC}\]
3. Nuevamente, presentamos una deducción:
   \[\left[ x = x \land y = z \right] \rightarrow \left[ x = y \rightarrow x = z \right] \tag{E3}\]
   \[x = x \tag{E1}\]
   \[\left( x = y \land y = z \right) \rightarrow x = z. \tag{PC}\]

Chafia: Observe que hemos hecho un poco más que demostrar que la igualdad es una relación de equivalencia. (Diablos, lo has sabido desde cuarto grado.) Más bien, hemos demostrado que nuestro sistema deductivo, con los axiomas y reglas de inferencia que se han esbozado en este capítulo, es lo suficientemente poderoso como para demostrar que la igualdad es una relación de equivalencia. Habrá un poco de “nuestro sistema deductivo es lo suficientemente fuerte como para hacer tal y tal” en las páginas por venir.

Ahora probamos algunas propiedades generales de nuestro sistema deductivo. Comenzamos con un lema que parece algo problemático, pero nos ayudará a pensar un poco más detenidamente en lo que nuestras deducciones hacen por nosotros.

Lema 2.7.2\(\Sigma \vdash \theta\) si y solo si\(\Sigma \vdash \forall x \theta\).

Prueba. Primero, supongamos que\(\Sigma \vdash \theta\). Aquí hay una deducción\(\Sigma\) de\(\forall x \theta\):

\[\begin{array}{lr} \vdots & \text{Deduction of} \: \theta \\ \theta & \\ \left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right] \rightarrow \theta & \text{(PC)} \\ \left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right] \rightarrow \left( \forall x \theta \right) & \text{(QR)} \\ \forall x \theta. & \text{(PC)} \end{array}\]

Hay un par de cosas que señalar sobre esta prueba. El primer uso de (PC) se justifica por el hecho de que si\(\theta\) es cierto, entonces (cualquier cosa\(\rightarrow \theta\)) también es cierto. El segundo uso de (PC) depende del hecho de que\(\left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right]\) es una tautología, y por lo tanto\(\forall x \theta\) es una consecuencia proposicional de la implicación. En cuanto al paso (QR) de la deducción, advertir que la variable no\(x\) es libre en la oración\(\left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right]\), haciendo legítimo el uso de la regla cuantificadora.

Ahora, supongamos eso\(\Sigma \vdash \forall x \theta\). Aquí hay una deducción\(\Sigma\) de\(\theta\) (recordar que\(\theta_x^x\) es\(\theta\)):

\[\begin{array}{lr} \vdots & \text{Deduction of} \: \forall x \theta \\ \forall x \theta & \\ \forall x \theta \rightarrow \theta_x^x & \text{(Q1)} \\ \theta_x^x. & \text{(PC)} \end{array}\]

Así\(\Sigma \vdash \theta\) si y sólo si\(\Sigma \vdash \forall x \theta\).

Aquí un ejemplo para mostrar lo extraño que podría parecer este lema. Supongamos que\(\Sigma\) consiste en la fórmula única\(x = \overline{5}\). Entonces ciertamente\(\Sigma \vdash x = \overline{5}\), y así, por el lema,\(\Sigma \vdash \left( \forall x \right) \left( x = \overline{5} \right)\). Podría sentirse tentado a decir que al asumir que\(x\) era igual a cinco, hemos demostrado que todo es igual a cinco. Pero eso no es exactamente lo que está pasando. Si\(x = \overline{5}\) es cierto en un modelo\(\mathfrak{A}\), eso significa que\(\mathfrak{A} \models x = \overline{5} \left[ s \right]\) para cada función de asignación\(s\). Y ya que para cada\(a \in A\), hay una función de asignación\(s\) tal que\(s \left( x \right) = a\), debe ser cierto que cada elemento de\(A\) es igual a 5, por lo que el universo\(A\) tiene un solo elemento, y todo es igual a 5. Entonces nuestra deducción de\(\left( \forall x \right) \left( x = \overline{5} \right)\) ha conservado la verdad, pero nuestra suposición fue mucho más fuerte de lo que aparecía a primera vista. Y la moraleja de nuestra historia es: Para que una fórmula sea cierta en una estructura, debe satisfacerse en esa estructura con cada función de asignación.

Lema 2.7.3. Supongamos que\(\Sigma \vdash \theta\). Entonces si\(\Sigma^\prime\) se forma tomando alguno\(\sigma \in \Sigma\) y sumando o borrando un cuantificador universal cuyo alcance es la fórmula completa,\(\Sigma^\prime \vdash \theta\).

Prueba. Esto se deduce inmediatamente de Lemma 2.7.2. Supongamos que\(\forall x \sigma\) está en\(\Sigma^\prime\). Por lo anterior,\(\Sigma^\prime \vdash sigma\). Entonces, dada una deducción de\(\Sigma\) de\(\theta\), para producir una deducción\(\Sigma^\prime\) de\(\theta\), primero anote una deducción\(\Sigma^\prime\) de\(\sigma\), y luego copie su deducción de\(\Sigma\) de\(\theta\). Habiendo ya establecido\(\sigma\), esta deducción será una deducción válida de\(\Sigma^\prime\).

La prueba en el caso que\(\forall x \sigma\) sea un elemento de\(\Sigma\) y se sustituya por\(\sigma\) in\(\Sigma^\prime\) es análoga.

Observe que una consecuencia de este lema es el hecho de que si sabemos\(\Sigma \vdash \theta\), podemos asumir (si nos gusta) que cada elemento de\(\Sigma\) es una oración: Al citar Lema 2.7.3 varias veces, podemos sustituir a cada uno\(\sigma \in \Sigma\) con su cierre universal.

Ahora vamos a demostrar que en al menos algún sentido, el sistema de deducciones que hemos desarrollado refleja el proceso que los matemáticos utilizan para probar teoremas. Supongamos que se le pidió probar el teorema: Si A es un cuadrado entonces A es un rectángulo. Una manera perfectamente razonable de atacar este teorema sería asumir que A es un cuadrado, y usando esa suposición, probar que A es un rectángulo. Pero fíjese que no se le ha pedido que demuestre que A es un rectángulo. ¡Se le pidió que demostrara una implicación! El Teorema de Deducción dice que existe una deducción\(\phi\) del supuesto\(\theta\) si y sólo si hay una deducción de la implicación\(\theta \rightarrow \phi\). (Un poco de notación: En lugar de escribir lo formalmente correcto\(\Sigma \cup \{ \theta \} \vdash \phi\), omitiremos las llaves y escribiremos\(\Sigma \cup \theta \vdash \phi\).)

Teorema 2.7.4 (El Teorema de la Deducción). Supongamos que\(\theta\) es una oración y\(\Sigma\) es un conjunto de fórmulas. Entonces\(\Sigma \cup \theta \vdash \phi\) si y sólo si\(\Sigma \vdash \left( \theta \rightarrow \phi \right)\).

Prueba. Primero, supongamos que\(\Sigma \vdash \left( \theta \rightarrow \phi \right)\). Entonces, como lo demostraría esa misma deducción\(\Sigma \cup \theta \vdash \left( \theta \rightarrow \phi \right)\), y como\(\Sigma \cup \theta \vdash \theta\) por una deducción unifilar, y como\(\phi\) es una consecuencia proposicional de\(\theta\) y\(\left( \theta \rightarrow \phi \right)\), eso lo sabemos\(\Sigma \cup \theta \vdash \phi\).

Para la dirección más difícil haremos uso de la Proposición 2.2.4. Supongamos que\(C = \{ \phi | \Sigma \vdash \left( \theta \rightarrow \phi \right) \}\). Si demostramos que\(C\) contiene\(\Sigma \cup \theta\),\(C\) contiene todos los axiomas de\(\Lambda\), y\(C\) se cierra bajo las reglas de inferencia como se señala en la Proposición 2.2.4, entonces por esa proposición lo sabremos\(\{ \phi | \Sigma \cup \theta \vdash \phi \} \subseteq C\). En otras palabras, lo sabremos si\(\Sigma \cup \theta \vdash \phi\), entonces\(\Sigma \vdash \left( \theta \rightarrow \phi \right)\), que es lo que necesitamos mostrar.

Por lo que queda por probar que\(C\) tiene las propiedades enumeradas en el párrafo anterior.

1. \(\Sigma \subseteq C\): Si\(\sigma \in \Sigma\), entonces\(\Sigma \vdash \sigma\). Pero entonces\(\Sigma \vdash \left( \theta \rightarrow \sigma \right)\), ya que esto es una consecuencia proposicional de\(\sigma\).
2. \(\theta \in C\):\(\Sigma \vdash \theta \rightarrow \theta\), ya que esto es una tautología.
3. \(\Lambda \subseteq C\): Esto es idéntico a (1).
4. \(C\)está cerrado bajo las reglas:
   1. Regla (PC): Supongamos que todos\(\gamma_1, \gamma_2, \ldots, \gamma_n\) son elementos de\(C\) y\(\phi\) es una consecuencia proposicional de\(\{ \gamma_1, \gamma_2, \ldots, \gamma_n \}\). Debemos demostrarlo\(\phi \in C\). Por suposición,\(\Sigma \vdash \left( \theta \rightarrow \gamma_1 \right)\),\(\Sigma \vdash \left( \theta \rightarrow \gamma_2 \right), \ldots, \Sigma \vdash \left( \theta \rightarrow \gamma_n \right)\). Pero entonces como\(\left( \theta \rightarrow \phi \right)\) es una consecuencia proposicional del conjunto
      \[\left\{ \left( \theta \rightarrow \gamma _ { 1 } \right) , \left( \theta \rightarrow \gamma _ { 2 } \right) , \ldots , \left( \theta \rightarrow \gamma _ { n } \right) \right\},\]
      tenemos eso\(\Sigma \vdash \left( \theta \rightarrow \phi \right)\). En otras palabras,\(\phi \in C\), según sea necesario.
   2. Reglas del cuantificador: Supongamos que\(\psi \rightarrow \phi\) está adentro\(C\) y no\(x\) es libre en\(\psi\). Queremos demostrar que\(\left( \psi \rightarrow \forall x \phi \right)\) es un elemento de\(C\). Es decir, tenemos que demostrar que
      \[\Sigma \vdash \left[ \theta \rightarrow ( \psi \rightarrow \forall x \phi ) \right].\]
      Por suposición tenemos
      \[\begin{array}{ll} \Sigma \vdash \left[ \theta \rightarrow \left( \psi \rightarrow \phi \right) \right] & \psi \rightarrow \phi \: \text{is in} \: C \\ \Sigma \vdash \left( \theta \land \psi \right) \rightarrow \phi & \text{propositional consequence} \\ \Sigma \vdash \left( \theta \land \psi \right) \rightarrow \forall x \phi & \text{rule (QR)} \\ \Sigma \vdash \left[ \theta \rightarrow \left( \psi \rightarrow \forall x \phi \right) \right] & \text{propositional consequence} \end{array}\]
      Aviso que nuestro uso de regla (QR) es legítimo ya que sabemos que\(\theta\) es una oración, por lo que no\(x\) es libre en \(\theta\). Pero la última línea de nuestro argumento dice eso\(\left( \psi \rightarrow \forall x \phi \right) \in C\), que es lo que necesitábamos mostrar. La otra regla del cuantificador, que trata del cuantificador existencial, se demuestra de manera similar.

Entonces tenemos espectáculo que\(C\) contiene\(\theta\), todos los elementos de\(\Sigma\) y\(\Lambda\), y\(C\) está cerrado bajo las reglas. Esto termina la prueba del Teorema de Deducción.

Ejercicios

1. Lema 2.7.2 nos dice que\(\Sigma \vdash \theta\) si y solo si\(\Sigma \vdash \forall x \theta\). ¿Qué pasa si reemplazamos el cuantificador universal por un cuantificador existencial? Entonces supongamos eso\(\Sigma \vdash \theta\). \(\Sigma \vdash \exists x \theta\)¿Debe? Ahora asuma eso\(\Sigma \vdash \exists x \theta\). ¿\(\Sigma\)Necesariamente prueba\(\theta\)?
2. Terminar la prueba de Lemma 2.7.3 considerando el caso cuando\(\forall x \sigma\) es un elemento de\(\Sigma\) y es reemplazado por\(\sigma\) in\(\Sigma^\prime\).
3. Muchos autores exigen que los axiomas sean oraciones más que fórmulas. Explicar cómo Lemma 2.7.2 implica que podríamos sustituir todos nuestros axiomas por sus cierres universales sin cambiar la fuerza de nuestro sistema deductivo.
4. Supongamos que\(\eta\) es una oración. Demostrar que\(\Sigma \vdash \eta\) si y sólo si\(\Sigma \cup \left( \neg \eta \right) \vdash \left[ \left( \forall x \right) x = x \right] \land \neg \left[ \left( \forall x \right) x = x \right]\). Observe que este ejercicio nos dice que nuestro sistema deductivo nos permite hacer pruebas por contradicción.
5. Supongamos que\(P\) es un símbolo de relación unaria y muestra que
   \[\vdash [ ( \forall x ) P ( x ) ] \rightarrow [ ( \exists x ) P ( x ) ].\]
   [Sugerencia: Prueba por contradicción (ver Ejercicio 4) funciona muy bien aquí.]
6. Si\(P\) es un símbolo de relación binaria, mostrar que
   \[( \forall x ) ( \forall y ) P ( x , y ) \vdash ( \forall y ) ( \forall z ) P ( z , y ).\]
7. Dejar\(P\) y\(Q\) ser unarios símbolos de relación, y mostrar que
   \[\vdash [ ( \forall x ) ( P ( x ) ) \wedge ( \forall x ) ( Q ( x ) ) ] \rightarrow ( \forall x ) [ P ( x ) \wedge Q ( x ) ].\]