¿Reducción al absurdo o el contrapositivo?

Question

De vez en cuando, cuando escribo pruebas, empiezo con una afirmación y luego demuestro la contradicción. Sin embargo, cuando reviso la prueba después, parece que mi prueba era esencialmente una prueba del contrapositivo, y la afirmación inicial no era realmente importante en la prueba.

¿Pueden reformularse todas las afirmaciones demostradas por la reductio ad absurdum en pruebas del contrapositivo? Si no es así, ¿puede dar algunos ejemplos de pruebas que no se reducen? Si no se pueden reducir todas las pruebas de reductio, ¿hay alguna razón lógica para no hacerlo? ¿Es la reductio más fuerte o más débil que la contrapositiva?

Edición: Sólo otra pregunta menor (por supuesto, esto es opcional y no afectará a la elección de una respuesta): Si son equivalentes, entonces ¿por qué te molestas en usar la reductio?

Y otra pregunta extra (Como la anterior, no influye en la elección de la respuesta a aceptar). ¿Son las dos técnicas intuitivamente equivalentes?

Answer 1

Aunque las otras respuestas explican correctamente la equivalencia lógica básica de los dos métodos de prueba, creo que se ha pasado por alto un punto importante:

• Con razón Los matemáticos preferimos una prueba directa de una implicación a una prueba por contradicción, cuando dicha prueba está disponible. (en igualdad de condiciones)

¿Cuál es la razón? La razón es la fecundidad de la prueba, es decir, nuestra capacidad de utilizar la prueba para sacar más conclusiones matemáticas. Cuando demostramos una implicación (p implica q) directamente, asumimos p, y luego hacemos algunas conclusiones intermedias r ₁ , r ₂ antes de deducir finalmente q. Así, nuestra prueba no sólo establece que p implica q, sino también, que p implica r ₁ y r ₂ y así sucesivamente. Nuestra demostración nos ha proporcionado un conocimiento adicional sobre el contexto de p, sobre lo que debe suceder en cualquier mundo matemático en el que p sea válido. Así llegamos a una comprensión más completa de lo que ocurre en los mundos p.

Del mismo modo, cuando probamos el contrapositivo (¬q implica ¬p) directamente, asumimos ¬q, hacemos conclusiones intermedias r ₁ , r ₂ y finalmente concluir ¬p. Así, también hemos establecido no sólo que ¬q implica ¬p, sino también, que implica r ₁ y r ₂ y así sucesivamente. Así, la prueba nos dice qué más debe ser cierto en los mundos en los que q falla. De forma equivalente, puesto que estas implicaciones adicionales pueden enunciarse como (¬r ₁ implica q), nos enteramos de muchas hipótesis diferentes que todas implican q.

Este tipo de conclusiones puede aumentar el valor de la demostración, ya que no sólo aprendemos que (p implica q), sino que también aprendemos todo un contexto sobre cómo es una situación matemática en la que p se cumple (o en la que q falla, o sobre diversas situaciones que llevan a q).

Con la reductio, en cambio, una prueba de (p implica q) por contradicción parece llevar poco de este valor extra. Suponemos p y ¬q, y argumentamos r ₁ , r ₂ y así sucesivamente, antes de llegar a una contradicción. Los enunciados r ₁ y r ₂ se deducen todos bajo la hipótesis contradictoria de que p y ¬q, que finalmente no se cumple en ninguna situación matemática. La prueba ha proporcionado un conocimiento extra sobre un terreno inexistente y contradictorio. (¡Inútil!) Así que estas afirmaciones intermedias no parecen proporcionarnos ningún conocimiento mayor sobre los mundos p o los mundos q, más allá de la afirmación bruta de que (p implica q) por sí sola.

Creo que esta es la razón por la que a veces, cuando un matemático completa una prueba por contradicción, las cosas pueden seguir pareciendo inestables más allá de la implicación bruta, con menos contexto y conocimiento sobre lo que ocurre que en el caso de una prueba directa.

---

Edición: Para un ejemplo de una prueba en la que se nos hacen falsas expectativas en una prueba por contradicción, considere la prueba de Euclides de que hay infinitos primos. En una prueba común por contradicción, se asume que p ₁ , ..., p _n son todo los primos. Se deduce que como ninguno de ellos divide el producto-más-uno p ₁ ...p _n +1, que este producto más uno también es de primera. Esto contradice que la lista sea exhaustiva. Ahora bien, muchos principiantes esperan falsamente después de este argumento que siempre que p ₁ , ..., p _n son primos, entonces el producto-más-uno también es primo. Pero, por supuesto, esto no es cierto, y esto sería una instancia equivocada de intentar extraer mayor información de la prueba, equivocada porque esta es una prueba por contradicción, y esa conclusión se basó en la suposición de que p ₁ , ..., p _n fueron todo los primos. Sin embargo, si se organiza la prueba como un argumento directo que muestra que siempre que p ₁ , ..., p _n son primos, entonces hay otro primo que no está en la lista, entonces se llega a la verdadera conclusión, que p ₁ ...p _n +1 sólo tiene un divisor primo que no está en la lista original.

Answer 2

Estoy de acuerdo con la respuesta de Joel: las pruebas por contraposición son más satisfactorias que las pruebas por contradicción, ya que te dan más información más allá de saber que el resultado deseado es verdadero. Por ejemplo, en el análisis, las pruebas por contraposición tienden a ser de naturaleza finita y dan límites efectivos, mientras que las pruebas por contradicción (especialmente cuando se combinan con argumentos de compacidad) tienden a ser de naturaleza infinita y no dan fácilmente esos límites (a menos que uno convierta minuciosamente cada paso del argumento de contradicción infinita en un argumento contrapositivo finito). Discuto esto, por ejemplo, en

http://terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/

pero, por la misma razón, la prueba por contradicción es un método más poderoso en la práctica que las pruebas por contraposición, si su único objetivo es demostrar el resultado declarado; precisamente porque uno es menos ambicioso puede lograr su objetivo más fácilmente.

Hay una analogía con el problema computacional de intentar encontrar un camino en un laberinto desde A hasta B. El enfoque directo sería empezar desde A y explorar todas las direcciones razonables desde A hasta llegar a B. El análogo de la prueba por contraposición sería empezar hacia atrás desde B e intentar llegar a A; entonces al final uno simplemente invierte el camino. El análogo de la prueba por contradicción es una estrategia de encuentro en el medio: explorar tanto hacia adelante desde A como hacia atrás desde B hasta obtener una intersección. Se trata de una estrategia más rápida, con un tiempo de ejecución que suele ser la raíz cuadrada del tiempo de ejecución de los otros dos enfoques (debido a la paradoja del cumpleaños, básicamente, o a la ley de Metcalfe si se desea). Esta analogía está algo simplificada porque incluso en la estrategia de intersección no es difícil desentrañar la solución para crear un camino directo de A a B, pero con tareas de resolución de problemas más complicadas que los laberintos (por ejemplo, tratar de convertir varias hipótesis $A_1,\ldots,A_n$ en varias conclusiones $B_1,\ldots,B_m$ utilizando reglas deductivas como ``Si $A_3$ y $C_5$ son verdaderos, entonces $D_7$ es verdadero'', etc.) uno puede hacer que las soluciones de encuentro en el medio sean bastante difíciles de convertir de nuevo en un argumento directo.

Hay una clase de pruebas por contradicción que yo llamo argumentos "sin objeto autodestructivo", que son particularmente difíciles de convertir en pruebas por contraposición. Básicamente, estas pruebas tienden a mostrar que A es falso utilizando un argumento para establecer $A \implies B$ y otra para establecer $A \implies \neg B$ , dando lugar a la contradicción (A se derrota a sí mismo). Se puede convertir esto en una prueba por contraposición tomando la inspirada decisión de dividir en los dos casos $B$ y $\neg B$ y demostrar que cada uno de estos casos implica $\neg A$ tomando contraposiciones de cada lado del objeto no autodestructivo, pero en la práctica es difícil motivar esta elección de división en casos a menos que uno ya haya visto la versión de prueba por contradicción del argumento. Este es el caso, en particular, si A es un enunciado de existencia $\exists x: A(x)$ y B depende de x; entonces la dicotomía $B \vee \neg B$ ni siquiera puede introducirse sin introducir primero x. Discuto este tipo de argumento en mi blog en

http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/

Answer 3

Mi respuesta se aplica sólo a la lógica estándar.

En términos de lógica estándar, las pruebas por contraposición y por contradicción son "equivalentes" en el sentido de que ambas son lógicamente válidas, y dos proposiciones lógicamente válidas son equivalentes entre sí.

Por otro lado, es cierto que toda prueba por contraposición puede ser formulada como una prueba por contradicción. De hecho, dado que esta última es quizás un poco más intuitiva, a menudo se utiliza como justificación de la primera cuando se necesita, por ejemplo, en los cursos de cálculo:

Deseamos mostrar $A \implies B$ . Supongamos que sabemos que $\lnot B \implies \lnot A$ . Supongamos además que $B$ es falso. Entonces $\lnot B$ es verdadera, por lo que $\lnot A$ es verdadera, por lo que $A$ es falsa, en contra de nuestra suposición.

Supongamos que una proposición se puede demostrar por contraposición. Como en el caso anterior, existe una receta estándar para modificar la prueba y obtener una prueba por contradicción. Sin embargo, si se comparan las dos pruebas, se encuentra que la prueba por contradicción simplemente tiene el argumento de dos líneas anterior añadido, por lo que es ligeramente más larga sin ningún contenido adicional. Por esta razón, cuando es posible dar una prueba directa de $\lnot B \implies \lnot A$ es preferible hacerlo, en lugar de lanzarlo como una prueba por contradicción.

Sin embargo, la prueba por contradicción es una técnica más poderosa en el sentido informal de que algunas pruebas son más difíciles de enunciar utilizando la contraposición. (No quiero decir imposible, porque como arriba, ambas "técnicas" son simplemente argumentos lógicamente válidos, por lo que pueden insertarse en una prueba en cualquier momento).

¿Qué hace que la contradicción sea potencialmente más poderosa? (Esta es una pregunta a la que hay que enfrentarse cuando se imparten clases de introducción a las pruebas, como he hecho yo. Antes no habría tenido una respuesta tan preparada). Creo que es porque podemos asumir dos cosas en lugar de una. Es decir, en lugar de suponer sólo $\lnot B$ y usando esa suposición para trabajar nuestro camino hacia $\lnot A$ , tenemos que suponer que ambos $A$ y $\lnot B$ y hacerlas coincidir para derivar una contradicción.

He aquí un ejemplo de ello. Supongamos que queremos demostrar que $\sqrt{2}$ es irracional. En primer lugar, vamos a expresar esto como una implicación:

Para todos $x \in \mathbb{R}$ , $x^2 = 2 \implies x \not \in \mathbb{Q}$ .

O, a la inversa:

Para todos $x \in \mathbb{R}$ , $x \in \mathbb{Q} \implies x^2 \neq 2$ .

¡Tomar el contrapositivo no fue tan útil! Lo que hay que hacer es trabajar desde los dos extremos a la vez:

Supongamos que $x \in \mathbb{Q}$ y $x^2 = 2$ . Ahora estamos en el negocio; podemos trabajar con esto. (Omito la prueba ya que supongo que todo el mundo la conoce).

Aquí hay otra diferencia entre las dos pruebas, que no noté hasta que pensé en esta respuesta: el contrapositivo de la afirmación

$\forall x \in S, P(x) \implies Q(x)$

es

$\forall x \in S, \lnot Q(x) \implies \lnot P(x)$ :

Obsérvese que el cuantificador no ha cambiado. (Por supuesto, podríamos tener un cuantificador existencial en su lugar, y la discusión sería la misma. De todos modos, en la práctica, la mayoría de las proposiciones matemáticas comienzan con un cuantificador universal).

Sin embargo, el negación de la declaración es

$\exists x \in S \ | \ P(x) \wedge \ \lnot Q(x)$ .

Nótese que el cuantificador ha cambiado de $\forall$ a $\exists$ , que es una característica clave de la prueba anterior.

Por último, pregunta por qué preferiríamos una técnica sobre otra, ya que ambas son equivalentes. Pero, por supuesto, hacemos esto todo el tiempo, según la conveniencia y el gusto: por ejemplo, la inducción, la inducción fuerte y la ordenación son lógicamente equivalentes, pero utilizamos las tres. Podríamos, por ejemplo, plantear todas las pruebas de inducción como apelaciones al Principio de Ordenación, pero en muchos casos eso equivaldría a insertar una tediosa rigidez: "Considere el conjunto $S = \{ n \in \mathbb{N} \ | \ P(n)\ \text{is false} \}$ ...", lo que no aporta claridad ni concisión a la prueba.

Answer 4

En sentido estricto, el contrapositivo de una afirmación que no es una implicación no tiene sentido. Sin embargo, siempre se puede fingir la implicación, el contrapositivo de $\top \to A$ (o simplemente $A$ ) es $\lnot A \to \bot$ es decir, una "prueba por contradicción" es el contrapositivo de una "prueba (por tautología)".

---

Supongo que todavía puedo responder a las otras dos partes, que se añadieron más tarde.

En primer lugar, una prueba por contradicción es una herramienta más versátil que el contrapositivo. Es más eficaz cuando se trata de enunciados complejos, por ejemplo, cualquier cosa que no sea una implicación simple. Además, el contrapositivo no funciona muy bien cuando la hipótesis no es completamente necesaria o cuando hay hipótesis implícitas al acecho. Por (pseudo)ejemplo, supongamos $A$ y $B$ son declaraciones sobre widgets con la propiedad $C$ . Tiene pruebas de que $A \to B$ asumiendo que $A$ y $\lnot B$ y concluyendo que $\lnot A$ o el widget no tiene $C$ . Se podría concluir formalmente $\lnot A$ del fracaso de $C$ desde $C$ es una hipótesis implícita, pero eso no sería natural. Demostrando $\lnot B \to \lnot A$ directamente podría ser difícil ya que no está claro dónde está la hipótesis implícita $C$ debería entrar en juego. Por supuesto, todo esto se puede arreglar eliminando las hipótesis innecesarias y enunciando todas las hipótesis implícitas, pero esto sólo ocurre en los cuentos de hadas (también conocidos como ejercicios de libros de texto bien escritos). Consulta la respuesta de Pete (¡y vótala!) para ver ejemplos más concretos...

Finalmente, para responder a la última parte. La implicación

$(B \to A) \to (\lnot A \to \lnot B)$

es intuitivamente válido. De hecho, el lado derecho es una afirmación mucho más débil. Lo contrario

$(\lnot A \to \lnot B) \to (B \to A)$

da $\lnot\lnot A \to A$ al sustituir $\top$ para $B$ por lo que sólo es válida en la lógica clásica. Sin embargo,

$(B \to \lnot A) \leftrightarrow (A \to \lnot B)$

es intuitivamente válido, ambas partes dicen $\lnot(A \land B)$ . Así que siempre se puede tomar el contrapositivo de una implicación cuya conclusión es negativa. Esta es otra cara del viejo dicho "no se puede demostrar un negativo" o, más exactamente, demostrar un negativo es inherentemente no constructivo.

Answer 5

Son trivialmente equivalentes. El contrapositivo de (P → Q) es (¬Q → ¬P). Esto es equivalente a (¬Q → (P → ⊥)), que es una forma curiosa de (¬Q ∧ P) → ⊥.

Edición: No estoy seguro de tu comentario añadido. La reductio me parece la técnica de demostración más general (como menciona Anweshi, funciona para enunciados que no son implicaciones); la contraposición parece menos útil a menos que la forma contrapositiva ¬Q → ¬P sea especialmente natural o intuitiva.

Edición 2: Estas transformaciones parecen ser intuitivamente válidas, con la condición de que una "prueba por contradicción de (P → Q)" es sólo una prueba de (P → ¬¬Q). Por lo tanto, el contrapositivo (¬Q → ¬P) es estrictamente más débil que (P → Q).

Además, a menudo se da el caso de que el antecedente P puede verse naturalmente como una afirmación negativa (¬P'). En estos casos, podemos proporcionar una prueba de (¬Q → P'). Este puede ser el caso de una prueba por contrapositiva que es una "prueba directa", lo que posiblemente explica las observaciones de J. Polak.

Edición 4: JD Hamkins señala que las pruebas directas suelen proporcionar pruebas útiles de los enunciados intermedios, mientras que las pruebas por contradicción no lo hacen. Pero esta técnica puede generalizarse empujando los "contextos" contradictorios hasta el final de la prueba: es decir, uno puede decir: "Demostraremos una contradicción suponiendo P, Q, R y S. A partir de P, R y S obtenemos los siguientes lemas..." No está claro que todas las pruebas de este tipo puedan enunciarse naturalmente como pruebas por contraposición.