¿Son realmente lógicas las pruebas por contradicción?

Question

Digamos que pruebo la afirmación $A$ demostrando que la negación de $A$ lleva a una contradicción.

Mi pregunta es la siguiente: ¿Cómo se pasa de "entonces hay una contradicción si no tenemos $A$ " para concluir que "tenemos $A$ "?

Eso, para mí, parece todo lo contrario a la lógica. Suena como si dijéramos "entonces, voy a tener un problema muy grande si esto no es cierto, así que por conveniencia, voy a actuar como si fuera cierto".

Answer 1

La prueba por contradicción, como has dicho, es la regla $\def\imp{\Rightarrow}$ " $\neg A \imp \bot \vdash A$ " para cualquier declaración $A$ que en inglés es "If you can derive the statement that $\neg A$ implica una contradicción, entonces se puede derivar $A$ ". Como han señalado otros, ésta no es una regla válida en la lógica intuicionista. Pero ahora le mostraré por qué probablemente no tenga más remedio que estar de acuerdo con la regla (bajo ciertas condiciones suaves).

Verás, dada cualquier declaración $A$ la ley del medio excluido dice que " $A \lor \neg A$ " es verdadero, que en inglés es "Either $A$ o $\neg A$ ". Ahora bien, ¿hay alguna razón para que esta ley se mantenga? Si se desea que todo lo que se pueda derivar venga acompañado de algún tipo de evidencia directa (como las diversas lógicas constructivas), entonces podría no sostenerse, porque a veces no tenemos ni evidencia a favor ni en contra de una afirmación. Sin embargo, si crees que los enunciados que puedes hacer tienen significado en el mundo real, entonces la ley obviamente se mantiene porque el mundo real o bien satisface un enunciado o su negación, independientemente de que puedas averiguar cuál.

El mismo razonamiento muestra también que una contradicción nunca puede ser verdadera, porque el mundo real nunca satisface al mismo tiempo una afirmación y su negación, simplemente por el significado de la negación. Esto da lugar al principio de explosión, al que me referiré más adelante.

Ahora, dada la ley del medio excluido, considere el siguiente razonamiento. Si a partir de $\neg A$ Puedo derivar una contradicción, entonces $\neg A$ debe ser imposible, ya que mis otras reglas son preservadoras de la verdad (partiendo de enunciados verdaderos derivan sólo enunciados verdaderos). Aquí hemos utilizado la propiedad de que una contradicción nunca puede ser verdadera. Como $\neg A$ es imposible, y por la ley del medio excluido sabemos que o bien $A$ o $\neg A$ debe ser cierto, no tenemos otra opción que concluir que $A$ debe ser cierto.

Esto explica por qué la prueba por contradicción es válida, siempre que se acepte que para cada afirmación $A$ exactamente uno de " $A$ " y " $\neg A$ " es cierto. El hecho de que utilicemos la lógica para razonar sobre el mundo en que vivimos es precisamente la razón por la que casi todos los lógicos aceptan la lógica clásica. Por eso dije "condiciones leves" en mi primer párrafo.

Volviendo al principio de la explosión, que es la regla " $\bot \vdash A$ " para cualquier declaración $A$ . A primera vista, esto puede parecer incluso más poco intuitivo que la regla de la prueba por contradicción. Pero, por el contrario, la gente la utiliza sin darse cuenta. Por ejemplo, si no crees que pueda levitar, podrías decir "Si puedes levitar, me comeré el sombrero". ¿Por qué? Porque saben que si la condición es falsa, entonces si la conclusión es verdadera o falsa es completamente irrelevante. Están asumiendo implícitamente la regla de que " $\bot \imp A$ " es siempre verdadera, lo que equivale al principio de explosión.

Por lo tanto, podemos mostrar mediante una deducción formal que la ley del medio excluido y el principio de explosión dan conjuntamente la capacidad de hacer pruebas por contradicción:

[Supongamos que desde " $\neg A$ " se puede derivar "Contradicción"].

  $A \lor \neg A$ . [ley del medio excluido]

  Si $A$ :

    $A$ .

  Si $\neg A$ :

    Contradicción.

    Así, $A$ . [principio de explosión]

  Por lo tanto, $A$ . [eliminación de la disyunción]

Otra forma posible de obtener la regla de la prueba por contradicción es si se acepta la eliminación de la doble negación, es decir " $\neg \neg A \vdash A$ " para cualquier declaración $A$ . Esto puede justificarse exactamente con el mismo razonamiento que antes, porque si " $A$ " es verdadero entonces " $\neg A$ " es falso y, por tanto, " $\neg \neg A$ " es verdadero, y de forma similar si " $A$ " es falso, así como " $\neg \neg A$ ". A continuación se presenta una deducción formal que muestra que la eliminación de la contradicción y la eliminación de la doble negación juntas dan la capacidad de hacer pruebas por contradicción:

[Supongamos que desde " $\neg A$ " se puede derivar "Contradicción"].

  Si $\neg A$ :

    Contradicción.

  Por lo tanto, $\neg \neg A$ . [eliminación de la contradicción / introducción de la negación]

  Así, $A$ . [eliminación de la doble negación]

Answer 2

Una contradicción no es un "problema". Una contradicción es una imposibilidad. No se trata de decir "Caramba, si tengo menos de 20 dólares en la espalda no podré salir a cenar y tengo tantas ganas de hacerlo que supondré que tengo más de 20 dólares". Se trata de entrar en el banco y decir "Me gustaría sacar 20 dólares" y que se derrumbe una trampilla debajo de ti y que un guardia de seguridad de 300 libras salte sobre tu bazo gritándote al oído "Tú no tienen ¡No lo tienes!"

No puedes decir "Oh, tengo una contradicción cuando supuse que tenía 20 dólares... Pero eso no significa que no tenga 20 dólares".

Significa precisamente que. Es imposible para que tengas 20. Así que debes concluir que no tienen 20 dólares.

Si obtienes una contradicción, simplemente no es posible que A sea falso.

Una contradicción, por definición, es una imposibilidad. Así que si asumes que A no es cierto y obtienes una contradicción. Tienes probado que es imposible para que A no sea cierto. Si lo es imposible para que algo no sea cierto ¿qué otras opciones hay?

Answer 3

NOTA PARA LOS INTUICIONISTAS : Lee la pregunta del OP: si crees que el OP o cualquier otro lector de ese nivel se beneficiará de lo que para ellos serán distinciones incomprensibles, por supuesto añade a los comentarios de esta respuesta.

Supongo que estás familiarizado y te sientes cómodo con las pruebas que no utilizan la prueba por contradicción. La receta para estas pruebas es:

• Comienza con algunas afirmaciones (suposiciones) $X,Y,Z$ que tomamos como verdad.
• (También se empieza con un puñado de no se ha dicho afirmaciones que damos por ciertas, como las leyes aritméticas o los teoremas previamente demostrados).
• Utilizar las reglas de la lógica que consideramos sonido Estas reglas toman enunciados verdaderos y nos permiten deducir nuevos enunciados verdaderos.
• Combínalos para obtener una nueva declaración, $A$ . Dado que partimos de enunciados verdaderos, y utilizamos reglas que hacen nuevos enunciados verdaderos a partir de enunciados verdaderos anteriores, concluimos $A$ es cierto.

La receta para una prueba por contradicción de la lógica clásica es:

• Comienza con algunas afirmaciones (suposiciones) $X,Y,Z$ que tomamos como verdad.
• (También se empieza con un puñado de no se ha dicho afirmaciones que damos por ciertas, como las leyes aritméticas o los teoremas previamente demostrados).
• Utilizar las reglas de la lógica que consideramos sonido Estas reglas toman enunciados verdaderos y nos permiten deducir nuevos enunciados verdaderos.
• Asumir la declaración $P$ es cierto.
• Combínalos para obtener una nueva afirmación que sabemos que es falsa. Si no había incluye $P$ cualquier deducción de nuestras verdaderas declaraciones $X,Y,Z$ sería cierto. Nosotros hizo incluye $P$ y dedujo una afirmación falsa, por lo que concluimos $P$ es falso. Editar : Más concretamente, concluimos que $P$ es falso en el contexto de $X,Y,Z$ siendo todo cierto, o $X \wedge Y \wedge Z$ implica $P$ es falso.

Lo anterior probablemente no le hará cómodo con la prueba por contradicción (que requiere tiempo y reflexión; véase la nota más abajo), pero al menos debería mostrarte que el proceso no se limita a suponer algo que queremos suponer.

Nota: He pasado muchas noches durmiendo preocupado por la irracionalidad de $\sqrt2$ porque la única prueba que conocía -usando la contradicción- ¡parecía tan rara!

Answer 4

La solución viene de la definición de afirmación: puede que no lo hayas pensado, pero es, por definición, algo que debe ser verdadero o falso. Como se obtiene una contradicción suponiendo $A$ es falso, debe ser necesariamente verdadero. Puede haber algunas cosas que no sean afirmaciones en la vida real, pero en matemáticas solemos ocuparnos sólo de ellas.

Answer 5

Encontré la obra de Bourbaki " Teoría de los conjuntos " útil para profundizar en mi comprensión del concepto de prueba cuando era estudiante. En él introduce un lenguaje formal particular y procede a definir rigurosamente el concepto de prueba. En particular, introduce los símbolos lógicos $\vee$ y $\lnot$ . Define $A \implies B$ para ser $\lnot A \vee B$ e introduce algunos axiomas como $A \vee B \implies B \vee A, A \implies A \vee B, A \vee A \implies A$ y lo más importante, $$\lnot\lnot A \Longleftrightarrow A$$ Este es el axioma clave para la prueba por contradicción. (Esto no contradice las afirmaciones del usuario21820 sobre la ley del medio excluido, sino que lo aborda desde una dirección diferente).

A prueba según Bourbaki, es una lista de enunciados tal que cada enunciado de la lista es

• Una aplicación directa de un axioma (es decir, el axioma con variables sustituidas por expresiones específicas), o
• Una declaración $B$ que ha sido precedida en la prueba por otras dos afirmaciones $A$ y $A \implies B$ .

A teorema es cualquier afirmación que aparece en una prueba. Tras introducir este concepto, desarrolla varias técnicas de demostración comunes, que en su lenguaje no son pruebas reales, sino argumentos metamatemáticos de que las pruebas reales existen. Entre ellas se encuentran

• Permitir "pruebas" que contengan aplicaciones de teoremas previamente demostrados, en lugar de empezar sólo con los axiomas. Esto indica que existe una prueba real, ya que se puede simplemente preceder la prueba abreviada con las pruebas de cada teorema utilizado en ella para crear una prueba completa.
• prueba por hipótesis añadida: Se crea una nueva teoría matemática añadiendo un axioma adicional $A$ a los axiomas normales. Cualquier prueba en la teoría aumentada puede convertirse en una prueba en la teoría original añadiendo cualquier declaración que dependa de $A$ con " $A \implies$ ".
• prueba por contradicción: Para demostrar $A$ Como en la prueba por hipótesis añadida, se forma una nueva teoría añadiendo un nuevo axioma. En este caso, $\lnot A$ . En esta teoría aumentada se produce entonces una contradicción. Bourbaki ya había demostrado en este punto que se pueden demostrar todas las afirmaciones a partir de una contradicción. En particular, se puede demostrar $A$ en la teoría aumentada. Al igual que con la prueba por hipótesis añadida, esto significa que se puede demostrar $\lnot A \implies A$ en la teoría original. Pero $\lnot A \implies A$ es por definición $(\lnot \lnot A) \vee A$ lo que equivale a $A \vee A$ que a su vez implica $A$ .

Así que en una teoría donde las leyes básicas de la lógica se mantienen, si $\lnot\lnot A \Longleftrightarrow A$ también es válida, cualquier prueba por contradicción puede traducirse en una prueba normal.

Por supuesto, éste es sólo un ejemplo de cómo desarrollar una teoría de la prueba, y otros pueden preferir enfoques diferentes. Pero para mí sigue siendo la demostración más clara que he encontrado.