Prueba por contradicción e Incompleteness

Question

¿El teorema de incompletitud de Gödel implica que las pruebas por contradicción no funcionan?

Answer 1

No claro que no. Pruebas por contradicción "trabajo" debido a la Ley del Medio Excluido: si no-S es falso, entonces S debe ser verdadero. Godel dice que (en un sistema formal con ciertas propiedades) existen enunciados S tales que ni S ni not-S pueden ser probados. Pero eso no es lo mismo que decir que ni S ni no-S son verdaderas.

Answer 2

No. Y quizás uno debe detenerse ahí.

Muchas teorías están incompletos, porque nosotros queremos que sean. Mira por ejemplo en la teoría elemental de grupos. Es fácil escribir una frase que dice que el grupo tiene al menos $47$ elementos. Esta frase no es ni demostrable (después de todo, no son grupos con $46$ o menos elementos), ni es su negación demostrable.

Pero cuando buscamos axiomatizations para algo como elementales de la teoría de números, nos gustaría elegir los axiomas de modo que la sentencia sea comprobable o rebatible. Por desgracia, resulta que si queremos que nuestra colección de axiomas para ser recursivo, y queremos que todos los axiomas cierto en los enteros no negativos, no podemos hacer eso. Demasiado malo, pero no es bello que se puede demostrar que no podemos hacer eso?

Pruebas por contradicción de trabajo en todas partes, tanto para las teorías que están incompletas por diseño (como la teoría elemental de grupos) y las teorías como la de la primaria a la teoría de números, donde podríamos desea tener una completa recursiva axiomatization.

Después de todo, la prueba por contradicción sólo utiliza el razonamiento básico. Supongamos que queremos demostrar que si $p$ es verdadera, entonces el $q$ debe de ser verdad. Examinamos las posibles consecuencias de $q$ ser falso. Si se demuestra que una de estas consecuencias es que el $p$ debe ser falsa, entonces sabemos que si $p$ es verdadera, entonces el $q$ es cierto. Las reglas formales de la lógica están diseñados para hacer ese tipo de razonamiento disponible en el formal nivel.

El Teorema de la Incompletitud es matemáticamente fascinante. Pero el Teorema también ha dado lugar a una gran cantidad de informales a la especulación, a menudo basados en lecturas erróneas del Teorema.

Answer 3

Creo que lo que estás diciendo es esto:

• La incompletitud de gödel muestra que hay declaraciones de $P$ tal manera que ninguno de $P$ ni $\neg P$ son demostrables a partir de ciertos conjuntos de axiomas.
• Por lo tanto, el hecho de saber que $\neg P$ no es comprobable, no es suficiente para concluir que $P$ es comprobable con un conjunto de axiomas.

Sin embargo, una prueba por contradicción no muestran que el $\neg P$ no es demostrable que muestra que el $\neg P$ es falso. Esto es más fuerte. Lo que hace la prueba por contradicción de trabajo es la ley del medio excluido o algo equivalente, y cuando se trabaja en un ambiente donde la ley del medio excluido es válida (como ordinario de la lógica de primer orden), una prueba por contradicción no es diferente de la ordinaria de la prueba.

Parece que la gente en general, obtener muy colgó en la distinción entre la verdad y la provability. Yo no soy un experto en lógica, pero mi entendimiento queda de la siguiente manera.

Para cualquiera de primer orden de teoría (conjunto de axiomas) $T$ existe una noción de un modelo de $T$, que se compone de una colección de conjuntos, funciones y relaciones de la satisfacción de los axiomas. Por ejemplo, los modelos de primer orden de la teoría de grupos. $T$ es coherente si se tiene un modelo. Una declaración de $P$ es verdadera si es verdad para todos los modelos, y false si no lo es falsa para todos los modelos; en otras palabras, la verdad es semántica. Una declaración de $P$ es comprobable si se puede deducir de los axiomas de $T$; en otras palabras, provability es sintáctica.

Gödel integridad teorema afirma que la verdad y la provability son equivalentes: una afirmación es verdadera en todos los modelos, si y sólo si es demostrable.

Teorema de la incompletitud de gödel, por otro lado, afirma que si $T$ satisface ciertas condiciones, existen afirmaciones que son verdaderas en algunos modelos (en especial en "el único y verdadero modelo" que nos importa, que en el caso de la aritmética es la ordinaria enteros positivos), pero no en otros. Por el teorema de completitud, esto es equivalente a decir que ni $P$ ni $\neg P$ puede ser demostrable.

Pero esto no es un extraño, fuera de propiedad, para $T$ tener. Por ejemplo, obviamente hay afirmaciones que son verdaderas para algunos grupos, pero no para otros, por ejemplo, " $G$ es abelian." No se puede probar esta declaración del grupo de axiomas porque no existen no abelian grupos, pero también no se puede demostrar su negación, porque no existen abelian grupos. Lo que el teorema de la incompletitud dice es que incluso las más sofisticadas teorías $T$ se comportan en este sentido, es como la teoría de grupos: hay un montón de modelos, y algunos de ellos se comportan de manera diferente de los demás. Por ejemplo, hay modelos de la aritmética de Peano , que se comportan de manera muy diferente de la habitual números naturales: pueden tener un número $n$ que satisface $1 < n, 1 + 1 < n, 1 + 1 + 1 < n, ...$.