¿Por qué la prueba por contradicción se considera una prueba débil en matemáticas?

Answer 1

Hay dos objeciones independientes.

• No son tan “limpios”

Esta primera objeción tiene que ver con la elegancia, la comprensión y la pedagogía.

Las pruebas por contradicción a veces tienen un paso adicional. Algunos pueden acortarse haciéndolos directos. Sin embargo, ese no es siempre el caso. Ocasionalmente, una prueba por contradicción es más corta.

Incluso cuando es necesaria una prueba por contradicción, puede ser difícil de seguir. Toda la prueba es hipotética. Discute cosas que resultan no ser posibles. Tome los Elementos de Euclides, Libro III, Proposición 10 por ejemplo.

Un círculo no corta un círculo en más de dos puntos.

Una prueba directa puede ser posible cuando tienes coordenadas para tus puntos, pero Euclides trabajó 1900 años antes de que se inventaran, por lo que dio una prueba por contradicción. Él supone que dos círculos se encuentran en tres puntos B, G y H. Debido a que es una situación hipotética, el diagrama que dibuja es imposible. Sin embargo, él persevera y finalmente llega a una contradicción con la Propuesta 5 anterior “… por lo tanto, los dos círculos ABC y DEF que se cortan entre sí tienen el mismo centro P, lo cual es imposible”.

Es más fácil seguir una prueba directa, y eso significa que es más fácil para los estudiantes entenderla.

• Pruebas de existencia no constructivas.

Una forma de demostrar que algo existe es con una prueba por contradicción. Asumes que no existe y dibujas una contradicción, y por lo tanto concluyes que existe. Saber que algo tiene que existir puede ser útil de alguna manera, pero no puede hacer nada si no sabe cómo encontrarlo.

Euclides no tenía ninguna de esas pruebas. Los elementos consisten en pruebas constructivas.

La prueba no constructiva más famosa es el teorema del punto fijo de Brouwer. Brouwer demostró que, bajo ciertas situaciones, una función tenía que tener un punto fijo, pero su prueba no era constructiva. No estaba satisfecho con su prueba y se esforzó por restringir las matemáticas para excluir estas pruebas no constructivas, fundando así las matemáticas intuicionistas.

• ¿ Otras objeciones?

Puede haber otras objeciones, especialmente las de la primera categoría que afirman que las pruebas por contradicción no son tan buenas como las pruebas directas. La objeción de Brouwer es más grave. Incluso si no llega tan lejos como Brouwer y rechaza por completo las pruebas no constructivas, probablemente aún prefiera las constructivas.

Answer 2

Esto no pretende ser una respuesta completa, ya que David Joyce ya ha dado una excelente, pero solo quería agregar que es fácil dar accidentalmente pruebas incorrectas mediante el uso de contradicciones.

El esquema básico es el siguiente:
1) Para probar X, suponga que X es falso.
2) Haz algunas cosas complicadas. Comete un error sutil en el proceso.
3) Date cuenta de que algo se rompió y reclama la victoria cuando la “contradicción” fue tu error.

Imagínese leer la prueba intencionada de alguien donde el paso 2 es difícil de entender, tiene ineficiencias y salta incoherentemente, mientras tiene la tarea de averiguar si es correcto.

(Para una mejor exposición de esto de un tipo más famoso, vea Peligros de la prueba por contradicción de Henry Cohn)
______________________________________________________
Editar: Al leer esto de nuevo, parece que solo digo que podría ser difícil verificar una prueba mal hecha para asegurarme de que no está rompiendo nada.

Sin embargo, hay una diferencia entre probar algo directamente y usar la contradicción. Cuando pruebas algo directamente, hay una sensación interna de que no estás rompiendo algo y todo parece plausible. (Piense: ¿Dos de las deducciones que hace se contradicen entre sí? ¿Algo suena demasiado bueno para ser verdad? ¿Una de sus deducciones generaliza de alguna manera un famoso problema abierto?) Los errores básicos a menudo se corrigen cuando nota inconsistencias.

Sin embargo, cuando usa la contradicción, está tratando de encontrar una inconstancia, por lo que es mucho más difícil determinar si la inconstancia se debió a la suposición o al error que cometió.

Answer 3

Los programadores saben de algo llamado refactorización de código, que es algo como esto: cuando comienzas a escribir código para resolver un problema, puedes escribir lo que sea natural para ti, usando todas las herramientas disponibles a tu disposición y, a menudo, con una comprensión incompleta de la estructura del problema. Una vez que haya terminado y tenga el código de trabajo, si se encuentra volviendo a revisarlo, es bueno refactorizar el código; estos cambios no lo hacen más poderoso, sino que lo hacen más modular, más fácil de entender, más fácil de extender y menos Es probable que contenga errores.

En matemáticas, a menos que esté trabajando en lógica intuicionista o algo así, el uso de la prueba por contradicción no hace que la conclusión de la prueba sea más débil en el sentido técnico. Pero puede marcar una gran diferencia pedagógicamente, y debe intentarlo: reescribir una prueba matemática para evitar la prueba por contradicción es como refactorizar : puede hacer que su prueba sea más modular, más fácil de entender, más fácil de extender y Es menos probable que contenga errores.

(Y ocasionalmente puede encontrar que la versión que usa prueba por contradicción es mejor después de todo, así como podría refactorizar y descubrir que la versión original era mejor; está bien volver a esa versión. Pero debe intentarlo).

Aquí hay más sobre el tema, la mayoría de ellos por matemáticos que trabajan:
Reductio ad absurdum o el contrapositivo? [MathOverflow]
¿Por qué a algunas personas no les gustan las pruebas por contradicción?
¿Son las “pruebas por contradicción” más débiles que otras pruebas?
Prueba de negación y prueba por contradicción por Andrej Bauer
¿Cuándo es necesaria la prueba por contradicción? [“pensando en voz alta” por Timothy Gowers, pero vea la publicación anterior de Andrej Bauer señalando algunos errores que tiene]
¿Es esta una forma tonta de hacer pruebas?
¿Puede toda prueba por contradicción también mostrarse sin contradicción?
¿Podría estar usando demasiado la prueba por contradicción?

Answer 4

La principal objeción a las pruebas por contradicción, planteada por los constructivistas matemáticos, es su naturaleza no constructiva. Obviamente, esta es una opinión, aunque ampliamente aceptada en las matemáticas modernas.

La cuestión clave en la matemática constructiva, la que la originó, es la existencia de paradojas matemáticas (por ejemplo, vea ¿Cuáles son algunas de las paradojas más famosas?). Fueron descubiertos bastante tarde, a fines del siglo XIX (aunque algunos, como la paradoja del mentiroso, eran conocidos por miles de años), mostraban claramente límites y problemas inherentes a la teoría clásica de conjuntos y la lógica clásica.

Las pruebas por contradicción son la clase principal de pruebas no permitidas en las matemáticas constructivas. La solidez de las pruebas por contradicción se basa en la aceptación de la ley de doble negación [matemáticas] \ neg \ neg A = A [/ matemáticas] que no se acepta en las matemáticas constructivas.

Se ha comprobado que la ley de la doble negación es equivalente a la ley del medio excluido [matemática] A \ vee \ neg A [/ matemática] en términos de constructivismo y puede usarse en lugar de ello para no permitirlo en pruebas.

Intuitivamente, para producir una prueba constructiva, no es suficiente demostrar una contradicción, uno tiene que producir (de manera constructiva, de ahí el nombre) un elemento que satisfaga la propiedad. La restricción de la ley del medio excluido es aún más clara, ya que en matemáticas constructivas uno tiene que mostrar de qué parte del medio excluido ([matemática] A \ vee \ neg A [/ matemática]) proviene la prueba constructiva en lugar de simplemente indicarlo debe provenir de [math] A [/ math] o [math] \ neg A [/ math].

Siempre hubo esperanzas grandiosas de que la teoría de conjuntos clásica sea la base de todas las matemáticas. El innovador trabajo de Goedel sobre teoremas de incompletitud mostró la insuficiencia y las limitaciones de la teoría clásica de conjuntos y la lógica clásica.

Un trabajo más reciente sobre proposiciones como tipos, que vincula la lógica con la computación, muestra en mi humilde opinión conexiones asombrosas entre pruebas no constructivas y computaciones y programación.

En los términos más simples, en el paradigma de proposiciones como tipos para cada prueba (constructiva) de una proposición dada, hay un programa del tipo correspondiente, y viceversa.

Sorprendentemente, hay programas que corresponden a pruebas no constructivas, especialmente las pruebas por contradicción, que implican la teoría de las continuaciones.

Se desarrollaron continuas para dar semántica a los saltos en los lenguajes de programación, lo que obstaculizó los primeros intentos. Puede pensar en una continuación como un cálculo que, dado un valor, llevará al programa a su respuesta final.

Por lo tanto, una prueba por contradicción tiene un programa correspondiente donde el uso de contradicción corresponde (hablando informalmente) a la invocación de una continuación.

A finales de los años ochenta y principios de los noventa, hubo un estallido de actividad en este campo que se ha calmado pero está aumentando nuevamente en formas alternativas, por ejemplo, programación reactiva.

Answer 5

Debido a que generalmente resulta en una prueba no constructiva, lo que significa que no se puede encontrar un ejemplo específico de lo que sea que estaba tratando de mostrar.

Answer 6

Creo que, además de su falta de constructividad, algunos matemáticos no desean probar la contradicción porque se basa en el supuesto de que la lógica / teoría matemática es coherente (a lo que Robert J. Koller hizo alusión). Según el primer teorema de incompletitud de Godel, la lógica matemática no puede ser al mismo tiempo consistente y completa. En la práctica, no podemos probar que la lógica matemática sea consistente, solo la asumimos y, por lo tanto, sacrificamos la integridad.
Pero además de este punto de vista más bien filosófico, algunas personas tienden a usar en exceso la prueba por contradicción donde se pueden encontrar pruebas directas. El peor de los casos, es cuando debes demostrar que una propiedad P es verdadera, supones que P es falsa, demostrar que P es verdadera, entonces obviamente tienes una contradicción :-). Por supuesto, todo esto es inútil, pero he visto a algunas personas hacerlo. La constructividad, como se mencionó en las publicaciones anteriores, es con mucho el criterio más importante para preferir la prueba directa sobre la prueba por contradicción.

Answer 7

Depende mucho del área matemática del teorema y del enunciado del teorema. Si estamos en el área de las matemáticas contables (por ejemplo, la teoría de números) y queremos probar que una determinada solución sobre los enteros (racionales) de una ecuación no existe, una prueba por contradicción no es débil.

Si desea resolver sobre los reales, una prueba por contradicción ya es más débil, porque hacer el supuesto hipotético “suponga que hay una x que resuelve la ecuación” implica proporcionar un número infinito de dígitos. Si bien establecer una solución hipotética sobre los racionales requiere un número finito de símbolos. Peor aún si la solución hipotética se da usando el axioma de elección (que casi solo se usa junto con la prueba por contradicción).

Si el teorema no se trata de la no existencia de un objeto, sino de la existencia del objeto. La prueba por contradicción proporciona mucha menos información que una prueba “constructiva” que le proporciona “un algoritmo” para construir el objeto. O, si trabaja sobre los reales, una secuencia que converge al objeto.

Answer 8

Porque es más probable que se equivoquen.
Los matemáticos principiantes (¡soy uno!) A menudo abordan problemas difíciles de la siguiente manera:

1) Asumen el resultado negativo.
2) Manipulan algebraicamente la función derivada del resultado negativo en alguna forma.
3) Utilizan algún proceso comprensible para transformar o expandir la función en una diferente.
4) Manipulan algebraicamente la nueva función en alguna forma nueva.
5) Utilizan algún proceso comprensible para transformar o expandir * esa * función en una diferente.
6) Manipulan algebraicamente la nueva función hasta que encuentran que contradice algún hecho conocido sobre las matemáticas.

Presentan sus resultados con entusiasmo a un tutor, un profesor u otro sabio de matemáticas. El sabio matemático (con suerte con gran paciencia) señalará su error de álgebra en el paso 4.

A diferencia de las pruebas de contradicción, las pruebas directas se basan tanto en conceptos como en manipulación. Por lo tanto, no pueden construirse simplemente transformando y manipulando el problema. Se aseguran de que comprenda por qué la prueba es correcta.

Answer 9

Los resultados de las pruebas de existencia por contradicción generalmente no son constructivos. (Un contraejemplo podría ser una prueba por contradicción de que cierto algoritmo para la construcción de un objeto es correcto). Las pruebas de existencia constructivas a menudo son satisfactorias y útiles, al menos si están disponibles y no son demasiado complicadas. Por ejemplo, la prueba del teorema de existencia / unicidad para ecuaciones diferenciales ordinarias que utilizan la iteración de Picard es constructiva. No es un algoritmo muy bueno para resolver numéricamente ecuaciones diferenciales, pero es un algoritmo que puede ejecutar antes de comprender cualquier otro método numérico.

Algunas pruebas por contradicción son realmente pruebas por contraposición, es decir, prueban p-> q demostrando directamente ~ q-> ~ p. Estas pruebas son a menudo bastante claras e iluminadoras. Otras pruebas por contradicción proceden concluyendo una contradicción que aparentemente tiene poco que ver con la pregunta original. Esto a veces no es muy esclarecedor, y también tiende a no proporcionar un método para otros problemas.

Relativamente pocas, pero algunas, a las personas les gustaría evitar suposiciones innecesarias tanto en sus matemáticas como en su lógica subyacente. Las pruebas por contradicción son válidas siempre que asuma la eliminación de doble negación o, de manera equivalente, la ley del tercero excluido. Estos se mantienen en la lógica clásica pero no en, por ejemplo, la lógica intuicionista. Por lo tanto, una prueba por contradicción no es válida sin esta suposición en la lógica, mientras que el resultado en sí podría ser demostrable en una lógica más débil.

Answer 10

“También escuché que los matemáticos continúan buscando pruebas directas incluso si una declaración ha sido probada por contradicción”. Las razones por las que la respuesta puede ser correcta, soy médico, uso continuamente teoremas matemáticos especialmente del análisis de álgebra y análisis funcional, y Supongo que la utilidad de la prueba directa es que hay menos probabilidades de estar equivocado, pero sobre “También he oído que los matemáticos continúan buscando pruebas directas incluso si una declaración ha sido probada por contradicción”. Si la prueba de reducción absurda es correcta, no es necesario que exista una prueba constructiva, pero hay un criterio filosófico llamado constructivismo que considera que la prueba de contradicción no es válida no porque su lógica sea errónea, porque consideran que las matemáticas son construcciones mentales ( eso es absurdo, 3 + 2 = 5 es cierto incluso si no hay 5 cosas para contar en el universo, pero piensan de esta manera). Hay algunas matemáticas constructivistas, pero es imposible usar las matemáticas constructivistas para hacer arquitectura, informática, robótica, psicología, estadística, física, química, biología. Cuando QM aún no es rigurosamente del formalismo matemático (esa matemática actual única que no tiene imposiciones filosóficas) las computadoras todavía funcionaban. Esto no va en contra del rigor matemático, pero las ciencias experimentales para avanzar se ven obligadas a trabajar con conceptos matemáticos que en el presente todavía no son rigurosos pero son pausibles y después de muchos años los matemáticos demuestran su consistencia. Son muchos ejemplos, dirac delta “función”, números complejos, etc.

Answer 11

El problema de la existencia con pruebas no constructivas se ha mencionado en otras respuestas, pero las objeciones a las pruebas no constructivas son un poco más profundas. Aunque las matemáticas están “inspiradas” por intuiciones, podría decirse que los objetos matemáticos son pura definición, y lo que sabemos de ellos es solo lo que se puede leer de una prueba. En pocas palabras, el significado de una fórmula matemática ES su prueba.

Entonces, tener una prueba no constructiva es saber que una fórmula es verdadera, pero no lo que significa.

(Quizás; hay muchos escritos filosóficos sobre esto).

Answer 12

Noticias para mí que esto es así. También sería una novedad para Hardy, escribió:

Reductio ad absurdum, que Euclides amaba tanto, es una de las mejores armas de un matemático. Es un juego mucho más fino que cualquier juego de ajedrez: un jugador de ajedrez puede ofrecer el sacrificio de un peón o incluso una pieza, pero un matemático ofrece el juego.

La prueba de Euclides de la infinitud de los números primos es muy hermosa, creo; y es prueba por contradicción.

Answer 13

Una prueba por contradicción me parece perfectamente bien siempre que acepte la equivalencia lógica de “Si A, entonces B” y su contrapositiva “Si no-B, entonces no-A”. Las dos declaraciones tienen la misma tabla de verdad y son falsas solo en la situación en que A es verdadero y B es falso.

Probar “Si A, entonces B” por contradicción es lo mismo que probar directamente “Si no-B, entonces no-A”.

A decir verdad, no veo el problema. Las dos declaraciones son lógicamente iguales.

Answer 14

Toda prueba es buena, siempre y cuando sea correcta. Las pruebas por contradicción pueden ser elegantes, cortas, al grano o pesadas, largas, incorrectas, ¡como cualquier otro tipo de prueba!
No proporcionar una prueba constructiva en el caso de una prueba de existencia es un punto válido, pero desde mi experiencia, saber que algo es posible es más del 50% de la batalla de hacerlo realmente. A veces sigo ese razonamiento en mis pruebas también “ok, supongo que es verdad; ¡ahora demostrémoslo!”.
Por el contrario, trabajar en una prueba por contradicción puede ayudarlo a darse cuenta de que lo que está tratando de probar está mal, ya que (si tiene cuidado con su prueba) terminará golpeando muchos callejones sin salida. He encontrado mejores soluciones a un problema tratando de demostrar que mi solución anterior era la mejor que había, por contradicción 🙂
Así que tengo una debilidad por las pruebas de contradicción. No es que ningún otro tipo de prueba sea inferior como dije anteriormente.

Answer 15

Nunca he oído que una prueba por contradicción sea débil. De hecho, iría tan lejos como para decir que es extremadamente ubicuo, ¡lo que parece implicar su fuerza!
Sin embargo, supongo que una prueba directa podría ser muy deseable ya que las suposiciones que haces pueden ser parte del proceso de descubrimiento, es decir, una prueba directa puede señalar la dirección para futuras pruebas que juegan con las suposiciones que haces. Cuando haces una prueba por contradicción, jugar con tus suposiciones puede no darte ninguna pista sobre posibles direcciones futuras.
Para decirlo de otra manera: cuando haces una prueba directa, inmediatamente ves el flujo lógico de tus supuestos, y cuando juegas con los supuestos, puedes tener una idea de formas más generales del problema / respuesta.
Si hace una prueba por contradicción, si bien es cierto, está muy adaptada para esa prueba específica y no sugiere más descubrimientos posibles, per se.

Answer 16

No es débil en absoluto. La gran mayoría de los matemáticos adora la prueba por contradicción. Tales pruebas generalmente no son constructivas. Esto parece molestar a una pequeña minoría, especialmente a aquellos que se convirtieron en informáticos antes de interesarse por las matemáticas.

Answer 17

No es constructivo. Por ejemplo, usando una prueba indirecta o un medio excluido de manera equivalente, podemos probar que existe algún número con alguna propiedad sin poder decir qué número es.

Answer 18

Una prueba es una prueba. No hay pruebas “débiles” ni “fuertes”. De lo contrario, no es una prueba matemática … ¡Puede que quieras decir que es menos “elegante”!

Bueno, alguna prueba como la prueba de Pitágoras de que [math] \ square {2} [/ math] no es racional se considera sumamente elegante desde hace más de 25 siglos, incluso si es por contradicción. Y puede ser porque fue por contradicción.

Después de todo, fue la primera vez registrada en la historia humana que se demostró que algo no puede ser.

Answer 19

Si un sistema es consistente, la prueba por contradicción es tan válida como la prueba directa.

Sin embargo, en el caso de una prueba de existencia, la construcción real del objeto cuya existencia se afirma es de primera clase.

Answer 20

Es una tontería total y una superstición, al igual que los mitos en la ingeniería de software que dicen que las cosas deben hacerse de cierta manera. Las pruebas por contradicción son tan buenas como las pruebas por cualquier otro método. Las respuestas dadas por otros supuestos matemáticos aquí son incorrectas y estoy muy sorprendido de que cometan un error tan básico. La prueba por contradicción es un método de prueba muy poderoso que no es menos correcto que cualquier otro método de prueba.

Estos tipos están tratando de impulsar una agenda (se den cuenta o no) que comenzó con la introducción de la filosofía en las matemáticas a principios del siglo XX por personas como Frege y Russell. Estas son las falacias que llevaron a la idea de indecidibilidad. Todos se originan de la falacia de (supuestamente) conjuntos “infinitos” introducidos por Cantor.