2.2: Deducciones

Comenzamos por fijar un idioma\(\mathcal{L}\). También supongamos que se nos ha dado un conjunto fijo de\(\mathcal{L}\) -fórmulas\(\Lambda\),, llamado el conjunto de axiomas lógicos, y un conjunto de pares ordenados\(\left( \Gamma, \phi \right)\), llamados las reglas de inferencia. (Especificaremos de qué fórmulas son elementos\(\Lambda\) y cuáles pares ordenados son reglas de inferencia en las dos secciones siguientes). Una deducción va a ser una secuencia finita, o lista ordenada, de\(\mathcal{L}\) -fórmulas con ciertas propiedades.

Definición 2.2.1

Supongamos que\(\Sigma\) es una colección de\(\mathcal{L}\) -fórmulas y\(D\) es una secuencia finita\(\left( \phi_1, \phi_2, \ldots, \phi_n \right)\) de\(\mathcal{L}\) -fórmulas. Vamos a decir que\(D\) es una deducción de\(\Sigma\) si para cada uno\(i\),\(1 \leq i \leq n\), ya sea

1. \(\phi_i \in \Lambda\)(\(\phi_i\)es un axioma lógico), o
2. \(\phi_i \in \Sigma\)(\(\phi_i\)es un axioma no lógico), o
3. Hay una regla de inferencia\(\left( \Gamma, \phi_i \right)\) tal que\(\Gamma \subseteq \{ \phi_i, \phi_2, \ldots, \phi_{i - 1} \}\).

Si hay una deducción de\(\Sigma\), cuya última línea es la fórmula\(\phi\), llamaremos a esto una deducción\(\Sigma\) de\(\phi\), y escribiremos\(\Sigma \vdash \phi\).

Chaff: Bueno, ahora hemos establecido lo que queremos decir con la palabra justificada. En una deducción se nos permite anotar cualquier\(\mathcal{L}\) fórmula que nos guste, siempre y cuando esa fórmula sea un axioma lógico o esté listada explícitamente en una colección\(\Sigma\) de axiomas no lógicos. Cualquier fórmula que escribamos en una deducción que no sea un axioma debe surgir de fórmulas anteriores en la deducción vía una regla de inferencia.

Es posible que hayas descubierto que existen muchos sistemas deductivos diferentes, dependiendo de las elecciones para las que se tomen\(\Lambda\), y las reglas de inferencia. Como regla general, un sistema deductivo o bien tendrá muchas reglas de inferencia y pocos axiomas lógicos, o no demasiadas reglas y muchos axiomas. Al desarrollar el sistema deductivo para que podamos usar en este libro, intentamos seguir un curso medio.

También fíjese que\(\vdash\) es otro símbolo metalingüístico. No es parte del idioma\(\mathcal{L}\)

Ejemplo 2.2.2. Supongamos, para empezar, que no queremos hacer suposiciones. Entonces, vamos\(\Sigma = \emptyset\), vamos\(\Lambda = \emptyset\), y anote una deducción de\(\Sigma\). No seas tímido. Adelante. Vamos a esperar.

¿Aún nada? Derecha. No hay deducciones del conjunto vacío de axiomas. (En realidad, después de establecer nuestras reglas de inferencia, habrá algunas deducciones del conjunto vacío de axiomas, pero eso viene después). Este es un problema que el lógico inglés Bertrand Russell encontró particularmente molesto cuando comenzó a aprender matemáticas.

A los once años, comencé Euclides, con mi hermano como mi tutor. Este fue uno de los grandes acontecimientos de mi vida, tan deslumbrante como el primer amor. No me había imaginado que hubiera algo tan delicioso en el mundo.... Desde ese momento hasta que Whitehead y yo terminamos Principia Mathematica, cuando tenía treinta y ocho años, las matemáticas eran mi principal interés, y mi principal fuente de felicidad. Como toda felicidad, sin embargo, no estaba sin alear. Me habían dicho que Euclides probaba las cosas, y estaba muy decepcionado de que comenzara con axiomas. Al principio me negué a aceptarlos a menos que mi hermano pudiera ofrecerme alguna razón para hacerlo, pero dijo: “Si no los aceptas no podemos seguir”, y como deseaba continuar, los admití a regañadientes pro tem. La duda en cuanto a las premisas de las matemáticas que sentí en ese momento quedó conmigo, y determinó el curso de mi trabajo posterior. [Russell 67, p. 36]

Sin embargo, lo que hemos logrado hacer con nuestra definición de deducción es ser sinceros sobre nuestra necesidad de hacer suposiciones, y reconoceremos nuestro axioma establecido en cada deducción que escribamos.

Ejemplo 2.2.3. Trabajemos en el lenguaje\(\mathcal{L} = \{ P \}\), donde\(P\) es un símbolo de relación binaria. Que\(\Sigma\), nuestro conjunto de axiomas, sea

\[\begin{align} \Sigma + &\{ \forall x P \left( x, x \right), \\ &P \left( u, v \right), \\ &P \left( u, v \right) \rightarrow P \left( v, u \right), \\ &P \left( v, u \right) \rightarrow P \left( u, u \right) \}. \end{align}\]

Vamos a dejar\(\Lambda = \emptyset\) por ahora. También necesitamos tener un conjunto de reglas de inferencia. Así que temporalmente deja que nuestro conjunto de reglas de inferencia sea

\[\{ \{ \{ \alpha, \alpha \rightarrow \beta \}, \beta \} | \alpha \: \text{and} \: \beta \: \text{are formulas of} \: \mathcal{L} \}.\]

Esta es sólo la regla modus ponens, que dice que a partir de las fórmulas\(\alpha\) y\(\alpha \rightarrow \beta\) podemos concluir\(\beta\).

Ahora podemos escribir una deducción\(\Sigma\) de la fórmula\(P \left( u, u \right)\), de la siguiente manera:

\[\begin{align} &P \left( u, v \right) \\ &P \left( u, v \right) \rightarrow P \left( v, u \right) \\ &P \left( v, u \right) \\ &P \left( v, u \right) \rightarrow P \left( u, u \right) \\ &P \left( u, u \right). \end{align}\]

Puede ver fácilmente que cada fórmula en nuestra deducción está explícitamente enumerada entre los elementos de nuestro conjunto de axiomas\(\Sigma\), o se desprende de modus ponens de fórmulas previamente listadas en la deducción.

Observe, sin embargo, que no podemos usar la declaración universal\(\forall x P \left( x, x \right)\) para derivar nuestra fórmula necesaria\(P \left( u, u \right)\). Incluso una afirmación que parece que debería seguir de nuestros axiomas, por ejemplo\(P \left( v, v \right)\), no será deducible\(\Sigma\) hasta que o agreguemos a nuestras reglas de inferencia o incluyamos algunos axiomas adicionales. Nuestra definición de deducción es muy limitante; ni siquiera podemos usar trucos lógicos estándar como la instanciación universal [de\(\forall x blah \left( x \right)\) deducir\(blah \left( t \right)\)]. Estos axiomas lógicos se reunirán en la Sección 2.3.

Chaff: Aquí es realmente tentador anotar la deducción incorrecta

\[\begin{align} &\forall x P \left( x, x \right) \\ &P \left( u, u \right) \end{align}\]

Por favor, no digas cosas así hasta que hayamos construido nuestra colección de axiomas lógicos. Recuerden, lo que estamos tratando de hacer aquí es tener una definición de deducción que sea enteramente sintáctica, que no dependa de los significados de los símbolos. Donde es probable que te encuentres con problemas es cuando empiezas a pensar demasiado en los significados de las cosas que escribes. Nuestra definición nos da deducciones que son fácilmente verificables: Ante una supuesta deducción de\(\Sigma\), siempre y cuando podamos decidir en qué fórmulas se encuentran\(\Sigma\) podemos decidir si la supuesta deducción es correcta. De hecho, podríamos programar fácilmente una computadora para verificar la deducción por nosotros. No obstante, esta facilidad en la verificación viene con un precio: Las deducciones son difíciles de escribir y difíciles de motivar.

La definición 2.2.1 es una definición de “abajo hacia arriba”. Define una deducción en términos de sus partes. Otra forma de definir una colección de cosas es adoptar un enfoque “de arriba hacia abajo”. La siguiente proposición hace precisamente eso, al demostrar que podemos pensar en el cobro de deducciones de\(\Sigma\) (llamado Thm\(_\Sigma\)) como el cierre de la colección de axiomas bajo la aplicación de las reglas de inferencia.

Proposición 2.2.4

Fijar conjuntos de\(\mathcal{L}\) -fórmulas\(\Sigma\) y\(\Lambda\) y una colección de reglas de inferencia. el conjunto Thm\(_\Sigma = \{ \phi | \Sigma \vdash \phi \}\) es el conjunto más pequeño de\(C\) tal manera que

1. \(\Sigma \subseteq C\).
2. \(\Lambda \subseteq C\).
3. Si\(\left( \Gamma, \theta \right)\) es una regla de inferencia y\(\Gamma \subseteq C\), entonces\(\theta \in C\).

Prueba

Esta proposición hace dos afirmaciones separadas sobre el conjunto Thm\(_\Sigma\). La primera afirmación es que\(_\Sigma\) Thm satisface los tres criterios. La segunda afirmación es que Thm\(_\Sigma\) es el conjunto más pequeño para satisfacer los criterios. Abordamos estas afirmaciones una a la vez.

Primero, veamos los criterios en orden, y asegurémonos de que Thm los\(_\Sigma\) satisfaga. Entonces, para comenzar, debemos demostrar que\(\Sigma \subseteq\) Thm\(_\Sigma\). Pero ciertamente si\(\sigma \in \Sigma\), hay una deducción -de-\(\Sigma\) de\(\sigma\), por ejemplo esta deducción unifilar:\(\sigma\). Del mismo modo, para demostrar que\(\Lambda \subseteq\) Thm\(_\Sigma\). Para terminar esta parte de la prueba, debemos demostrar que si\(\left( \Gamma, \theta \right)\) es una regla de inferencia y Thm\(\Gamma \subseteq\)\(_\Sigma\), entonces\(\theta \in\) Thm\(_\Sigma\). Pero para producir una deducción -de-\(\Sigma\) de\(\theta\), todo lo que tenemos que hacer es anotar deducciones de cada uno de los\(\gamma\)'s in\(\Gamma\), seguido de la fórmula\(\theta\). Se trata de una deducción válida, como se\(\theta\) desprende\(\Gamma\) de la regla de inferencia\(\left( \Gamma, \theta \right)\). Así,\(_\Sigma\) Thm satisface los tres criterios de la proposición.

Ahora debemos demostrar que Thm\(_\Sigma\) es el conjunto más pequeño de este tipo. Esto es bastante fácil de probar una vez que descubras lo que tienes que hacer. Lo que se afirma es que si\(C\) es una colección de fórmulas que satisfacen los requisitos dados, entonces Thm\(_\Sigma\)\(\subseteq C\). Entonces asumimos que\(C\) es una clase que satisface las condiciones, e intentamos demostrar que cada elemento de Thm\(_\Sigma\) está en\(C\).

Si\(\phi \in\)\(_\Sigma\) Thm, hay una deducción de\(\Sigma\) con última línea\(\phi\). Si la entrada\(\phi\) se justifica en virtud de\(\phi\) ser un axioma lógico o no lógico, entonces\(\phi\) se incluye explícitamente en el conjunto\(C\). Si\(\phi\) se justifica por referencia a una regla de inferencia\(\left( \Gamma, \phi \right)\), entonces cada uno\(\gamma \in \Gamma\) es un elemento de\(C\) (esto es realmente una prueba por inducción, y aquí es donde usamos la hipótesis inductiva), y así, por el tercer requisito sobre\(C\)\(\phi \in C\), según sea necesario.

Dado que\(_\Sigma\)\(\subseteq C\) Thm para todos esos conjuntos\(C\), Thm\(_\Sigma\) es el conjunto más pequeño de este tipo, como se afirma.

\(\square\)

Esto es lo que haremos en las próximas secciones: Vamos a definir\(\Lambda\), el conjunto fijo de axiomas lógicos; estableceremos nuestra colección de reglas de inferencia; probaremos algunos resultados sobre deducciones; y finalmente, discutiremos algunos ejemplos de conjuntos de axiomas no lógicos.

Ejercicios

1. Que sea la colección de axiomas no lógicos
   \[\Sigma = \{ \left( A \left( x \right) \land A \left( x \right) \right) \rightarrow B \left( x, y \right), A \left( x \right), B \left( x, y \right) \rightarrow A \left( x \right) \},\]
   y que la regla de inferencia sea modus ponens, como en el Ejemplo 2.2.3. Por cada una de las siguientes, decidirá si se trata de una deducción. Si no es una deducción, explique cómo sabe que no es una deducción.
   (a)
   \[\begin{align} &A \left( x \right) \\ &A \left( x \right) \land A \left( x \right) \\ &\left( A \left( x \right) \land A \left( x \right) \right) \rightarrow B \left( x, y \right) \\ &B \left( x, y \right) \end{align}\]
   (b)
   \[\begin{align} &B \left( x, y \right) \rightarrow A \left( x \right) \\ &A \left( x \right) \\ &B \left( x, y \right) \end{align}\]
   (c)
   \[\begin{align} &\left( A \left( x \right) \land A \left( x \right) \right) \rightarrow B \left( x, y \right) \\ &B \left( x, y \right) \rightarrow A \left( x \right) \\ &\left( A \left( x \right) \land A \left( x \right) \right) \rightarrow A \left( x \right) \end{align}\]
2. Consideremos el sistema\(\Sigma\) de axiomas del Ejemplo 2.2.3. Está implícito en ese ejemplo que no hay deducción\(\Sigma\) de la fórmula\(P \left( v, v \right)\). Demostrar este hecho.
3. Escriba cuidadosamente la prueba de la Proposición 2.2.4, preocupándose por el paso inductivo. [Sugerencia: Es posible que desee proceder por inducción sobre la duración de la deducción más corta de\(\phi\).]
4. Dejar\(\mathcal{L}\) ser un lenguaje que consiste en un solo símbolo de predicado unario\(R\), y dejar\(B\) ser el conjunto infinito de axiomas
   \[\begin{align} B = &\{ R \left( x_1 \right), \\ &R \left( x_1 \right) \rightarrow R \left( x_2 \right), \\ &R \left( x_2 \right) \rightarrow R \left( x_3 \right), \\ &\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \vdots \\ &R \left( x_i \right) \rightarrow R \left( x_{i + 1} \right), \\ &\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \vdots \\ &\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \}. \end{align}\]
   Utilizando modus ponens como única regla de inferencia, demostrar por inducción que\(B \vdash R \left( x_j \right)\) para cada número natural\(j \geq 1\).