Reductio ad absurdum o la contrapositiva?

Question

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

¿Se pueden reformular todas las afirmaciones probadas por reducción al absurdo como pruebas de la contrapositiva? Si no, ¿puedes dar algunos ejemplos de pruebas que no se reduzcan? Si no todas las pruebas de reducción se pueden reducir, ¿hay alguna razón lógica por la que no? ¿Es la reducción más fuerte o más débil que la contrapositiva?

Edición: Solo otra pregunta menor (por supuesto, esto es opcional y no afectará mi elección de respuesta): ¿Si son equivalentes, por qué te molestarías en usar la reducción al absurdo?

Y otra pregunta adicional (Al igual que la anterior, no influye en cómo elijo la respuesta para aceptar.) ¿Son equivalentes desde un punto de vista intuicionista las dos técnicas?

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 buena razón, nosotros, los matemáticos, preferimos una prueba directa de una implicación sobre una prueba por contradicción, cuando tal prueba está disponible. (todo lo demás siendo igual)

¿Cuál es la razón? La razón es la fecundidad de la prueba, es decir, nuestra capacidad para usar la prueba para hacer conclusiones matemáticas adicionales. Cuando probamos una implicación (p implica q) directamente, asumimos p, y luego hacemos algunas conclusiones intermedias r₁, r₂, antes de finalmente deducir q. Así, nuestra prueba no solo establece que p implica q, sino también que p implica r₁ y r₂ y así sucesivamente. Nuestra prueba nos ha proporcionado conocimiento adicional sobre el contexto de p, sobre qué más debe ser cierto en cualquier mundo matemático donde p sea cierto. Así que llegamos a una comprensión más completa de lo que está sucediendo en los mundos de p.

De manera similar, cuando demostramos la contrapositiva (¬q implica ¬p) directamente, asumimos ¬q, hacemos conclusiones intermedias r₁, r₂, y luego concluimos finalmente que ¬p. Así, también hemos establecido no solo que ¬q implica ¬p, sino también que implica r₁ y r₂ y así sucesivamente. Por lo tanto, la prueba nos dice qué más debe ser cierto en los mundos donde q falla. Equivalentemente, ya que estas implicaciones adicionales se pueden expresar como (¬r₁ implica q), aprendemos sobre muchas hipótesis diferentes que implican q.

Este tipo de conclusiones puede aumentar el valor de la prueba, ya que no solo aprendemos que (p implica q), sino que también aprendemos todo un contexto sobre cómo es una situación matemática donde p es cierto (o donde q falla, o sobre diversas situaciones que conducen a q).

Con la reducción al absurdo, en contraste, una prueba de (p implica q) por contradicción parece llevar poco de este valor extra. Asumimos p y ¬q, y argumentamos r₁, r₂, y así sucesivamente, antes de llegar a una contradicción. Las afirmaciones r₁ y r₂ se deducen todas bajo la hipótesis contradicente de que p y ¬q, lo cual en última instancia no se cumple en ninguna situación matemática. La prueba ha proporcionado conocimiento adicional sobre una tierra inexistente y contradictoria. (¡Inútil!) Por lo tanto, estas afirmaciones intermedias no parecen proporcionarnos un mayor conocimiento sobre los mundos de p o los mundos de q, más allá de la simple afirmación de que (p implica q) solo.

Creo que esta es la razón por la que a veces, cuando un matemático completa una prueba por contradicción, las cosas todavía pueden parecer no resueltas más allá de la simple implicación, con menos contexto y conocimiento sobre lo que está sucediendo de lo que sería el caso con una prueba directa.

---

Edición: Para un ejemplo de una prueba donde se nos lleva a falsas expectativas en una prueba por contradicción, consideremos la prueba de Euclides de que hay infinitos números primos. En una prueba común por contradicción, se asume que p₁, ..., p_n son todos los números primos. Se deduce que dado que ninguno de ellos divide al producto más uno p₁...p_n+1, este producto más uno también es primo. Esto contradice que la lista fuera exhaustiva. Ahora, muchos principiantes esperan falsamente después de este argumento que siempre que p₁, ..., p_n sean primos, entonces el producto más uno también es primo. Pero por supuesto, esto no es cierto, y esto sería una instancia errónea de intentar extraer mayor información de la prueba, errónea porque esta es una prueba por contradicción, y esa conclusión se basó en la suposición de que p₁, ..., p_n eran todos los primos. Si uno organiza la prueba, sin embargo, como un argumento directo que muestra que siempre que p₁, ..., p_n son primos, entonces hay otro primo que no está en la lista original, entonces se llega a la verdadera conclusión, que p₁...p_n+1 tiene simplemente un divisor primo que no está en la lista original.

Answer 2

Estictamente hablando, la contrapositiva de una afirmación que no es una implicación no tiene sentido. Sin embargo, siempre puedes simular la implicación, la contrapositiva de $\top \to A$ (o solo $A$) es $\lnot A \to \bot$, es decir, una "demostración por contradicción" es la contrapositiva de una "demostración (de la tautología)".

---

Supoongo que aún puedo responder las otras dos partes, que se añadieron más tarde.

Primero, una demostración por contradicción es una herramienta más versátil que la contrapositiva. Es más eficiente al tratar con afirmaciones complejas, por ejemplo, cualquier cosa que no sea una simple implicación. Además, la contrapositiva no funciona muy bien cuando la hipótesis no es completamente necesaria o cuando hay hipótesis implícitas rondando. Por (pseudo-)ejemplo, supongamos que $A$ y $B$ son afirmaciones sobre widgets con la propiedad $C$. Tienes una demostración de $A \to B$ asumiendo que $A$ y $\lnot B$ y concluyendo que o bien $\lnot A$ o el widget no tiene $C$. Podrías concluir formalmente $\lnot A$ a partir del fracaso de $C$ ya que $C$ es una hipótesis implícita, pero eso sería antinatural. Demostrar directamente $\lnot B \to \lnot A$ podría ser difícil ya que no está claro dónde debería entrar en juego la hipótesis implícita $C$. Por supuesto, todo esto se puede solucionar eliminando hipótesis innecesarias y enunciando todas las hipótesis implícitas, pero esto solo sucede en cuentos de hadas (también conocidos como ejercicios de texto bien escritos). Consulta la respuesta de Pete (¡y vota a favor!) para obtener ejemplos más concretos...

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

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

es válida desde un punto de vista intuitivo. De hecho, el lado derecho es una afirmación mucho más débil. La conversa

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

da $\lnot\lnot A \to A$ al sustituir $\top$ por $B$, por lo que solo se cumple en la lógica clásica. Sin embargo,

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

es válida desde un punto de vista intuitivo, ambos lados dicen $\lnot(A \land B)$. Así que siempre puedes tomar la contrapositiva de una implicación cuya conclusión es negativa. Esta es otra cara del antiguo dicho "no puedes probar una negativa" o, más precisamente, probar una negativa es inherentemente no constructivo.

Answer 3

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

En términos de la lógica estándar, pruebas por contrapositivo y por la contradicción son "equivalentes" en que ambos son lógicamente válidos, y dos, lógicamente válido proposiciones son equivalentes entre sí.

Por otro lado, es cierto que cada prueba por contrapositivo puede ser formulada como una prueba por contradicción. En efecto, puesto que el último es tal vez un poco más intuitivo, se utiliza a menudo como una justificación de la ex cuando es necesario, por ejemplo, en el cálculo de los cursos de:

Queremos mostrar $A \implica B$. Supongamos que sabemos que $\lnot B \implica \lnot$. Supongamos, además, que $B$ es falso. Entonces $\lnot B$ es verdad, entonces $\lnot$ es cierto, por lo que $A$ es falso, contrario a nuestra hipótesis.

Supongamos que una proposición puede ser demostrado por contraposición. Como en el anterior, existe una receta estándar para la modificación de la prueba para dar una prueba por contradicción. Sin embargo, si comparamos las dos pruebas que usted encuentre que la contradicción sólo tiene dos anteriores argumento de la línea de anexados, por lo que es sólo ligeramente más largo sin ningún contenido adicional. Por esta razón, cuando es posible dar una prueba directa de $\lnot B \implica \lnot$ es preferible hacerlo, en lugar de colada como una prueba por contradicción.

Sin embargo, la prueba por contradicción es una técnica más potente en el sentido informal que algunas pruebas son más difíciles de frase utilizando contraposición. (No quiero decir imposible, ya que como anteriormente, tanto el de "técnicas" son simplemente lógicamente argumentos válidos, por lo que puede ser insertado en una prueba en cualquier momento.)

Lo que hace que la contradicción potencialmente más poderosa? (Esta es una pregunta que te tienes que enfrentar cuando se enseña introducción a las pruebas de las clases, como yo. Yo no habría tenido como preparado una respuesta antes.) Creo que es porque podemos asumir dos cosas en lugar de uno. Es decir, en lugar de simplemente suponiendo que $\lnot B$ y el uso que una suposición de que nuestra forma de trabajo a $\lnot$, tenemos que asumir tanto $A$ y $\lnot B$ y jugar con ellos a la salida de uno a otro con el fin de derivar una contradicción.

Aquí está un ejemplo de esto. Supongamos que queremos demostrar que $\sqrt{2}$ es irracional. En primer lugar, vamos a decirlo, como una consecuencia:

Para todo $x \in \mathbb{R}$, $x^2 = 2 \implica x \no \in \mathbb{Q}$.

O, contrapositively:

Para todo $x \in \mathbb{R}$, $x \in \mathbb{Q} \implica x^2 \neq 2$.

Tomando el contrapositivo no era tan útil! Lo que tenemos que hacer es un trabajo de ambos extremos a la vez:

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

Aquí hay otra diferencia entre las dos pruebas, que yo no me di cuenta hasta que se me ocurrió esta respuesta: el contrapositivo de la declaración de

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

es

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

tenga en cuenta que el cuantificador no ha cambiado. (Por supuesto que podría tener un cuantificador existencial en su lugar, y el debate iba a ser el mismo. De todos modos, en la práctica, la mayoría de los matemáticos proposiciones empiezan con un cuantificador universal.)

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

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

Tenga en cuenta que el cuantificador ha cambiado desde $\forall$ $\exists$, que es una característica clave de la anterior prueba.

Finalmente, se preguntan por qué nos prefieren una técnica por encima de otro, ya que ambos son equivalentes. Pero, por supuesto, lo hacemos todo el tiempo, de acuerdo a la comodidad y el gusto: por ejemplo, la inducción, el fuerte de inducción y bien ordenar todos son lógicamente equivalentes, pero la usamos todos los tres. Podríamos por ejemplo, la frase de todas las pruebas de inducción como los recursos para el bienestar de Principio de orden, pero en muchos casos, lo que supondría la inserción de una fatigosa rigamarole "Considerar el conjunto $S = \{ n \in \mathbb{N} \ | \ P(n)\ \text{false} \}$..." que no contribuye a la claridad y concisión de la prueba.

Answer 4

Son trivialmente equivalente. El contrapositivo de (P → Q) (Q → P). Esto es equivalente a (P → (P → ⊥)), que es un curry forma de (Q ∧ P) → ⊥.

Edit: no estoy seguro acerca de su comentario. Reductio parece el más general de la prueba técnica para mí (como Anweshi menciona, funciona para las declaraciones que no son consecuencias); en contraposición, parece menos útil a menos que el contrapositivo forma Q → P es especialmente natural o intuitiva.

Edit 2: las transformaciones parecen ser intuitionistically válido, con la salvedad 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).

En otra nota, es a menudo el caso de que el antecedente P puede ser, naturalmente, visto como una declaración negativa (P'). En estos casos, puede ser capaz de proporcionar una prueba de (Q → P'). Este puede ser el caso de una prueba por contrapositivo que es una "prueba directa", posiblemente de contabilidad para J. Polak los comentarios.

Edit 4: JD Hamkins señala que directa pruebas proporcionan a menudo útil pruebas de que las cuentas intermedias, mientras que las pruebas por las contradicciones no. Pero esta técnica puede ser generalizado empujando contradictorio "contextos" hasta el final de la prueba: es decir, uno puede decir: "vamos a demostrar una contradicción suponiendo que P, Q, R y S. De P, R y S, obtenemos los siguientes lemas..." no Es claro que todas estas pruebas pueden ser, naturalmente, declaró como pruebas por contrapositivo.

Answer 5

Estoy de acuerdo con la respuesta de Joel: las demostraciones por contrapositiva son más satisfactorias que las demostraciones por contradicción, porque te proporcionan más información además de saber que el resultado deseado es verdadero. Por ejemplo, en análisis, las demostraciones por contrapositiva tienden a ser finitarias en naturaleza y proporcionan límites efectivos, mientras que las demostraciones por contradicción (especialmente cuando se combinan con argumentos de compacidad) tienden a ser infinitarias en naturaleza y no proporcionan fácilmente tales límites (a menos que uno convierta muy laboriosamente cada paso del argumento infinitario de contradicción en un argumento de contrapositiva finitario). Hablo de esto, por ejemplo, en

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

Pero, por el mismo motivo, la demostración por contradicción es un método más poderoso en la práctica que las demostraciones por contrapositiva, si tu único objetivo es probar el resultado afirmado; precisamente porque uno es menos ambicioso, puede alcanzar su objetivo más fácilmente.

Hay una analogía con el problema computacional de tratar de encontrar un camino en un laberinto de A a B. El enfoque directo sería comenzar desde A y explorar todas las direcciones que parezcan razonables desde A hasta llegar a B. La analogía de la demostración por contrapositiva sería comenzar desde B reverso y tratar de llegar a A; luego al final simplemente se invierte el camino. La analogía de la demostración por contradicción es una estrategia de encuentro en el medio: explorar hacia adelante desde A y hacia atrás desde B hasta que se llegue a una intersección. Esta es 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 (básicamente por el paradoja del cumpleaños, o la ley de Metcalfe si lo prefieres). Esta analogía es algo simplificada porque incluso en la estrategia de encuentro en el medio no es difícil desenredar la solución para crear un camino directo de A a B; pero con tareas de resolución de problemas más complicadas que laberintos (por ejemplo, intentar convertir varias hipótesis $A_1,\ldots,A_n$ en varias conclusiones $B_1,\ldots,B_m$, usando reglas deductivas como "Si $A_3$ y $C_5$ son verdaderos, entonces $D_7$ es verdadero", etc.) se pueden hacer que las soluciones de encuentro en el medio sean muy difíciles de convertir de nuevo en un argumento directo.

Hay una clase de demostraciones por contradicción a las que llamo argumentos de "objeto no auto-derrotado", que son particularmente difíciles de convertir en demostraciones por contrapositiva. Básicamente, estas demostraciones tienden a mostrar que A es falso utilizando un argumento para establecer $A \implies B$ y otro para establecer $A \implies \neg B$, dando la contradicción (A se derrota a sí mismo). Se puede convertir esto en una demostración por contrapositiva tomando la decisión inspirada de dividir en los dos casos $B$ y $\neg B, y demostrar que cada uno de estos casos implica $\neg A$ tomando las contrapositivas de cada lado del objeto no auto-derrotado, pero es difícil en la práctica motivar esta elección de división en casos a menos que uno haya visto previamente la versión de la argumentación por contradicción. Esto es especialmente cierto si A es una declaración de existencia $\exists x: A(x)$ y B depende de x; entonces la dicotomía $B \vee \neg B$ ni siquiera se puede introducir sin antes introducir a x. Hablo de este tipo de argumento en mi blog en:

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