¿Qué tiene de malo esta definición de predicado de verdad?

Question

El teorema de Tarski, interpretado en la Aritmética de Peano, dice que no hay predicado $T$ tal que $PA\vdash T(\phi)\leftrightarrow \phi$ . Sin embargo, sabemos que existen predicados de verdad parcial para cada $k< \omega$ tal que, para todo $\phi \in \Sigma_k$ , $PA\vdash T_k(\phi)\leftrightarrow \phi$ . ¿Qué hay de malo en este supuesto predicado de verdad, que llamaré $T_\omega$ ? Lo definiré mediante un algoritmo recursivo.

En entrada $\phi$ determine $k$ como el menos $j$ tal que $\phi\in\Sigma_j$ . A continuación, salida $T_\omega(\phi) = T_k(\phi)$ .

Answer 1

Eso no es realmente un algoritmo en el sentido de un proceso computable: ya, la comprobación de la verdad de $\Sigma_1$ no es computable.

Y si pasamos al lenguaje de, bueno, el lenguaje, las cosas no van mejor. Es de suponer que la fórmula que tienes en mente es algo así como

$\varphi$ es verdadera si $T_k(\varphi)$ donde $\Sigma_k$ es la complejidad óptima de $\varphi$ .

Determinación de $k$ es, por supuesto, fácil. El problema es que esencialmente has cuantificado sobre el $T_k$ s. Esto sólo se puede hacer si se puede batir una fórmula $T(x,y)$ donde para cada $k$ la fórmula $T(\underline{k}, y)$ corresponde a $T_k(y)$ ... pero eso es exactamente lo que estás tratando de hacer aquí.

Dicho de otro modo, aunque la secuencia de fórmulas $(\psi_i)_{i\in\mathbb{N}}$ es tan simple como se desee (por ejemplo, computable), expresiones como $$\forall x(P(x)\rightarrow \psi_x(a))$$ son no fórmulas de primer orden: no podemos tener "fórmulas variables".