¿Teórica de Gödel?

Question

Estoy buscando una teoría de la información de la prueba de Gödel del Teorema que dice algo como esto, sin referencia alguna a la diagonalización:

1. Cada sistema axiomático en el ámbito de aplicación del Teorema de Gödel tiene un número finito de bits.
2. Se requiere de un infinito número de bits para especificar el todas las verdades de la teoría de números.
3. Por la Solidez teorema, no hay nuevos bits puede ser introducido por deducción.
4. Así que no hay tal sistema axiomático como se especifica en la parte 1 anteriormente plenamente axiomatize la teoría de números.

Hace una prueba de que existen? Es aún posible? Por favor, incluir referencias con su respuesta. Gracias

Answer 1

Es posible que desee echar un vistazo a esto: http://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem

Sin embargo, parece que la diagonalización se usa, para generar la cadena paradójica (para la cual la complejidad no puede ser probada).

Answer 2

Creo que las partes (1) y (2) ya probarían el teorema. El corazón es parte (2), que expresó otra manera dice que "ningún número finito de bits puede codificar todas las verdades de la teoría numérica". Lo difícil con la prueba sería dar sentido formal a "número finito de bits".

Answer 3

Esto no tiene ningún sentido para mí. Sí, algunos sistemas axiom pueden ser anotados usando un número finito de bits. De estos axiomas pueden deducirse infinidad de teoremas. ¿No requiere infinitamente muchos bits para especificarlos? ¿Cómo distingue su "prueba" entre los sistemas completos, como la aritmética de Presburger, y los sistemas que no lo son?