Programa de Hilbert: ¿La coherencia y la integridad implican decidibilidad?

Question

Tengo una pregunta sobre el Programa de Hilbert. A continuación voy a expresar mi comprensión actual de la es $($... si me sale algo mal, por favor me corrija!$)$ ... seguido por mi pregunta.

Grosso modo, el objetivo del Programa de Hilbert fue a buscar un 'sonido' y 'completo' conjunto de los axiomas de las matemáticas: un conjunto de axiomas que, lógicamente, implica que todos los $($'integridad') y sólo $($'solidez'$)$ matemática verdades.

Ahora, es mi entendimiento de que esta es 'grosso modo', porque matemático de la verdad' es un poco delicado noción: a diferencia de la 'lógica de la verdad', para el que tenemos una buena semántica formal $($al menos para la lógica de primer orden$)$, que no tiene una semántica formal para todos los de matemática de la verdad'.

Evitar la semántica, a continuación, el Programa de Hilbert era en realidad expresa como un sintáctica uno: en lugar de pedir un 'sonido' $($todos los verdaderos$)$ y el conjunto completo de axiomas, el objetivo era ofrecer una "coherente" y completa el conjunto de axiomas: un conjunto de axiomas a partir de la cual no se puede derivar tanto de $\varphi$ e $\neg \varphi$ para algunos declaración de $\varphi$. Asimismo, 'integridad' se entenderá puramente sintáctica así: por cada declaración de $\varphi$, podemos deducir cualquiera de las $\varphi$ o $\neg \varphi$. ... Aún así, supongo que el objetivo implícito era tener un conjunto de axiomas que al menos 'match', 'matemáticas verdades" como $1+1=2$

Finalmente, Hilbert fue con la esperanza de que habrá algún tipo de 'método eficaz' o algoritmo que podría decidir, por cualquier declaración de $\varphi$, si $\varphi$ fue derivable de los axiomas o no. Aproximadamente el traducir de esta de nuevo en la 'verdad': si no hay un algoritmo, podríamos decir que la 'verdad' es decidable. Esto es de Hilbert "Entscheidungsproblem"

OK, aquí está mi pregunta: ¿por Qué Hilbert agregar el criterio de decidability? No la coherencia y la integridad juntos implica decidability? Porque uno puede simplemente enumerar todas las posibles pruebas de $($como secuencias finitas de símbolos, el conjunto de todas las pruebas es enumerable$)$. Entonces, desde que por la integridad de cualquiera de $\varphi$ o $\neg \varphi$ es demostrable, en algún momento se va a ejecutar en una de esas pruebas. Si resulta ser una prueba de $\varphi$, entonces obviamente $\varphi$ es derivable/demostrable, y si nos encontramos con una prueba de $\neg \varphi$, entonces por coherencia sabemos que no hay ninguna prueba de $\varphi$. Así, podemos decidir si $\varphi$ es comprobable o no.

Estoy equivocado acerca de esto? Pero si no: ¿por qué Hilbert agregar explícitamente decidability a la coherencia y la integridad?

Answer 1

Milo Brandt comentario es exactamente correcto. El problema es cuando se escribe

uno puede simplemente enumerar todas las posibles pruebas

Para hacer esto, uno debe ser capaz de identificar pruebas válidas. Esto sólo es posible si sabemos lo que los axiomas son: en una teoría de la $T$, la secuencia "$\langle\varphi\rangle$" es una prueba válida de $\varphi$ fib $\varphi$ es un axioma de la $T$. De hecho, las tres condiciones que son completamente independientes el uno del otro, en el sentido de que podemos tener cualquiera de los dos sin la tercera:

• Una teoría es inconsistente tanto decidable y completa (prueba de todo), pero no consistente.

  • Tenga en cuenta que algunos textos definen "completa" que incluye consistencia: $T$ es completa iff para cada oración $\varphi$, $T$ demuestra exactamente uno de $\varphi$ e $\neg\varphi$. Pero de Hilbert es el uso de los más débiles de la noción de integridad aquí, que permite la inconsistencia.

• Si $\mathcal{A}$ es cualquier estructura, el conjunto de todos los axiomas cierto en $\mathcal{A}$ - la teoría de $\mathcal{A}$, $Th(\mathcal{A})$ - es consistente y completa, y el segundo significa $\mathcal{A}\models\neg\varphi$), pero en general no necesitan ser decidable (tome $\mathcal{A}=(\mathbb{N};+,\times)$).

  • En un poco más de detalle (ya que se ha pedido aquí antes): $Th(\mathcal{A})$ tiene un modelo, es decir, $\mathcal{A}$, y así es consistente por la solidez teorema. La integridad de $Th(\mathcal{A})$ viene de la perspectiva de la definición de "$\models$:" por definición, $\mathcal{A}\not \models\varphi\implies\mathcal{A}\models\neg\varphi$, y por lo que sea a $\varphi\in Th(\mathcal{A})$ o $\neg\varphi\in Th(\mathcal{A})$.

• La teoría de la algebraicamente cerrado campos es decidable y consistente, pero no completa (no especifica la característica).

  • Una de las menos interesantes, pero más simple ejemplo: pensemos en el lenguaje que contiene un único predicado unario $U$ y la teoría de la $T=\{\exists x\forall y(x=y)\}$; a continuación, esta teoría tiene exactamente (hasta el isomorfismo) dos modelos, cada uno de los cuales tiene un elemento, que sólo difieren en si $U$ tiene de que uno de los elementos. $T$ es claramente consistente y decidable - para saber si $T\vdash\varphi$, sólo comprobar si $\varphi$ que es verdad en cada uno de los dos modelos de $T$, y tenga en cuenta que la comprobación de si un enunciado es verdadero en un finitos de la estructura (en un lenguaje finito) es computable. Sin embargo, no es completa, ya que no decide si $\forall x(U(x))$ es cierto.

---

EDIT: Es importante en este punto señalar que el teorema de Gödel hace no implica que no es completa, coherente, decidable teoría! Por ejemplo, la teoría de la algebraicamente cerrado campos de la característica $17$ (decir) es completa, coherente, y decidable, y una más trivial ejemplo está dado por la teoría de la $\{\exists x\forall y(x=y)\}$ en el vacío del lenguaje.

Donde Gödel aparece cuando tratamos a veces en un cuarto requisito, diciendo que la teoría es lo suficientemente fuerte (por ejemplo, "contiene PA"). Esto es lo que el "matemáticas" significa "el objetivo del Programa de Hilbert fue a buscar un 'sonido' y 'completo' conjunto de los axiomas de las matemáticas" - queremos una teoría que es capaz de "ejecución" (en algún sentido razonable) todas nuestras matemáticas, y algo así como algebraicamente cerrado campos de la característica $17$ simplemente no se corte.

Answer 2

Comentario muy largo, para tratar de dar una visión de Hilbert enfoque.

Ver : David Hilbert & Wilhelm Ackermann, los Principios de la Lógica Matemática-Chelsea (inglés trad. de la 2ª a la alemana, ed. 1938).

Página 87 :

§ 9. La coherencia y la Independencia del Sistema de Axiomas

El método de interpretación aritmética, que previamente fueron capaces de obtener una idea de la consistencia y la independencia de los Axiomas a) a d) [los axiomas del cálculo proposicional], también hace posible para nosotros reconocer que la totalidad del sistema de axioma de que el predicado de cálculo es consistente.

Página 88 :

No debemos, por cierto, sobreestimar la importancia de este consistencia de la prueba. Esto equivale a decir que se asume que el dominio de los individuos que subyacen a los axiomas que constan de un solo elemento, y por lo tanto ser finito. No tenemos absolutamente ninguna garantía de que la introducción formal de los postulados de la inobjetable en cuanto a su contenido deja el sistema de teoremas coherente. Por ejemplo, la pregunta sigue sin respuesta si la adición de los axiomas matemáticos no sería, en nuestro cálculo, hacer cualquier fórmula demostrable. Este problema, cuya solución es de fundamental importancia para las matemáticas, es incomparablemente más difícil que la cuestión tratada aquí. Los axiomas matemáticos en realidad suponer un infinito de dominio de los individuos, y no están relacionados con el concepto de infinito las dificultades y paradojas que desempeñan un papel en la discusión de los fundamentos de las matemáticas.

Página 92 :

§ 10. La Integridad del Sistema de axiomas

Nos comentó en el primer capítulo que la integridad de un sistema de axiomas puede ser definido de dos maneras. En el sentido más fuerte de la palabra, la integridad significa que la adición de una improbable fórmula para el sistema axiomático siempre se obtiene una contradicción. No tenemos este tipo de exhaustividad aquí [es decir, en el caso de los restringida predicado de cálculo].

Página 95 :

Habiéndose demostrado que el sistema axiomático no es completo en el sentido fuerte de la palabra, podemos preguntarnos si hemos integridad en el otro sentido, se define [arriba]. La pregunta aquí es si todos universalmente válidas las fórmulas del cálculo de predicado, como se define en el principio de este capítulo, se puede demostrar en el sistema axiomático. De hecho tenemos la exhaustividad en este sentido. La prueba es debido a K. Gödel, cuya exposición vamos a seguir.

Página 101 :

§ 11. La derivación de las Consecuencias de los Locales; la Relación Universalmente Válidas las Fórmulas

Hasta ahora hemos utilizado el predicado de cálculo sólo para deducir fórmulas válidas. Los locales en nuestras deducciones, viz. Axiomas de a) a f), fueron ellos mismos de una forma puramente lógica de la naturaleza. Ahora vamos a ilustrar con algunos ejemplos de los métodos generales de formal derivación en el predicado de cálculo, que previamente, antes de que los axiomas fueron establecidos, podría ser meramente esbozado. Ahora es una cuestión de la que se derive de las consecuencias de cualquier instalación que sea, ya no de una pura lógica de la naturaleza.

Página 107 :

El método explicado en esta sección de la derivación formal de los locales, que no son universalmente válidas lógica de las fórmulas tiene su principal aplicación en la configuración de la primitiva frases o axiomas para un determinado campo del conocimiento y de la derivación de el resto de los teoremas de ellos como de las consecuencias. Incluso puede decirse que sólo ahora es el concepto de un sistema de axiomas formulados con precisión; para, una completa axiomatization no sólo debe incluir la configuración de los axiomas mismos, pero también la declaración exacta de la lógica de los medios que nos permiten obtener nuevos teoremas a partir de los axiomas. Vamos a examinar, al final de esta sección, la cuestión de si cada declaración en la que se haría de forma intuitiva ser considerada como una consecuencia de los axiomas pueden ser obtenidos por medio del método formal de la derivación.

Página 108 :

La siguiente pregunta que se plantea ahora como un problema fundamental: ¿Es posible determinar si es o no un determinado declaración relativa a un campo de conocimiento es una consecuencia de los axiomas ?

Queremos mostrar que este problema puede ser reducido a un puro cálculo de predicado, es decir, el cálculo que contiene sólo el predicado y las variables individuales. Para la pregunta de la lógica de la dependencia de una declaración sobre un sistema de axiomas puede ser reducida a la pregunta de si una determinada fórmula de la pura predicado de cálculo es o no es universalmente válida. Sin embargo, esto sólo se aplica si el axioma del sistema es de primer orden.

Página 112 :

§ 12 De La Decisión De Problema

A partir de las consideraciones de la sección anterior, surge la importancia fundamental de la determinación de si o no una determinada fórmula de cálculo de predicado es universalmente válida. De acuerdo a la definición dada [arriba], la validez universal de una fórmula significa lo mismo que su validez universal en todos los dominios de los individuos. El problema que acabamos de mencionar se llama el problema de la validez universal de una fórmula. Más precisamente, en vez de validez universal, se habla de validez universal en todos los dominios de los individuos. La validez universal de las fórmulas del cálculo de predicado son precisamente aquellas fórmulas que son deducible de los axiomas del sistema de [predicado de cálculo]. Este hecho no produce una solución del problema de validez universal, ya que no tenemos criterio general para la deducibility de una fórmula [énfasis añadido]. [...] Es habitual referirse a los dos problemas equivalentes de validez universal y satisfiability por el nombre común de la decisión del problema de la restricción del predicado de cálculo. Como se señaló [arriba], estamos justificados en llamarlo el principal problema de la lógica matemática.

Página 119 :

Ahora un informe sobre los casos particulares más importantes en los que el éxito de una solución del problema de decisión ha sido alcanzado. [...] El teorema de que para cualquier fórmula de la predicado de cálculo podemos encontrar uno que sea equivalente, en el respeto a satisfiability y que contiene sólo monádico y predicado diádico variables, tiene su analogía en el teorema de que la decisión que el problema ha sido resuelto para todas las fórmulas que contienen sólo predicado monádico variables.

Página 124 :

Resultados por A. de la Iglesia basado en los trabajos de K. Gödel demuestra que la búsqueda de una solución general del problema de decisión debe ser considerado como un desesperado. Podemos informar sobre estas investigaciones en detalle dentro de los límites de este libro. Vamos sólo la observación de que un método general de decisión ,vould constan de un determinado procedimiento recursivo para el individuo fórmulas que finalmente rendimiento para cada fórmula el valor de la verdad o el valor de la mentira. Trabajo de la iglesia demuestra, sin embargo, la no existencia de un procedimiento recursivo; al menos, la necesaria recursiones no caen bajo el tipo general de la recursividad establecido por la Iglesia, que ha dado el poco vaga intuitivo concepto de recursividad cierto precisa la formalización.