6.1: Introducción a los Teoremas de Incompletitud

Última actualización
Guardar como PDF

Page ID: 113532

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Supongamos que\(A\) es una colección de axiomas en el lenguaje de la teoría de números tal que\(A\) es consistente y es lo suficientemente simple como para que podamos decidir si una fórmula dada es o no un elemento de\(A\). El Teorema del Primer Incompletitud producirá una oración\(\theta\),, tal que\(\mathfrak{N} \models \theta\) y\(A \nvdash \theta\), mostrando así nuestra colección de axiomas\(A\) es incompleta.

La idea detrás de la construcción de\(\theta\) es realmente ordenada: Llegamos\(\theta\) a decir que no\(\theta\) es demostrable a partir de los axiomas de\(A\). En cierto sentido, no\(\theta\) es más que una versión elegante de la Paradoja del Mentiroso, en la que el hablante afirma que el hablante está mintiendo, invitando al oyente a decidir si esa enunciación es una verdad o una falsedad. ¡El reto para nosotros es averiguar cómo conseguir una\(\mathcal{L}_{NT}\) sentencia para hacer la afirmación!

Notarás que hay dos partes para\(\theta\). El primero es que\(\theta\) habrá que hablar de la colección de Gödel números de teoremas de\(A\). Eso no es problema, ya que tendremos una\(\Sigma\) -fórmula\(Thm_A \left( f \right)\) que sea verdadera (y así demostrable a partir de\(N\)) si y sólo si\(f\) es el número de Gödel de un teorema de\(A\). Lo que hace\(\theta\) complicado es que queremos\(\theta\) estar\(Thm_A \left( \bar{a} \right)\), dónde\(a = \ulcorner \theta \urcorner\). En este sentido, necesitamos\(\theta\) referirnos a sí mismo. Demostrar que podemos hacer eso será el contenido del Lema de Auto-Referencia que abordamos en la siguiente sección.

Después de probar el Teorema del Primer Incompletitud, discutiremos algunos corolarios y mejoras al teorema antes de pasar a discutir el Teorema del Segundo Incompletitud, que establece que el conjunto de axiomas de la Aritmética de Peano no puede probar que la Aritmética de Peano es consistente, a menos que (por supuesto) Peano La aritmética es inconsistente, en cuyo caso puede probar cualquier cosa. Entonces nuestro objetivo de demostrar que tenemos un conjunto completo y consistente de axiomas para\(\mathfrak{N}\) es una meta que no se puede alcanzar dentro de los confines de la lógica de primer orden.