En una prueba por la contradicción, ¿cómo sabemos que la asunción es la causa de la contradicción?

Question

En una prueba por contradicción, ¿cómo sabemos que la suposición es la causa de la contradicción? Y no sólo el resultado de alguna otra propiedad más fundamental para los números?

En otras palabras, ¿cómo podemos estar seguros de que llegamos a la contradicción, porque de la proposición $P$ que hemos asumido, y no a causa de alguna otra proposición $Q$ ni siquiera somos conscientes de?

---

La respuesta que viene en mente es "Bueno, si hay algunos proposición $Q$ causando la contradicción, entonces debería también se manifiestan en el caso de $ \neg P$."

Es este sencillo o hay más? ¿Qué pasa si la proposición $Q$ sólo puede manifestarse en el caso de $P$, y no en todos, en el caso de $\neg P$?

Lo siento si esto es una tontería - tratando de despejar algunas confusiones.

Answer 1

En matemáticas, podemos deducir teoremas a partir de axiomas, así que se termina sabiendo que los teoremas son verdaderos en cualquier situación en la que los axiomas son verdaderos. No obtenemos información acerca de situaciones en las que algunos de los axiomas son falsas.

Ahora supongamos que demostrar un teorema de T por la contradicción; asumimos no-T y, por medio de esta suposición más nuestros axiomas, llegamos a una contradicción. Entonces sabemos que no-T es falsa o (al menos) uno de nuestros axiomas es falso. Que el conocimiento es exactamente el mismo que saber que si los axiomas son verdaderos, entonces no-T debe ser falsa y, por tanto, T debe ser cierto. Si, por otro lado, algunos de los axiomas son falsas, entonces tenemos ninguna información.

Por lo que la información que obtenemos de la prueba por contradicción es el mismo que lo que conseguiría de una prueba directa: mientras que los axiomas son verdaderas, sabemos que T; si algunos axiomas son falsas, todas las apuestas están apagadas.

Answer 2

Este post se explica la justificación intuitiva de que la técnica de la prueba por contradicción es válido. Por lo tanto creo que se ocupa de un aspecto de su pregunta. Pero me gustaría señalar un aspecto adicional que se asemeja a su pregunta. Supongamos que tenemos la siguiente estructura de prueba:

Si $P$:

Si $Q$:

...

Contradicción. [Supongamos que podemos deducir esto. Es un 'debido a' $Q$ o $P$?]

$\neg Q$. [Esta es una válida la deducción? Voy a explicar a continuación por qué es!]

Es válido para deducir $\neg Q$ bajo el exterior de la asunción de $P$, como se muestra arriba. Por qué? Como se explica en el post vinculado, todas nuestras reglas deductivas están diseñados para ser verdad-la preservación, es decir, que cada frase se puede deducir que es verdadero en su contexto (incluyendo los supuestos es bajo). Por lo tanto, no podemos deducir una contradicción, excepto en un imposible contexto. Ahora en la anterior estructura de prueba debe ser que es imposible para los $P$ $Q$ para ser cierto, pero a partir de la estructura dada, no podemos determinar que no es verdad. Esto es exactamente igual que lo que están pidiendo en tu pregunta! Sin embargo, la última deducción anterior es válida debido a que bajo la suposición de que $P$ es cierto, es imposible para $Q$ a ser cierto y, por tanto, $Q$ debe ser falsa.

Podría muy bien ser que $Q$ es realmente cierto, pero $P$ es el falso tonterías que permite deducir una contradicción bajo los supuestos de ambos $P$$Q$. A pesar de que, lo que hemos dicho más arriba es correcta! Por qué? Bueno, si $P$ es falso, entonces lo que podemos deducir bajo la suposición de que $P$ es cierto es irrelevante, porque no estamos deducir una frase que es falsa bajo ninguna hipótesis.

Para los programadores, usted puede pensar de cada frase como un assert declaración, y cada "Si" contexto de encabezado como un if-construir. El hecho de que nuestras reglas deductivas son verdad-la preservación implica que cada prueba escribimos siguiendo nuestras reglas deductivas es uno que no hace ninguna afirmación de error. Por lo tanto, si logramos demostrar una contradicción en algún lugar, esto implica que cuando se ejecute la prueba como un programa que va a nunca llegar a ese assert declaración! Así que echemos un vistazo a la estructura a prueba de nuevo. La única manera de llegar a la última declaración es si $P$ es verdadero, en cuyo caso $Q$ debe ser falso, ya que no podemos llegar a la "Contradicción" afirmación. Así que cuando llegamos a $\neg Q$ estamos de hecho correcto afirmarlo. La otra situación posible es que $P$ es falso, en cuyo caso nunca nos ejecutar todas las instrucciones debajo de ella, por lo que no importa que nos han hecho algunas afirmaciones debajo de ella!

Por último, quiero señalar que no es siempre el caso de que sólo una de nuestras premisas es la 'causa' cuando podemos deducir una contradicción. Considere la siguiente prueba válida de la estructura:

Si $P$:

Si $\neg P$:

Contradicción. [Que 'causado' esto?]

$\neg \neg P$.

Answer 3

Una prueba por contradicción se basa en el hecho de que (a$P$ e no$Q$) es la negación de ($P$ implica $Q$). La ley del medio excluido, junto con la ley de noncontradiction, da exactamente una de estas dos afirmaciones es verdadera, por lo que si ($P$ e no$Q$) conduce a una contradicción que debe ser una declaración falsa, y por lo tanto ($P$ implica $Q$) es verdadera. Tenga en cuenta que si usted obtiene una contradicción que no esté relacionado con su asunción de ($P$ e no$Q$) han demostrado que el universo se está trabajando en es inherentemente contradictorios, por lo general nos gusta pensar que ese no es el caso.

Me gustaría mencionar que la idea de que la "ley del medio excluido" es controversial es... tal vez excesivamente en algunas partes de la internet en comparación con las opiniones que se encontraría entre los matemáticos. Yo le reto a que lo intente, en su propia, vienen con una afirmación matemática tal que ni la declaración ni su negación es verdadera (o, cuando ambas son verdaderas). No voy a aguantar la respiración.

Answer 4

En otras palabras, ¿cómo podemos estar seguros de que llegamos a la contradicción, porque de la proposición $P$ que hemos asumido, y no a causa de alguna otra proposición $Q$ ni siquiera somos conscientes de?

Vamos a considerar las posibilidades de $Q.$ Voy a suponer que la Ley del Medio Excluido, porque no sé lo suficiente acerca de la lógica de los sistemas sin ella para decir si la prueba por contradicción obras en cualquiera de ellos.

También asumo que la prueba se establece en algunos axiomática del sistema de $A,$ ya no sé cómo hacer pruebas fuera de cualquier sistema axiomático.

Así que, o bien tienen que $Q$ siempre es verdadera en virtud de $A,$ o $Q$ no es siempre cierto en $A.$

Caso 1

Si $Q$ siempre es verdadera en virtud de $A,$ $Q$ conduce a una contradicción, a continuación, $A$ es un sistema inconsistente. Realmente no es adecuado para cualquier tipo de prueba, incluyendo la prueba por contradicción.

Caso 2

Si $Q$ no es siempre cierto en $A,$ entonces $Q$ es ocasionado por los axiomas $A$ junto con la suposición de $P$ (pero no por $A$ o $Q$ no se supone que los axiomas $A$ junto con la suposición de $P.$ Vamos a dividir este caso en dos sub-casos.

El caso 2a

Si $Q$ es no implicaba por los axiomas $A$ junto con la suposición de $P,$ a continuación, $Q$ representa un injustificado de la suposición de que hemos hecho. Esto hace que la prueba no válida incluso si su conclusión es verdadera. Nuestra falibilidad humana hace posible que las cosas sucedan. Es posible introducir una hipótesis a una prueba directa así, lo que es igualmente válido.

Caso 2b

Si $Q$ es ocasionado por los axiomas $A$ junto con la suposición de $P$ pero no por $A$ solo, a continuación,$P$, de hecho es necesario para llegar a la contradicción, y el teorema es demostrable. Pero si $Q$ realmente es instrumental en la fabricación de algunos de los pasos en el prueba, y no éramos conscientes de este hecho, entonces creo que de nuevo tenemos una prueba no válida de una conclusión verdadera. De nuevo, este es un posible resultado de la falibilidad humana que también puede suceder en directo de las pruebas.

Conclusión

Tomando todos los casos juntos, realmente hay sólo dos maneras para que una prueba por contradicción a ir mal. Uno de ellos es si estamos trabajando con un incoherente conjunto de axiomas, que es una muy mala noticia por completo. La otra es que si tenemos a un paso injustificado en algún lugar de la prueba.

Un ejemplo de un "paso injustificado" se produjo la famosa frase de Andrew Wiles del primer anuncio que había demostrado Último Teorema de Fermat. Alguien (en realidad, creo que varias personas) se encontró un error en la prueba se presentan. Después de que él hizo un considerable esfuerzo adicional, que finalmente fue capaz de presentar una prueba sin ese error, y esta prueba fue aceptada.

---

Algunos comentarios en la pregunta original se planteó la cuestión de cómo revisamos los pasos intermedios de una prueba por contradicción, afirman que es más fácil comprobar los pasos de una prueba directa ya que sus conclusiones son todas verdaderas.

Las cosas que queremos probar suelen tener la forma $S\implies T,$ para que una prueba directa implica típicamente asumiendo $S$ y, a continuación, mostrando que $T$ sigue. En los pasos intermedios de la prueba, tenemos algunos hechos que dependen $S,$ que no podemos "verificación" por la simple observación de que son verdaderas; nos puede comprobar mediante la verificación de la lógica en cada paso que conduce a la parte de la prueba, o nos puede comprobar por dar con una alternativa de prueba que demuestre que son consecuencia de $S.$

También podemos introducir algunos hechos conocidos (que no dependen de $S$) en el transcurso de la prueba, que nos puede comprobar simplemente comprobando que son verdad de los hechos.

Una tercera posibilidad es la que se deriva algo de $S$ que podríamos haber conocido a ser verdad sin asumiendo $S.$ Esto es un desperdicio; podríamos mejorar la prueba por la simple introducción de estos hechos ya conocidos, sin mostrar una lógica derivación de $S.$

Pasan las mismas cosas que en la prueba por contradicción. Vamos a tener algunos pasos que podemos comprobar sólo por la comprobación de que cada paso en la lógica que conduce a ellos o mediante la elaboración de una alternativa de la prueba, nos han conocido hechos que podemos comprobar más fácilmente, y que incluso puede tener el desperdicio de esfuerzo por derivar algo de nuestra (falso) suposición de que podemos tener simplemente como un hecho conocido.

Answer 5

No es que por $P\Rightarrow \bot$ (el símbolo $\bot$ denota una contradicción) asumimos $\neg P$ sólo porque parece que hay algo "malo" con $P$. Es más, que no podemos evitar de todos modos.

La contradicción surge de $P$ y sería razonable suponer $\neg P$, o la contradicción queda al retirar $P$, pero luego de los ya existentes inconsistente sistema de axiomas es suficiente para demostrar $\neg P$ (así como de $P$) utilizando el principio de la explosión. Así es que en cualquier forma, añadiendo $\neg P$ es razonable $-$ o al menos no más incoherente como el axioma el sistema en sí.