Supongamos que no hay una prueba en PA de si alguna TM se detiene o no.
Supongamos además que TM no se detiene y que PA es consistente. ¿Es necesario que PA+TM se detenga?
¿Es el paro de PA+TM necesariamente consistente?
Respuesta
¿Demasiados anuncios?Supongamos que $PA$ es consistente.
Supongamos que $PA+S$ , donde $S$ es cualquier declaración, es inconsistente. Entonces $PA+S$ prueba $0=1$ . Esto significa que $PA$ solo demuestra $S\Rightarrow 0=1$ Así que $PA$ muestra que una afirmación falsa se desprende de $S$ Así que $S$ debe ser falso. Por lo tanto, $PA$ prueba $\neg S$ .
Por contraposición, si $PA$ hace no mostrar $\neg S$ entonces $PA+S$ es consistente. Aplique esto a $S$ siendo "TM se detiene" y "TM no se detiene" para conseguir que sea consistente que, respectivamente, TM no se detenga y que se detenga.