Gödels incompleteness vs incompleteness

Question

Esto ha estado molestando, y podría ser un inepto pregunta, pero aún así:

Me han enseñado que la integridad de una teoría de la $T$ significa que para cualquier frase, $\varphi$ en el lenguaje de la teoría, tendremos a $T \vdash \varphi$ o $T \vdash \neg\varphi$. Si esta propiedad no se mantiene (así que si hay algo de $\varphi$ que la teoría no dice nada acerca de), tenemos una teoría incompleta.

Ahora, la copia de la wikipedia, tenemos:

El primer teorema de la incompletitud de los estados que no coherente del sistema de axiomas cuyos teoremas pueden ser enumerados por un "procedimiento efectivo" (por ejemplo, un programa de ordenador, pero podría ser cualquier tipo de algoritmo es capaz de demostrar todas las verdades acerca de las relaciones de los números naturales (aritmética).

Estas dos nociones de integridad parecen muy lejos el uno del otro, y cuando pido a otros que saben más acerca de esto, me dicen que es incompleto en un sentido diferente, y que es demasiado técnico para cubrir brevemente. Así que la pregunta es:

¿Hay alguna diferencia entre mi comprensión de la incompletitud, y el de Gödel significaba? Y ¿cómo algoritmos encaja en todo esto?

Quiero que el 'philosphical la diferencia, no los bocetos de Gödel de las pruebas.

Gracias de antemano.

Answer 1

La integridad de $T$ significa que por cada frase $\varphi$ le tienen o $T\vdash\varphi$ o $T\vdash\neg\varphi$.

Gödel de la incompletitud teorema muestra que si $T$ es un eficaz la teoría de que puede expresar "suficiente" de la aritmética y no prueba aritmética falsedades (lo que implica que es constante), entonces no puede ser completa en el anterior sentido.

El teorema se hace mostrando que no es una verdadera pena que no se puede demostrar. Puesto que suponemos que la teoría no es prueba de falsedades, esto significa que la teoría demuestra que ni la sentencia de Gödel o de su negación, lo que significa que no está completo.

Answer 2

Gödel (bueno, en realidad Rosser edificio de Gödel) mostró que cualquier coherente, recursivamente axiomatizable conjunto de oraciones en el lenguaje de la aritmética, que contiene una cierta (muy pequeño) la teoría de la $T_0$ no está completa (en su sentido, que es lo que "completa" significa). En particular, esto significa que no hay recursivamente axiomatizable conjunto de oraciones en el lenguaje de la aritmética demuestra cada enunciado verdadero de la aritmética (no necesitamos el "contiene $T_0$" poco aquí).

Nota, sin embargo, que (Rosser la mejora de) el teorema de Gödel se aplica también a las teorías que contienen declaraciones de verdad no de $\mathbb{N}$ ("$PA$ es inconsistente," "Goodstein procesos no siempre terminar", etc.) - siempre que contengan $T_0$!

¿Qué es $T_0$? Gödel original de la prueba de establecer explícitamente $T_0$ a ser el sistema de los Principia Mathematica; sin embargo, básicamente con sólo mirar la prueba de que podemos tomar $T_0$ a ser muy, muy débiles $I\Sigma_1$; este es un muy pequeño fragmento de la aritmética de Peano! Con un poco de trabajo, $T_0$ puede ser debilitado aún más a la de Robinson teoría de la $Q$, y creo que incluso se sabe.

---

Entonces, ¿qué acerca de los supuestos? He aquí por qué ellos no pueden ser eliminados:

• "Contiene $T_0$:" considerar la teoría (generados por) "$\exists x\forall y(x=y)$." Esta teoría es, obviamente, coherente y completa y de forma recursiva axiomatized (de hecho, decidable :P), pero no contiene, digamos, de Robinson $Q$. (Como alternativa, no contienen una afirmación que es falsa.)

• "Recursivamente axiomatizable:" la verdadera teoría de la aritmética es ciertamente completo, y contiene, además de todos los de la aritmética; pero no es recursivamente axiomatizable.

Answer 3

Tal vez ayuda a la hora de distinguir la sintáctica versión de la semántica de la versión. Así que tenemos algo así como la siguiente

Gödel primer teorema de la incompletitud (sintáctica): Cada sistema lógico, que es coherente y lo suficientemente fuerte como para formalizar PA, es la negación incompleta.

que es el "original" uno (bueno, para ser precisos usted tiene que hablar de la más fuerte noción de lo que se denomina $\omega$-consistencia cuando se trata de Gödel, porque Rosser contribuido el resto) y

Gödel primer teorema de la incompletitud (semántica): Cada sistema lógico, que es sano y lo suficientemente fuerte como para formalizar PA, es incompleta.

La semántica de la versión puede ser mostrado como una consecuencia de la undecidability de la detención problema, que se conecta a prueba la teoría y la recursividad (la computabilidad) de la teoría.

Saludos, Heywood