Puede prueba por contradicción 'no'?

Question

Estoy familiarizado con el mecanismo de la prueba por contradicción: queremos demostrar a $P$, por lo que asumimos $¬P$ y demostrar que esto es falso; por lo tanto $P$ debe de ser verdad.

Tengo el siguiente abogado del diablo pregunta, que puede parecer más de la filosofía de las matemáticas, pero prefiero las respuestas de un matemático punto de vista de:

Cuando se demuestra que $¬P$ es "falso", lo que realmente estamos mostrando es que es incompatible con nuestra base de axiomas. Podría no ser nunca un caso fueron, para algunos $P$ y un conjunto de axiomas, $P$ $¬P$ son tanto incompatible con los axiomas (o ambos coherente, para el caso)?

Answer 1

La situación de preguntar acerca de, donde $P$ es inconsistente con nuestros axiomas y $\neg P$ es también incompatible con nuestros axiomas, significaría que los axiomas mismos son inconsistentes. Específicamente, la inconsistencia de las $P$ con los axiomas significaría que $\neg P$ es demostrable a partir de esos axiomas. Si, además, $\neg P$ es incompatible con los axiomas, entonces los axiomas mismos son incompatibles --- implican $\neg P$ y, a continuación, se contradicen. (He enunciado de esta respuesta, de modo que sigue siendo correcto, incluso si la lógica del sistema de axiomas es intuitionistic en lugar de los clásicos.)

Answer 2

Es posible que ambos $P$ $ \neg P $ a de ser coherente con un conjunto de axiomas. Si este es el caso, entonces la $P$ es llamado independiente. Hay un par de cosas que se saben para ser independientes, tales como la Hipótesis continua siendo independiente de ZFC.

También es posible que tanto $P$ $ \neg P $ incompatible con un conjunto de axiomas. En este caso, el son los axiomas que se consideran incompatibles. Incoherente axiomas resultado en sistemas que no funcionan en una manera que es útil para la participación en las matemáticas.

La prueba por contradicción depende de la ley del medio excluido. Constructivista de las matemáticas, que utiliza intuitionistic lógica, rechaza el uso de la ley del medio excluido, y esto se traduce en un tipo diferente de las matemáticas. Sin embargo, esto no protegerlos de los problemas derivados de la incoherente axiomas.

Hay sistemas lógicos llamados paraconsistent lógica que puede soportar inconsistente axiomas. Sin embargo, son más difíciles de trabajar que la lógica estándar y no son tan ampliamente estudiado.

Answer 3

Otras personas han mencionado la posibilidad de que $P$ $\neg P$ podría ser consistente con los axiomas, en cuyo caso $P$ es independiente de los axiomas, y no se puede derivar una contradicción a partir de cualquiera de asunción.

También podría agregar que en intuitionistic lógica, no solo es cierto que la prueba por contradicción podría fallar, es que no puede tener éxito. El problema descrito anteriormente es en realidad una limitación fundamental en la lógica matemática. Gödel del teorema de la incompletitud nos dice que cada conjunto de axiomas lo suficientemente potente como para definir la aritmética de los números naturales tienen este problema, por lo que cada definibles por el sistema de la lógica tendrá un número infinito de enunciados que no son ni verdaderos ni falsos dentro de ese sistema. Debido a esto, hay un problema en la misma premisa de la prueba por contradicción, que es la afirmación de que, "si no es falsa, entonces debe ser cierto!"

Intuitionistic lógica de abordar este problema por dar un paso atrás de la asunción de la lógica clásica que cada afirmación es verdadera o falsa, ya que parece ser manifiestamente mal! En su lugar hemos de decir que una declaración de $P$ es verdadera si y sólo si es una consecuencia lógica de nuestra axiomas y reglas de inferencia. La única manera de demostrar que un enunciado es verdadero es constructiva proporcionar evidencia de ello, porque eso es lo que significa la verdad! La mentira también tiene un significado diferente que en la lógica clásica. Decir que un enunciado es falso, $\neg P$, es equivalente a decir $P \rightarrow \bot$ donde $\bot$ (pronunciado "fondo") puede ser considerado como evidencia de que cada afirmación es verdadera. Por lo $\neg P$ es otra manera de decir que la evidencia de $P$ haría que el principio de explosión para poner en.

La prueba por contradicción obras afirmando $P \lor \neg P$, lo que podría traducirse, "o me puede proporcionar evidencia de $P$, o puedo demostrar que $P$ implica que todo lo que es verdadero". Cuando el enunciado de esta forma, la ley del medio excluido de repente parece la manera menos intuitiva. Además, se puede observar que en este punto de vista de la lógica de $\neg (\neg P)$ es no equivalente a $P$, pero una declaración de que $(P \rightarrow \bot) \rightarrow \bot$! Esto es importante, porque ahora puedo demostrar que $P \rightarrow \neg (\neg P)$, pero yo no puede demostrar que $\neg (\neg P) \rightarrow P$, que es el paso final en cada prueba por contradicción. $((P \rightarrow \bot) \rightarrow \bot) \rightarrow P$ simplemente no sigue, por lo tanto, consideramos válida y dicen que necesitamos más constructivo evidencia para apoyar la $P$.

En resumen, intuitionists son reales. Caminamos entre ustedes. Y nosotros estamos aquí para decirles que la prueba por contradicción siempre van a fallar. Saludos!