4.2: Complejidad de las Fórmulas

Trabajamos en el lenguaje de la teoría de números

\[\mathcal{L}_{NT} = \{ 0, S, +, \cdot, E, < \},\]

y seguiremos trabajando en este lenguaje durante los próximos capítulos. \(\mathfrak{N}\)es el modelo estándar de los números naturales,

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

donde las funciones y relaciones son las funciones y relaciones habituales que has conocido desde que estuviste a la altura de las rodillas a un saltamontes. \(E\)es exponenciación, que generalmente se escribirá\(x^y\) en lugar de\(Exy\) o\(xEy\).

Una forma de pensar sobre las fórmulas más simples del lenguaje de los números naturales (de cualquier lenguaje, realmente) son las fórmulas que no implican ningún cuantificador. Parece natural que la fórmula\(S0 = y\) sea más sencilla que\(\forall x S 0 = y\). Un paso de bebé más complicado que las fórmulas sin cuantificador son las fórmulas que contienen lo que llamaremos cuantificadores acotados:

Definición 4.2.1.

Si\(x\) es una variable que no ocurre en el término\(t\), aceptemos utilizar las siguientes abreviaturas:

\[ \left( \forall x < t \right) \phi \: \text{means} \: \forall x \left( x < t \rightarrow \phi \right) \\ \left( \forall x \leq t \right) \phi \: \text{means} \: \forall x \left( \left( x < t \lor x = t \right) \rightarrow \phi \right) \\ \left( \exists x < t \right) \phi \: \text{means} \: \exists x \left( x < t \land \phi \right) \\ \left( \exists x \leq t \right) \phi \: \text{means} \: \exists x \left( \left( x < t \lor x = t \right) \land \phi \right).\]

Estas abreviaturas constituirán el conjunto de cuantificadores acotados.

Así, la fórmula\(\exists x \left( \left( \forall y < \overline{42} \right) y = Sx \right)\) es una fórmula con un cuantificador acotado y un cuantificador no acotado.

Recuerda que nuestro objetivo es producir una frase que sea verdadera en\(\mathfrak{N}\) y no demostrable a partir de nuestro conjunto de axiomas. ¿Podríamos encontrar una fórmula que sólo contenga cuantificadores acotados? Eso sería realmente genial, pero desgraciadamente no va a suceder. ¿Recuerdas nuestro conjunto de axiomas\(N\), de vuelta en la Sección 2.8? Si vuelves a esa sección verás que todos estos axiomas son verdaderas declaraciones sobre los números naturales, por lo que deberían ser consecuencia de cualquier conjunto potencial de axiomas para\(Th \left( \mathfrak{N} \right)\). Pero en realidad\(N\) es una colección bastante fuerte de declaraciones. En particular,\(N\) es lo suficientemente robusto como para probar cada afirmación verdadera al respecto\(\mathfrak{N}\) que contiene solo cuantificadores acotados. Aún mejor,\(N\) puede refutar cada declaración falsa que contenga solo cuantificadores acotados. Demostraremos este hecho en la Proposición 5.3.14. Dado que cualquier candidato potencial para una axiomatización de\(\mathfrak{N}\) debe ser al menos tan fuerte como\(N\), esto nos dice que nuestra búsqueda de una fórmula que sea a la vez verdadera\(\mathfrak{N}\) y no demostrable debe mirar fórmulas que contengan al menos algunos cuantificadores no acotados.

Definición 4.2.2.

La colección de \(\Sigma\)-formulas se define como el conjunto más pequeño de\(\mathcal{L}_{NT}\) -fórmulas de tal manera que:

1. Toda fórmula atómica es una\(\Sigma\) fórmula.
2. Toda negación de una fórmula atómica es una\(\Sigma\) fórmula.
3. Si\(\alpha\) y\(\beta\) son\(\Sigma\) -fórmulas, entonces\(\alpha \land \beta\) y\(\alpha \lor \beta\) son ambas\(\Sigma\) -fórmulas.
4. Si\(\alpha\) es una\(\Sigma\) -fórmula, y\(x\) es una variable que no ocurre en el término\(t\), entonces las siguientes son\(\Sigma\) -fórmulas:\(\left( \forall x < t \right) \alpha\),\(\left( \forall x \leq t \right) \alpha\),\(\left( \exists x < t \right) \alpha\),\(\left( \exists x \leq t \right) \alpha\).
5. Si\(\alpha\) es una\(\Sigma\) fórmula y\(x\) es una variable, entonces\(\left( \exists x \right) \alpha\) es una\(\Sigma\) -fórmula.

Demostraremos más adelante (Teorema 5.3.13) que de hecho nuestro conjunto de axiomas\(N\) es lo suficientemente fuerte como para probar cada\(\Sigma\) oración verdadera, por lo que incluso estas fórmulas no son lo suficientemente complicadas como para establecer el resultado de incompletitud de Gödel. Sin embargo, si en lugar de permitir un cuantificador existencial sin límites, permitimos un cuantificador universal sin límites, la situación es diferente.

Definición 4.2.3.

La colección de \(\Pi\)-formulas es el conjunto más pequeño de\(\mathcal{L}_{NT}\) -fórmulas de tal manera que:

1. Toda fórmula atómica es una\(\Pi\) fórmula.
2. Toda negación de una fórmula atómica es una\(\Pi\) fórmula.
3. Si\(\alpha\) y\(\beta\) son\(\Pi\) -fórmulas, entonces\(\alpha \land \beta\) y\(\alpha \lor \beta\) son ambas\(\Pi\) -fórmulas.
4. Si\(\alpha\) es una\(\Pi\) -fórmula, y\(x\) es una variable que no ocurre en el término\(t\), entonces las siguientes son\(\Pi\) -fórmulas:\(\left( \forall x < t \right) \alpha\),\(\left( \forall x \leq t \right) \alpha\),\(\left( \exists x < t \right) \alpha\),\(\left( \exists x \leq t \right) \alpha\).
5. Si\(\alpha\) es una\(\Pi\) fórmula y\(x\) es una variable, entonces\(\left( \forall x \right) \alpha\) es una\(\Pi\) -fórmula.

Entonces, mientras el conjunto de\(\Sigma\) -fórmulas se cierra bajo cuantificación acotada y cuantificación existencial no acotada, la colección de\(\Pi\) -fórmulas se cierra bajo cuantificación acotada y cuantificación universal sin límites.

El mayor resultado del resto del libro, el primer teorema de incompletitud de Gödel, establece que si se nos da algún conjunto consistente y decidible de axiomas, entonces habrá una\(\Pi\) -fórmula\(\sigma\) tal que\(\sigma\) sea una verdadera afirmación sobre los números naturales pero no hay deducción de nuestros axiomas de la fórmula\(\sigma\). Por lo que nuestro conjunto de axiomas debe estar incompleto. Llegar a ese teorema nos ocupará el resto de nuestro tiempo juntos.

Podrías notar que cada negación\(\Sigma\) de una fórmula es lógicamente equivalente a una\(\Pi\) fórmula, y viceversa (ver Ejercicio 3). Si tomamos la intersección de la colección de\(\Sigma\) -fórmulas y la colección de\(\Pi\) -fórmulas, tenemos las\(\Delta\) -fórmulas:

Definición 4.2.4.

La colección de \(\Delta\)-fórmulas es la intersección de la colección de\(\Sigma\) -fórmulas con el conjunto de\(\Pi\) -fórmulas.

Así, en cada\(\Delta\) fórmula todos los cuantificadores están acotados. Resultará que nuestro misterioso (bueno, en realidad no es tan misterioso) conjunto de axiomas\(N\) es lo suficientemente fuerte como para probar cada\(\mathfrak{N}\)\(\Delta\) fórmula verdadera y refutar cada\(\mathfrak{N}\)\(\Delta\) fórmula falsa. Esto va a ser muy importante para nosotros.

Ejercicios

1. Refiriéndose a la Definición 4.2.2, explique en detalle por qué las siguientes fórmulas son (o no son)\(\Sigma\) -fórmulas.
   a)\(S0 + S0 = SS0\)
   b)\(\neg \left( 0 < 0 \lor 0 < S0 \right)\)
   c\(\left( \forall x < \overline{17} \right) x < \overline{17}\)
   ) d\(S0 \cdot S0 = S0 \land \left( \exists y < x \right) \left( \exists z < y \right) y + z = x\)
   ) e\(\left( \forall y \right) \left( y < 0 \rightarrow 0 = 0 \right)\)
   ) f)\(\left( \exists x \right) \left( x < x \right)\)
2. Definamos el conjunto de Fórmulas Cool para que sea el conjunto más pequeño de\(\mathcal{L}_{NT}\) -fórmulas que:
   (a) Contiene todas las fórmulas atómicas.
   (b) Contiene todas las negaciones de fórmulas atómicas.
   (c) Se cierra bajo los conectivos\(\land\) y\(\lor\).
   (d) Se cierra bajo cuantificadores acotados y el cuantificador\(\exists\)
   Probar que una fórmula es Cool si y sólo si la fórmula es una\(\Sigma\) fórmula. (Las cuatro condiciones anteriores se utilizan a veces para definir el conjunto\(\Sigma\) de fórmulas. Acabas de demostrar que la definición aquí es equivalente a Definición 4.2.2.)
3. Piensa en la\(\Sigma\) -fórmula
   \[\alpha \: \text{is} \: x< y \lor \left( \forall z < w \right) x + \overline{17} = \overline{42}.\]
   (a) ¿Es\(\alpha\) una\(\Pi\) fórmula?
   b) ¿Es\(\neg \alpha\) una\(\Pi\) fórmula?
   (c) ¿Se puede encontrar una\(\Pi\) fórmula -que sea equivalente a\(\neg \alpha\)?
   (d) Demostrar cuidadosamente que, si\(\alpha\) es alguna\(\Sigma\) fórmula, entonces\(\neg \alpha\) es lógicamente equivalente a una\(\Pi\) fórmula.