¿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

A menudo da la sensación de que una prueba por contradicción es como exponer tu punto de vista a través de un chiste ingenioso y el contrapositivo es sentarse y explicar por qué el chiste es gracioso.

Dado que los dos enfoques son lógicamente equivalentes y que el lector medio de la revista suele pasar fácilmente de uno a otro, para mí la distinción se reduce al estilo. La mayoría de los argumentos que he visto por contradicción suelen ser más cortos, intuitivos y elegantes. Por lo tanto, normalmente prefiero la prueba por contradicción (suele ser la primera prueba que se me ocurre...) a menos que los pasos del contrapositivo sean especialmente perspicaces.

Answer 2

Hay otra razón para preferir las pruebas de la contraposición a las pruebas por contradicción que no se ha mencionado hasta ahora: Es más difícil que surjan argumentos erróneos que parezcan pruebas correctas cuando se intenta demostrar la contraposición directamente. Cuando se intenta demostrar algo por contradicción, es fácil declarar la victoria si se puede producir un sinsentido, incluso si el sinsentido es el resultado de un error.

Para un punto de vista extremo basado en esta perspectiva, Halsey L. Royden escribe lo siguiente en el "Prólogo al estudiante" de su libro de texto de análisis:

Se recomienda a todos los estudiantes, en los términos más enérgicos posibles, que eviten las pruebas por contradicción. Hay dos razones para esta prohibición: En primer lugar, tales pruebas son muy a menudo falaces, la contradicción en la contradicción en la última página se debe a una deducción errónea en una página anterior, y no de la incompatibilidad de $A$ con $\neg B$ . En segundo lugar, incluso cuando es correcta, dicha prueba da poca información sobre la conexión entre $A$ y $B$ mientras que tanto la prueba directa como la prueba por contraposición construyen una cadena argumental que conecta $A$ con $B$ . Una de las razones por las que los errores son mucho más probables en las pruebas por contradicción que en las pruebas directas o por contraposición es que en una prueba directa (suponiendo que la hipótesis no sea siempre falsa) todas las deducciones de la hipótesis son verdaderas en los casos en que la hipótesis se cumple, y de forma similar para las pruebas por contraposición (si la conclusión no es siempre verdadera) las deducciones de la negación de la conclusión son verdaderas en los casos en que la conclusión es falsa. En cualquier caso, se trata de enunciados verdaderos, y la intuición y el conocimiento de lo que es verdadero ayudan a evitar que uno haga afirmaciones erróneas. En las pruebas por contradicción, sin embargo, se está (asumiendo que el teorema es verdadero) en el mundo irreal donde cualquier afirmación puede ser derivado, y por lo tanto la falsedad de un enunciado no es una indicación de una deducción errónea.

Por supuesto, esto es sobre todo didáctico; está claro que Royden no es constructivista. Un punto didáctico relacionado es que los estudiantes podrían ser capaces de visualizar e imaginar el antecedente de una prueba del contrapositivo. Como el antecedente de una prueba por contradicción es lógicamente imposible, esto no funciona con las pruebas por contradicción. Al menos no si no se tienen las habilidades de la reina de Alicia en el País de las Maravillas, que en sus años de juventud era capaz de imaginar seis cosas imposibles antes del desayuno.

Answer 3

Parece que hay una diferencia, aunque no sé cómo distinguirlas formalmente, pero aquí hay dos casos que las distinguen:

*Sea V un espacio vectorial. Un mapa lineal f sobre V es inyectivo si su núcleo es 0. (sí, ya sé que es un iff). El contrapositivo es, si f es un mapa lineal y ker f no es 0, entonces f no es inyectivo. Prueba: $v\in \ker f$ significa que no es cero $f(v) = f(0) = 0$ . No tenemos que suponer en la prueba que f es inyectiva primero y obtener una contradicción.

Aquí estamos discutiendo sobre una clase de objetos con una propiedad y estamos tratando de demostrar otra de esa clase.

--

*sqrt(2) es irracional. Podemos redactar esto (artificialmente) como x = sqrt(2) implica que no existen a,b racionales tales que x = a/b. Sin embargo, si intentamos el contrapositivo, obtenemos que existen a,b racionales tales que x = a/b implica que x no es sqrt(2). Pero para demostrar esto todavía tenemos que suponer que a/b = sqrt(2) y derivar una contradicción.

En este caso se trata de demostrar que un solo objeto no posee una determinada característica. Sin embargo, debe haber un tratamiento más formal de estas diferencias...