¿Dónde está el error en esta "prueba" de la inconsistencia de ZFC?

Question

Esta es una "prueba" de que ZFC es incoherente, pero aún no he encontrado el error.

Sea $\{\varphi_n \colon n <\omega\}$ sea una enumeración de todas las fórmulas de $L_{\in}$ con exactamente una variable libre. Consideremos la fórmula $$\psi(x) \equiv x \in \omega \land \lnot \varphi_x(x) \, .$$ Desde $\psi$ es una fórmula con una variable libre, entonces $\psi$ es $\varphi_k$ para algunos $k$ . Pero entonces, $$\mathrm{ZFC} \vdash \varphi_k(k) \leftrightarrow \psi(k) \leftrightarrow \lnot \varphi_k(k)$$

Le he dedicado mucho tiempo a esto, pero sigo sin poder descubrir el error en la prueba falsa que hay aquí. ¿Alguien puede darme una pista?

Answer 1

El problema es que no hay manera de escribir $\varphi_n(x)$ uniformemente en ZFC mediante una única fórmula $\phi(n,x)$ . Si quisieras una forma de enumerar las fórmulas unarias de $L_\in$ en ZFC entonces no estarán en la representación que quieres aquí, más bien estarían en la forma de numeración de Godel. Entonces si ZFC pudiera probar el esquema $\mathsf{Prov}(\lceil\varphi_n\rceil)\to\varphi_n$ para cada $n$ entonces sí que sería incoherente. Todo esto es válido también para algo mucho más débil que ZFC.

Answer 2

Como otros han sugerido, la clave está en pensar cómo escribiríamos realmente el predicado $\psi(x)$ en $L_\in$ . No es tan sencillo como lo pintan. Por ejemplo, si $\varphi_0$ es $x=x$ y $\varphi_1$ es $\forall y(y\in x),$ querríamos $\varphi_0(0)$ ser $0=0$ y $\varphi_1(1)$ ser $\forall y(y\in 1).$ Está claro que no se trata sólo de dos instancias de alguna fórmula $\psi(x)$ con $0$ y $1$ enchufado para $x$ respectivamente. Ha confundido el " $n$ " en $\varphi_n$ con el número entero en la teoría formal. En realidad, este $n$ es de una enumeración que hemos creado en el exterior (es decir, en la metateoría), hablando acerca de la lengua, no en ella.

Así que lo mejor que puede esperar es escribir algo equivalente dentro de $L_\in,$ mediante la formalización de la sintaxis (es decir, codificando las fórmulas como conjuntos). Ciertamente, se pueden formalizar y enumerar las fórmulas de una variable de $L_\in,$ y también se puede formalizar la operación de sustitución de un parámetro establecido por una variable. Hasta aquí todo bien, pero para terminar, tienes que escribir una frase que signifique " $k\in\omega$ y $\varphi_k(k) $ no se sostiene".

Es el " $\varphi_k(k)$ no se sostiene" que es problemática. Requiere que tengas un predicado de verdad que tome el código de una frase y te diga si se cumple o no. De hecho, otra forma de ver lo que has escrito es como una prueba de que este predicado de verdad no se puede expresar en $L_\in$ . Se trata de una versión de Teorema de Tarski .

Edición: En línea con lo que otros han señalado, el teorema de Tarski no es particular de la teoría de conjuntos. De hecho, su prueba falsa sólo utiliza un pequeño aspecto de ZFC: que puede representar números. Así que también podría ser una prueba falsa de la inconsistencia de PA. Convertir esta prueba falsa de inconsistencia en una prueba real del teorema de Tarski sólo requiere cierta formalización de la sintaxis, como ya he explicado, y un análisis más detallado te mostrará que no necesitas expresar o demostrar mucho sobre aritmética para que funcione.

Answer 3

"ZFC" es una pista falsa. $ \def\eq{\Leftrightarrow} \def\nn{\mathbb{N}} $

Tomemos cualquier teoría de primer orden $S$ y cualquier $2$ -parámetro frase $P$ en $S$ . Sea $Q(x) :\equiv \neg P(x,x)$ . Entonces $Q$ es un $1$ -frases de parámetros y $S$ prueba trivialmente " $\forall y \exists z ( \neg Q(z) \eq P(y,z) )$ ". Ahora observe que si $S$ tiene un lenguaje contable y también tiene un conjunto contable $T$ de términos demostrablemente distintos, entonces todos $1$ -frases de parámetros sobre $S$ pueden enumerarse y ponerse en biyección con la interpretación de $T$ en cualquier modelo de $S$ . Sin embargo, el hecho anterior demuestra que no $2$ -parámetro frase sobre $S$ puede capturar cualquier enumeración de este tipo, a pesar de $T$ que parece proporcionar suficientes objetos

Por ejemplo, no $2$ -parámetro frase $P$ sobre PA representa (en el sentido anterior) una enumeración de todos los $1$ -frases de parámetros $X$ sobre PA, a pesar de que existe una biyección concreta entre los términos $N = \{``$ 1 $", ``$ 1+1 $", ``$ 1+1+1 $", \cdots \}$ y $X$ . Además, existe una biyección computable $r$ de $N$ a $X$ y, por tanto, podemos construir explícitamente a $2$ -parámetro frase $R$ sobre PA tal que para cada $t \in N$ y $Q \in X$ tenemos que $\text{PA} \vdash R(c(t),c(Q))$ si $r(t) = Q$ y $\text{PA} \vdash \neg R(c(t),c(Q))$ si $r(t) \ne Q$ . Qué hacemos no tiene es un $2$ -sobre PA que alcanza el valor valores de verdad de una enumeración de $X$ .

Llamo a este fenómeno una versión sintáctica del teorema de Cantor, porque el teorema de Cantor dice que no existe una enumeración contable de funciones de $\nn$ a booleanos, y aquí hemos demostrado que no existe una enumeración "sintáctica" de predicados sobre $S$ .