Constructivo de la prueba de Gödel ' s Teorema de completitud

Question

Como matemático interesado en las nuevas aplicaciones que yo estoy tratando de obtener una comprensión más profunda de (la no-constructivo) de Gödel del Teorema de Completitud y recientemente el estudio de dos textos: la Lógica Matemática para los Matemáticos (por Y. Manin) y el libro en el Reverso de las Matemáticas por Simpson [2009]. Después de haber leído Mendelsohn y Crossley (y otras obras) estoy realmente sorprendido por la no-constructivismo en esta prueba, debido al hecho de que muchos de los clásicos de la lógica de los textos no énfasis.

Sin embargo Manin hace hincapié en que las pruebas (y que él se presenta de 4 pruebas de integridad/compacidad) son todos a través del Axioma de Elección.

Mientras tanto, en el Reverso de las Matemáticas de trabajo nos enteramos de que el no-constructivo es identificado como el "Débil Konig del Lexema" (WKL) asunción. Veo que a partir de la revisión de la línea de resúmenes de Gödel original de la prueba de que Gödel utilizado Konig del Lexema en sí. Konig del Lema se encuentra en un nivel de "no constructivity clase" ACA en el Reverso de las Matemáticas, que WKL.

Ahora el problema que tengo con esta construcción es que tanto el Axioma de Elección y WKL no son verdades necesarias: podemos (creo) tienen un matemático universo en el cual ellos son negados. Sin embargo veo que WKL es comprobable en ZF. Por lo tanto Gödel Integridad del teorema no es una condición necesaria de la verdad - pero para ser un teorema de la lógica necesita ser necesario la verdad, no depende de otra suposición que seguramente?

En este papel Gödel termina su disertación con :

"esencial se haga uso de la principio del medio excluido para las colecciones infinitas... Quizás podría parecer que esto invalidaría todo el la integridad de la prueba."

En resumen tiene esta invalidación no se ha sugerido en los últimos años por el reconocimiento de los siguientes hechos no se conoce a Gödel o en 1930 ?:

1. Konig del Lema es una consecuencia del Axioma de Elección
2. La prueba puede ser reducido a la debilidad de Konig del Lema, pero no más allá
3. Axioma de Elección no es una lógica necesaria de la verdad (con sólo un matemático conveniencia)
4. Los teoremas de Turing Computabilidad teoría (que juegan un papel en la comprensión de la Lindenbaum Lema no constructivity desde otra perspectiva)

• o no, todo dependerá de si WKL (en contraposición a la CA) en realidad es el de la clásica rebatible?

EDIT: he vinculada a una pregunta que contiene la discusión sobre un tema relacionado.

Voy a agregar un resumen de algunos de los comentarios de abajo, para hacer la pregunta más autónomo. También tengo la esperanza de que va a hacer que responder que es más fácil si puedo añadir algo más de fondo.

En esta pregunta, estoy viendo la Lógica y las Matemáticas como independiente, pero la superposición de temas: hay aspectos de la Lógica no es relevante para las Matemáticas y viceversa. Esta pregunta es principalmente acerca de su título: la Construcción (o no) de Gödel Integridad del Teorema (GC) y las consecuencias de eso. Temas de matemática y los matemáticos de la filosofía sólo son relevantes si están directamente relacionados, como yo veo esto como una pregunta acerca de la Lógica.

Históricamente hay una particular línea de tiempo, que contiene algunos giros inesperados:

Gödel (1929) Tesis doctoral (Inédita) --- Contiene reparos acerca de la no-constructivo en GC

Gödel (1930) GC artículo Publicado --- Todos los reparos eliminado, dando la apariencia inicial de la construcción. Reinventa Konig del Lexema.

Kleene (1952) Intro. a MetaMathematics --- Prueba GC no uso constructivo de Gödel-Henkin prueba. Este utiliza "Lindenbaum Lema". Las reclamaciones que AC no es necesario en su prueba.

Textos posteriores (por ejemplo, Boolos-Jeffrey) --- No hay referencia a la no-constructivo en GC

Manin "la Lógica de los Matemáticos" --- "vamos a tener que usar el Lema de Zorn"

Inversa-Matemáticas - - - Débil Konig Lema de la GC

Por lo cual de todas estas es la correcta? Si una Respuesta fueron a reclamar que la GC era constructivo, entonces el Usuario tendrá que justificar la respuesta. Si una Respuesta fueron a reclamar que la GC no era constructivo, a continuación, tenemos al menos dos posibilidades: WKL o Zorn. Además, el último caso de re-abre Gödel original de no-Constructivo escrúpulos. Hacer estas dudas tienen ninguna validez - por ejemplo, hay un sentido en que no es "universalmente válida"?

Tenga en cuenta también que la GC es excepcional entre Gödel obra en la que se trabajan, en general, dentro de los constructivo marcos como con su Teorema de la Incompletitud, etc.

Ahora he estudiado otra prueba de GC por Hilbert-Bernays(1939). Este teorema se aplica solo en el dominio de la Aritmética (no juegos) y es de nuevo no constructiva. El "precio" que ha sido pagado por el no-constructivity es que el sistema se $\omega-$inconsistente (en lugar de - incompleta, ya que es un teorema de completitud). Resumiendo: una "verdadera" (instrucción para todos los números) puede ser falsificada por una prueba de su negación.

Ahora $\omega$-inconsistencia no existe para el general de los dominios, por lo que es el no-constructiva prueba todavía se considera totalmente válido? Puesto simplemente: ¿hay un nuevo tipo de Incompletitud de Gödel?

Answer 1

Aquí es una respuesta parcial.

El teorema de gödel se conecta lógica y teoría de conjuntos. La sintaxis es la parte de la lógica, que es donde las fórmulas y demostraciones en vivo; la teoría de conjuntos es la parte de la semántica, donde las interpretaciones y modelos en vivo. Por supuesto, uno puede tener de ellos trasladados a otros contextos, pero clásicamente creo que es un teorema acerca de la lógica y teoría de conjuntos.

Es comprobable sin el axioma de elección, que si tenemos un infinito árbol cuyos nodos son los números naturales, y cada nivel del árbol es finito, entonces no es una rama de ese árbol. Si se omite el requisito de que los nodos del árbol son los números naturales, que no se deterioren y contraejemplos no existen (por lo que me refiero, en consonancia con $\sf ZF$, por supuesto).

Del mismo modo, dada una contables lenguaje, escribimos la prueba del teorema de completitud para ese idioma, y todos los usos de la axioma de elección será mitigado por el hecho de que tenemos un uniforme de la enumeración de todos los objetos de interés. Por lo tanto, de algún fragmento de la integridad es el teorema de hecho comprobable, sin apelar a ningún axioma de elección.

Por otro lado, el teorema de completitud no es sobre contables de idiomas. Es acerca de cualquier lenguaje de la lógica de primer orden. De modo que podemos tener una gran cantidad de símbolos de función, o constantes, o así sucesivamente. Entonces, ¿qué acerca de la prueba? Así, se puede demostrar que si el idioma es bien disponible, a continuación, de hecho, podemos repetir los mismos argumentos y todo está bien-disponible de manera uniforme y todo está bien.

Pero, por desgracia, sin el axioma de elección, no todo conjunto puede ser bien ordenado. Y que cuando la no-naturaleza constructiva de la prueba se cuele. Permítanme darles un particular contraejemplo.

---

Ejemplo:

Decimos que un conjunto a $A$ amorfo si es infinito, y no puede ser escrito como un discontinuo de la unión de dos conjuntos infinitos. Uno puede mostrar que si $A$ es un conjunto amorfo, entonces no hay forma lineal del orden de $A$. Es decir, no es $R\subseteq A\times A$ tal que $(A,R)$ es un linealmente conjunto ordenado.

Supongamos que $A$ es un conjunto amorfo (y que es coherente que tal conjunto existe), y deje $\mathcal L$ ser el idioma en el que $<$ es una relación binaria símbolo, y para cada $a\in A$ hay una constante símbolo $c_a$.

Escribimos los axiomas, $\varphi$ es la conjunción de los enunciados $<$ es un orden lineal, y para cada distinto $a,b\in A$ escribimos $\varphi_{a,b}:=c_a\neq c_b$. Esta teoría es consistente, porque si fuera para probar un tipo de contradicción no sería un número finito de $a\in A$ cuyas constantes aparecen en la prueba, pero, a continuación, se puede construir un número finito de orden lineal que va a ser una interpretación de estos axiomas. Esto es imposible, por supuesto.

Sin embargo, la teoría como un todo, a pesar de ser coherente, no tiene un modelo. Porque en cualquier modelo de la teoría, la reducción sólo a las constantes se ha definido un orden lineal de $A$, e $A$ sí es un conjunto amorfo, por lo que no puede ser linealmente ordenado.

---

Entonces, ¿dónde está el axioma de elección que viene en el juego? Cuando construimos modelos necesitamos hacer algunas opciones arbitrarias a lo largo del camino. Cuando el idioma está bien-ordenó entonces podemos delegar esas decisiones para el bien ordenado y uniforme de hacer que todos ellos; pero cuando el lenguaje es un conjunto arbitrario que puede no ser bien disponible para empezar, entonces el axioma de elección es necesaria.

De hecho, se puede probar que el teorema de completitud (y su equivalente, el teorema de compacidad) es equivalente a la de ultrafilter lema, afirmando que cada filtro puede ser extendido a un ultrafilter. Todos estos también son equivalentes a muchos otros débiles elección de principios tales como el teorema de Tychonoff para espacios de Hausdorff, o el Booleano Primer Ideal teorema.

Así que lo que falta en esta respuesta? Bueno, yo no sé acerca de los contextos en donde la WKL no es comprobable, por lo que no puedo ayudar en ese aspecto. Pero espero que esta respuesta arrojar algo de luz en donde el teorema es el uso de fragmentos de elección y no de la construcción.

Answer 2

Si el axioma de elección no es una "lógica necesaria de la verdad", pero sólo un "matemático conveniencia", el mismo puede decirse de cada axioma de ZFC. Ninguno de ellos es una lógica de la verdad, después de todo. Incluso el axioma de inducción para los números naturales (en la aritmética de Peano) no es una lógica de la verdad.

En resumen, casi nada de interesante teorema de las matemáticas o de la lógica es una lógica de la verdad, a menos que se indique en el formulario de $H \to C$ donde $H$ es la conjunción de todos los axiomas necesarios para probar algunos teorema $C$. Generalmente, acabamos de estado "$C$" como un teorema, en lugar de indicar "Si estos axiomas poseen, por lo que no $C$".

Avigad, explica en su papel (vinculado en la pregunta) ¿qué Gödel significa por "anular". Avigad escribe,

Deseo destacar Gödel notable de la sensibilidad a la pregunta de qué es lo metamathematical métodos necesarios para obtener el requisito resultados y el impacto que estos métodos tienen en el epistemológica consecuencias

La palabra clave es "epistemológico consecuencias". El uso del axioma de elección para demostrar la integridad teorema de ZFC, o el uso de débil König del lema a probarlo en segundo orden de la aritmética, de ninguna manera disminuye la matemática exactitud del teorema. Pero el estudio de lo que son los axiomas necesarios para probar un determinado teorema tiene influencia en cómo interpretamos el teorema.

Por último, quiero destacar que el axioma de elección no está muy estrechamente relacionado con el constructivismo en matemáticas. Hay totalmente constructiva sistemas que incluyen el axioma de elección, y total no constructiva (como la de la teoría de conjuntos ZF) que no. Por lo que a menudo es un arenque rojo centrarse en si una prueba se usa el axioma de elección, porque muchas de las clásicas pruebas ya no constructiva mucho antes de que pruebe a utilizar ese axioma.