Comprender un paso del teorema de Gödel

Question

Estoy tratando de entender esta prueba del teorema de Gödel: https://mat.iitm.ac.in/home/asingh/public_html/papers/goedel.pdf

En la página 3 dice:

Sea $B_1(n), B_2(n), ...$ una enumeración de todas las fórmulas que tienen exactamente una variable libre. Considera la fórmula $¬P(B_n(n))$. Esta es una en la lista anterior, digamos $B_k(n)$.

Esta es una afirmación autocontenido, donde $P(X)$ puede ser cualquier forma de transformar un predicado $X$ en un nuevo predicado $P(X)$. Entiendo que para todo número natural $k$ podemos considerar la fórmula $¬P(B_k(n))$ dependiendo de la variable libre $n$. Así que existe un $j$ tal que $B_j(n) = ¬P(B_k(n))$. Pero no veo por qué podemos suponer que $j=k$.

¿Me puedes ayudar a explicar ese pasaje?

Answer 1

Una cosa que parece un poco sospechosa en la formulación es que $B_n(n)$ aparentemente usa la letra $n$ tanto como variable en el metanivel (para poder hablar sobre la fórmula número $n$) y como variable de objeto.

Lo que probablemente significa, dado cómo generalmente va la construcción de Gödel, es $ \neg P( B_n(\bar n))$ donde $\bar n$ significa el numeral para $n$ -- o en otras palabras $$ \neg P( B_n(\underbrace{SS\cdots S}_n 0)) $$ Entonces esperanzadoramente es más claro que "$B_n(\underbrace{S\cdots S}_n0)$" es una receta para construir una particular oración una vez que se haya dado un $n$. Entonces en el metanivel $\neg P(B_n(\bar n))$ pregunta si la oración que construimos es demostrable. Esto puede ser escrito como una fórmula aritmética con $n$ como variable libre, y por lo tanto aparece en algún lugar de la enumeración $B_1, B_2, \ldots, B_k, \ldots$. Luego dejamos que $k$ sea su número

Answer 2

No consideramos la fórmula $\neg P(B_k(n))$ para todo $k$, consideramos la fórmula única $\neg P(B_n(n))$ - $n$ es variable en esta fórmula, no solo un parámetro (es una de las partes más importantes en la prueba - que podemos usar una variable como número de fórmula).

Como la enumeración fue total, hay un $k$ tal que $\vdash B_k(n) \leftrightarrow \neg P(B_n(n))$ para cualquier $n$. La parte importante es que $k$ es una constante, la misma para todos los $n$. Entonces, como $\vdash B_k(n) \leftrightarrow \neg P(B_n(n))$ es cierto para cualquier $n$, podemos sustituir $n = k$ y obtener $\vdash B_k(k) \leftrightarrow \neg P(B_k(k))$.