Una frase cierta pero indemostrable $\theta$ que no es un $\Pi$ -sentencia

Question

Pregunta $4$ de la Sección $7.7.3$ en "A Friendly Introduction to Mathematical Logic" (Christopher C. Leary y Lars Kristiansen; $2$ nd edition):

Sea $A = \{\phi \mid \phi \text{ is a } \Pi\text{-sentence and } \mathfrak{R} \vDash \phi \}$ . (Obsérvese que todos los axiomas de $N$ son elementos del conjunto $A$ .) Demuestre que existe un $\mathcal{L}_{NT}$ -sentencia $\theta$ tal que $\mathfrak{R} \vDash \theta$ et $A \nvdash \theta$ . [...]

Nota sobre la notación: El lenguaje (de la teoría de números) $\mathcal{L}_{NT}$ es $\{0, S, +, \cdot, E, \lt\}$ donde $0$ es un símbolo constante, $+$ , $\cdot$ y $E$ son $2$ -símbolos de función, $S$ es un $1$ símbolo de función -ary, y $\lt$ es un $2$ símbolo de relación -ary (en este libro, el símbolo de igualdad es un $2$ relación -aria que se supone que siempre forma parte de una lengua). $N$ es una versión de los axiomas de la aritmética. $\mathfrak{R}$ es la interpretación estándar de los axiomas $N$ (como afirmaciones sobre números naturales). El conjunto de $\Pi$ -sentencias es el conjunto más pequeño de $\mathcal{L}_{NT}$ -que contiene todas las fórmulas atómicas y sus negaciones, y es cerrado bajo cuantificadores acotados, el cuantificador universal y las conectivas el $\land$ et $\lor$ .

El Primer Teorema de Incompletitud de Gödel (al menos tal como se presenta en el libro de Leary y Kristiansen) proporciona un $\Pi$ -sentencia que es verdad-en $\mathfrak{R}$ pero no demostrable por $A$ para cualquier conjunto de axiomas coherente y semicomputable $A$ . Obviamente eso no funcionará aquí, ya que $A$ es el conjunto de todos los $\mathfrak{R}$ $\Pi$ -sentencias. En algún lugar de la fórmula tendrá que haber un cuantificador existencial, y un cuantificador universal también (como true-in- $\mathfrak{R}$ $\Sigma$ -(sustituya el cuantificador universal por el cuantificador existencial en la definición de un $\Pi$ -) son demostrables por $N$ y así por $A$ ). Tal vez la solución tenga algo que ver con la frase $\psi$ tal que $\mathfrak{R} \vDash \psi$ pero $N \nvdash \psi$ ? ¿Cómo enfoco este problema?

Answer 1

A continuación, para simplificar, confundiré las sentencias con sus números de Godel.

Tenga en cuenta que $\{\varphi: A\vdash\varphi\}$ es definible en $\mathfrak{R}$ Esto se debe a que $A$ es definible, y el cierre deductivo de un conjunto definible de sentencias es también definible (este último punto forma parte esencialmente de la demostración del teorema de Godel). En Teorema de indefinibilidad de Tarski Esto significa que no puede coinciden con $Th(\mathfrak{R})$ (= $\{\varphi:\mathfrak{R}\models\varphi\}$ ).

El punto sutil aquí, por supuesto, es que $A$ es efectivamente definible en $\mathfrak{R}$ . Esto requiere un poco de cuidado; la cuestión es que, a pesar de Tarski, nosotros do tienen definiciones de verdad "locales" en $\mathfrak{R}$ en el sentido de que cada clase de complejidad "acotada" tiene su correspondiente predicado de verdad definible. En particular, existe una fórmula $\tau_\Pi$ definir en $\mathfrak{R}$ el conjunto de verdaderos-en $\mathfrak{R}$ $\Pi$ -sentencias (incluso podemos tener esta $\tau_\Pi$ ser un $\Pi$ -).