4.6: Un viejo amigo
- Page ID
- 113510
De vuelta en el Ejemplo 2.8.3 presentamos la colección de axiomas no lógicos\(N\). Sólo porque son tan importantes, los reimprimiremos aquí:
Los axiomas de\(N\)
\[\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}\]
En ese momento (Lema 2.8.4) probamos algunas cosas sobre la fuerza de este conjunto de axiomas de aspecto inocuo, por ejemplo, si el número natural\(a\) es igual a la suma\(b + c\), entonces\(N \vdash \bar{a} = \bar{b} + \bar{c}\). Vamos a necesitar algunos resultados adicionales sobre la fuerza de\(N\) que se probarán en detalle en el Capítulo 5. Los exponemos aquí y damos algunos ejemplos.
Recordemos que hemos definido las colecciones de\(\Delta\) -fórmulas como las fórmulas en el lenguaje de la teoría de números que no contienen cuantificadores no delimitados. Para un ejemplo específico, considere\(\phi \left( x \right)\), la fórmula con una variable libre
\[\phi \left( x \right) : \equiv \left( \exists y \leq x \right) \bar{2} y = x\]
que establece que\(x\) es un número par. Supongamos que consideramos dos frases diferentes asociadas con\(\phi : \phi \left( \bar{2} \right)\) y\(\phi \left( \bar{3} \right)\). Todos estaremos de acuerdo en que\(\phi \left( \bar{2} \right)\) es una afirmación verdadera sobre\(\mathfrak{N}\), mientras que\(\phi \left( \bar{3} \right)\) es falsa. Lo que es tan maravilloso de nuestro conjunto de axiomas no lógicos\(N\) es que\(N\) es lo suficientemente fuerte como para probar la primera afirmación y refutar la segunda:
\[N \vdash \phi \left( \bar{2} \right) \: \: \: \: \: \: \: \: \: \: N \vdash \neg \phi \left( \bar{3} \right)\]
Este es un dato general sobre la relación entre\(\Delta\) -fórmulas y\(N\), que aquí expondremos y probaremos como Proposición 5.3.14:
Si\(\phi \left( \underset{\sim}{x} \right)\) es una\(\Delta\) fórmula -con variables libres\(\underset{\sim}{x}\), si\(\underset{\sim}{t}\) son términos libres de variables, y si\(\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \phi \left( \underset{\sim}{t} \right)\). Si, por otro lado,\(\mathfrak{N} \models \neg \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \neg \phi \left( \underset{\sim}{t} \right)\).
Si permitimos un cuantificador existencial sin límites, la situación cambia ligeramente. Nuestro conjunto de axiomas\(N\) es lo suficientemente fuerte como para probar las\(\Sigma\) frases verdaderas, pero no puede refutar las\(\Sigma\) frases falsas. Este resultado, llamado \(\Sigma\)-completitud, será probado como Proposición 5.3.13:
Si\(\phi \left( \underset{\sim}{x} \right)\) es una\(\Sigma\) fórmula -con variables libres\(\underset{\sim}{x}\), si\(\underset{\sim}{t}\) son términos libres de variables, y si\(\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \phi \left( \underset{\sim}{t} \right)\).
En un nivel, esto no debería ser demasiado sorprendente, dado que\(N\) es lo suficientemente fuerte como para probar o refutar oraciones que no tienen cuantificadores ilimitados. Supongamos que\(\phi\) es una verdadera\(\Sigma\) -oración. Entonces\(\phi\) mira (aproximadamente) como\(\exists x \psi \left( x \right)\), donde\(\psi\) tiene una variable libre. Ya que\(\exists x \psi \left( x \right)\) es cierto en\(\mathfrak{N}\), entonces hay algún número natural\(k\) tal que\(\psi \left( k \right)\) es cierto. Pero entonces\(\psi \left( \bar{k} \right)\) es una\(\mathfrak{N}\) oración verdadera sin cuantificadores sin límites. Por suposición,\(N\) es lo suficientemente fuerte como para probarlo\(\psi \left( \bar{k} \right)\), y así por las reglas habituales de la lógica,\(N\) también prueba\(\exists x \psi \left( x \right)\); es decir,\(N\) prueba\(\phi\).
Por otro lado, si nuestra\(\Sigma\) -sentencia\(\phi\) es falsa en\(\mathfrak{N}\), eso solo significa que no hay un número natural\(k\) tal que\(\psi \left( k \right)\) sea cierto. Ahora, ya que no\(\psi \left( \bar{k} \right)\) tiene cuantificadores sin límites, por suposición eso significa que\(N \vdash \neg \psi \left( \bar{k} \right)\) para cada número natural\(k\). Pero ya hemos visto que hay muchas estructuras de aritmética no estándar donde una propiedad puede ser falsa de cada número natural pero aún así cierta de algún otro elemento del universo. Entonces solo porque\(N\) puede probar que\(\psi\) es falso de cada número natural, no hay razón a priori para asumir que luego\(N\) pueda probar que\(\psi\) es falso de todo. Y de hecho, no puede.
Entonces, la versión corta:
\(N\)es lo suficientemente fuerte como para probar\(\Sigma\) frases verdaderas, pero no lo suficientemente fuerte como para refutar\(\Sigma\) frases falsas.
Equivalentemente, dado que la negación de a\(\Sigma\) -oraciones es equivalente a una\(\Pi\) -oración:
\(N\)es lo suficientemente fuerte como para probar cada\(\Sigma\) oración verdadera, pero no lo suficientemente fuerte como para probar cada\(\Pi\) oración verdadera.
Por ejemplo, consideremos la Conjetura de Goldbach, que establece que cada número par mayor a dos puede escribirse como la suma de dos primos. No es difícil ver que la Conjetura de Goldbach pueda escribirse formalmente como una\(\Pi\) frase, pero lamentablemente actualmente no sabemos si la Conjetura de Goldbach es cierta o no. Supongamos por un segundo que la conjetura era falsa. Entonces su negación, equivalente a una\(\Sigma\) sentencia, sería cierta, y por lo tanto\(N\) sería capaz de probar la negación. No es de extrañar, de verdad. Todo lo que tendríamos que hacer es encontrar un número par que sea un contraejemplo a la Conjetura de Goldbach y comprobar que no es la suma de dos primos. (Advertencia: Si vas a empezar a buscar el contraejemplo, ve a lo grande o vete a casa. La conjetura ha sido verificada para todos los números pares hasta por lo menos\(4 \times 10^{18}\).)
Por otro lado, si la Conjetura de Goldbach es cierta, entonces no hay razón para creer que\(N\) sea lo suficientemente fuerte como para probar ese hecho. Lo que, por cierto, significa que si pudiéramos probar que no\(N\) es lo suficientemente fuerte como para decidir la Conjetura de Goldbach, ¡entonces la Conjetura de Goldbach es verdad!