Sea T una teoría consistente y axiomatizable que extiende Q.

Question

Pregunta: Que $T$ sea una teoría consistente y axiomatizable que extienda $Q$ . Sea $P+$ sea el conjunto de (números de código para) sentencias demostrables a partir de $T$ dejar $P$ sea el conjunto de (números de código para) sentencias refutables a partir de $T$ . Demuestre que no existe ningún conjunto recursivo $R$ de forma que $P+ \subseteq R$ y $R\cap P = \emptyset$ .

Sé que se puede utilizar el lema diagonal. Hay una prueba para la que pensaba seguir el formato. Así que mi intento iba a ser suponer lo contrario. ¿Es este un buen enfoque, o qué me estoy perdiendo aquí? Me siento escéptico acerca de sólo seguir una prueba para el lema diagonal.

Answer 1

He aquí un esbozo.

Como sugieres, asume lo contrario e intenta deducir una contradicción. Así que asumiendo que existe tal recursividad $R$ se puede representar en $\mathcal{Q}$ mediante una fórmula $\phi$ . Es decir, $x\in R \leftrightarrow Q\vdash \phi (x). $

Diagonalizar $\phi$ . Si $G$ es la frase que diagonaliza $\phi$ entonces hay dos casos. O bien $\mathbb N \models G $ o $\mathbb N \models \neg G$ . En cualquier caso, los hechos de uso acerca de cuando las sentencias verdaderas en aritmética estándar puede ser demostrado por $\mathcal Q$ para deducir contradicciones.