¿Cómo puedo demostrar que este conjunto no es aritmético?

Question

Dejemos que $\Sigma = \left\{ 0,1,+,\times , < \right\}$ sea una firma, donde los últimos 3 símbolos tienen aridad 2 y todos, excepto el último, son símbolos de funciones. ¿Cómo puedo demostrar que el conjunto $X=\left\{ \ulcorner A \urcorner \ : \mathbb{N} \vDash A \right\}$ , donde $ \ulcorner A \urcorner $ es el código del $\Sigma$ fórmula $A$ y " $\vDash$ " significa "es un modelo de", no es aritmética ?

Puedo utilizar el hecho de que el conjunto $$B=\left\{ (c,n)\in \mathbb{N}^2\left| \begin{array}{l} c= \ \ulcorner T \urcorner\text{, where } T \text{ is a } \Sigma \text{ formula that}\\ \text{ has only } v_0 \text{ as a free variable, and }\mathbb{N} \vDash T_{v_0 \rightarrow \underline{n}} \end{array}\right.\right\},$$ donde $A_{v_0 \rightarrow \underline{n} }$ es el $\Sigma$ fórmula era la variable $v_0$ en $T$ se sustituye por el término $ \underline{n}$ (que corresponde al número $n$ significa $ \underline{n}=++\ldots+011\ldots1$ donde hay $n$ símbolos adicionales) no es aritmética.

Lo que tengo hasta ahora es lo siguiente: Supuse, que $X\subseteq \mathbb{N}$ eran aritméticos. Por lo tanto, existe un $\Sigma$ fórmula $\psi$ que tiene exactamente una variable libre $v$ tal que $\psi_\mathbb{N}=X$ (hemos definido $\psi_\mathbb{N} =$ { $ m \in \mathbb{N}: \mathbb{N} \vDash \psi_{v \rightarrow \underline{m}} $ } - y si la fórmula contiene 2 variables libres, la definición cambia en consecuencia). De este modo, puedo introducir $\psi$ en el conjunto $B$ . Pero este es el punto a partir del cual no sé cómo continuar - y todavía no he utilizado el hecho de que $B$ no es aritmética también.

(Para más información, en cuanto a cómo $\Sigma$ Las fórmulas, etc., se definieron en mi curso, véase esto Correo electrónico: )

Answer 1

Aquí hay dos pruebas separadas.

• En primer lugar, si su conjunto $X$ fuera aritmética, entonces tendría una complejidad $\Sigma_n$ para algún número natural específico $n$ . Pero en este caso, seríamos capaces de expresar la verdad de $\Sigma_{n+1}$ declaraciones, o de hecho, $\Sigma_m$ declaraciones para cualquier $m$ utilizando sólo la complejidad $\Sigma_n$ diciendo que un $\Sigma_{n+1}$ declaración $\varphi$ tiene en $\vec n$ si ${}^\ulcorner\varphi(\vec n){}^\urcorner\in X$ . Así, la jerarquía aritmética se colapsaría a nivel de $\Sigma_n$ . Pero la jerarquía aritmética no se colapsa. Esto se puede demostrar primero probando que hay un universal $\Sigma_1$ conjunto, que no puede ser $\Pi_1$ por un simple argumento de diagonalización, y luego demostrar que existe un $\Sigma_n$ -conjunto para cada $n$ que no puede ser $\Pi_n$ .

• La segunda prueba, nota que tu afirmación es exactamente Teorema de Tarski sobre la no definibilidad de la verdad y hay una prueba elegante a través del lema del punto fijo. A saber, supongamos que tenemos una expresión aritmética para decir que " $\varphi(\vec n)$ es verdadera", es decir, una fórmula $\psi$ tal que $\mathbb{N}\models\psi(^\ulcorner\varphi(\vec n)^\urcorner)\iff\varphi(\vec n)$ . Por el lema del punto fijo, existe una frase $\sigma$ tal que PA demuestra $\sigma\iff\neg\psi(^\ulcorner\sigma^\urcorner)$ . Así, $\sigma$ afirma que $\sigma$ no es cierto, al igual que la paradoja del mentiroso. Es fácil ver que esto es contradictorio, ya que si $\sigma$ es cierto entonces no lo es y a la inversa.

Es interesante observar que el teorema de Tarski puede verse como una versión mucho más fuerte del teorema de incompletitud de Gödel. Esto se debe a que una versión del teorema de incompletitud dice que la verdadera teoría de la aritmética no es computablemente axiomatizable. Pero esto se deduce inmediatamente del teorema de Tarski, ya que si la verdadera teoría de la aritmética fuera axiomatizable computacionalmente, entonces sería fácilmente definible, con complejidad $\Sigma_1$ ya que podríamos definir el conjunto de aseveraciones verdaderas como aquellas que son demostrables en el sistema. Mientras tanto, el teorema de Tarski dice que no sólo no hay una axiomatización completa computable de la aritmética verdadera, sino que no hay una axiomatización definible aritméticamente de la aritmética verdadera.

También es interesante señalar que a Tarski se le atribuye tanto la definición recursiva de primer orden de la verdad como la demostración de que la verdad no es definible. (Pero, a pesar de las apariencias superficiales, estas afirmaciones no entran en conflicto).