¿Cuál es la teoría en la que se demuestra la incompletitud de la AP?

Question

Tal vez sea una pregunta tonta, pero tengo que admitir que no me queda muy claro cuál es la teoría en la que se demuestra la incompletitud de la AP y de las teorías más fuertes. Los textos que he estudiado hasta ahora no suelen ser muy explícitos al respecto.

¿Cuál es la teoría (mínima) en la que se demuestra la incompletitud de la AP y de las teorías más fuertes?

Answer 1

Sea PRA la teoría de Aritmética recursiva primitiva . Se trata de una subteoría de PA, y basta con demostrar el teorema de incompletitud. Quizás no sea la teoría más fácil de trabajar, pero la cuestión es que se puede llevar a cabo una demostración de incompletitud en un sistema significativamente más débil que las teorías a las que se aplica realmente la incompletitud. A veces se argumenta que la noción de finitismo de Hilbert está capturada (con la mayor precisión posible) por la ARP, por lo que, en ese sentido, ésta es la configuración ideal para demostrar la incompletitud de la AP o de los sistemas relacionados.

Puede beneficiarse de la lectura del bonito libro Metamatemática de la aritmética de primer orden de Hájek y Pudlák, donde se analizan detenidamente estas cuestiones, así como algunos de los numerosos ensayos de Harvey Friedman, disponibles en su página web .

Permítanme señalar que lo que se prueba en el ARP es que o la AP es inconsistente o bien, no puede demostrar su propia consistencia (y por lo tanto es incompleta). Si realmente queremos demostrar que PA es incompleta, necesitamos razonar dentro de un sistema en el que se asuma Con(PA), el enunciado formal que afirma la consistencia de PA. (Por supuesto, Con(PA) no es un teorema de PA, así que en cierto sentido se trata de una suposición fuerte). Del mismo modo, la ARP basta para formalizar la incompletitud de sistemas mucho más fuertes, e incluso, para formalizar la equiconsistencia resultados de la teoría de conjuntos.

Algunas personas prefieren poder razonar con conjuntos (es decir, semánticamente, en lugar de con pruebas formales, que son objetos sintácticos) de una manera menos engorrosa que mediante la codificación. Entonces, en lugar de trabajar con ARP, es conveniente hacerlo con un subsistema débil de la aritmética de segundo orden. Normalmente, WKL ${}_0$ (Un sistema que nos permite demostrar una versión débil del lema de König que árboles infinitos de ramificación finita tienen infinitas ramas) es el sistema elegido para llevar a cabo la formalización de las pruebas de incompletitud. Un buen lugar para aprender sobre esto y sobre la aritmética de segundo orden en general es el maravilloso libro por Stephen Simpson.

Permítanme mencionar que los subsistemas de la aritmética de segundo orden se entienden como las teorías naturales para llevar a cabo investigaciones sobre matemáticas inversas Es decir, proporcionan precisamente el escenario que uno desea para estudiar cuestiones sobre qué sistemas formales son suficientes para demostrar un teorema (como la incompletitud de la AP, en este caso).