¿Puede cada prueba por contradicción ser mostrada también sin contradicción?

Question

¿Hay algunas pruebas que sólo se pueden mostrar por contradicción o todo lo que se puede mostrar por contradicción también se puede mostrar sin contradicción? ¿Cuáles son las ventajas e inconvenientes de la demostración por contradicción?

Como un aparte, ¿cómo se demuestra por contradicción visto en general por los matemáticos "avanzados", es un poco de una "salida fácil" cuando se trata de tratar de mostrar algo o está perfectamente bien? Pregunto porque uno de nuestros tutores dijo algo en ese sentido y dijo que no le gustaba la prueba por contradicción.

Answer 1

Para determinar lo que puede y no puede se pruebe por contradicción, tenemos que formalizar una noción de prueba. Como una pieza de notación, dejamos $ \bot $ representan una proposición idénticamente falsa. Entonces $ \lnot A$ la negación de $A$ es equivalente a $A \to \bot $ y tomamos la segunda como la definición de la primera en términos de $ \bot $ .

Hay dos principios lógicos clave que expresan diferentes partes de lo que llamamos "prueba por contradicción":

1. El principio de explosión para cualquier declaración $A$ podemos tomar $ \bot $ implica $A$ "como un axioma. Esto también se llama ex falso quodlibet .

2. El ley del medio excluido para cualquier declaración $A$ podemos tomar $A$ o $ \lnot A$ "como un axioma.

En la teoría de la prueba, hay tres sistemas bien conocidos:

• Lógica mínima no tiene ninguno de los dos principios anteriores, pero tiene reglas básicas de prueba para manipular las conectivas lógicas (distintas de la negación) y los cuantificadores. Este sistema se corresponde más con la "prueba directa", porque no permite aprovechar una negación para ningún propósito.

• Lógica intuitiva incluye la lógica mínima y el principio de explosión

• La lógica clásica incluye la lógica intuicionista y la ley del medio excluido

Se sabe que hay afirmaciones que son demostrables en la lógica intuicionista pero no en la lógica mínima, y hay afirmaciones que son demostrables en la lógica clásica que no son demostrables en la lógica intuicionista. En este sentido, el principio de explosión nos permite probar cosas que no serían demostrables sin él, y la ley del medio excluido nos permite probar cosas que no podríamos probar ni siquiera con el principio de explosión. Así que hay afirmaciones que son demostrables por contradicción que no son demostrables directamente.

El esquema "Si $A$ implica una contradicción, entonces $ \lnot A$ debe aguantar" es cierto incluso en la lógica intuicionista, porque $ \lnot A$ es sólo una abreviatura de $A \to \bot $ y entonces ese esquema sólo dice "si $A \to \bot $ entonces $A \to \bot $ ". Pero en la lógica intuitiva, si probamos $ \lnot A \to \bot $ esto sólo muestra que $ \lnot \lnot A$ se mantiene. La fuerza adicional en la lógica clásica es que la ley del medio excluido muestra que $ \lnot \lnot A$ implica $A$ lo que significa que en la lógica clásica si podemos probar $ \lnot A$ implica una contradicción, entonces sabemos que $A$ se mantiene. En otras palabras: incluso en la lógica intuicionista, si una afirmación implica una contradicción, entonces la negación de la afirmación es verdadera, pero en la lógica clásica también tenemos que si la negación de una afirmación implica una contradicción, entonces la afirmación original es verdadera, y esta última no es demostrable en la lógica intuicionista, y en particular no es demostrable directamente.

Answer 2

Si una declaración dice "no $X$ "entonces está perfectamente bien asumir $X$ llegar a una contradicción y concluir que "no" $X$ ". Sin embargo, en muchos ocasiones se presenta una prueba por contradicción mientras que en realidad no se utiliza (y mucho menos es necesario). El razonamiento entonces va como sigue:

Prueba de $X$ : Supongamos que no $X$ . Entonces... prueba completa de $X$ sigue aquí ... Esto es una contradicción y por lo tanto $X$ .

Un ejemplo famoso es la prueba de Euclides de la infinitud de los primos. A menudo se afirma lo siguiente (no por Euclides, por cierto):

Supongamos que sólo hay un número finito de primos. Entonces... la construcción de la nueva prima sigue ... Esta es una contradicción, por lo que hay infinitamente muchos primos.

Sin la parte de la contradicción, te quedarías con un argumento perfecto. Es decir, dado un conjunto finito de primos, se puede construir un nuevo primo.

Este tipo de presentación es realmente algo que deberías aprender a evitar. Una vez que seas consciente de este patrón, es sorprendente la frecuencia con la que te encontrarás con él, incluso aquí en math.se.

Answer 3

Depende de si eres intuicionista o no (o ambos? o ninguno? ¿Quién sabe sin la ley del medio excluido ). Según el artículo de Wikipedia, incluso los intuicionistas aceptan algunos versiones de lo que se podría llamar prueba indirecta, pero que la mayoría rechaza. En ese sentido, una prueba directa sería preferible (y a menudo es incluso un poco más elegante).

---

Un ejemplo:

Teorema. Existen números irracionales $a,b$ de tal manera que $a^b$ es racional.

Prueba: Supongamos que $a,b \notin \mathbb Q$ siempre implica $a^b \notin \mathbb Q$ . Luego $u:= \sqrt 2^{ \sqrt 2} \notin \mathbb Q$ y $u^ \sqrt 2= \sqrt 2^{ \sqrt 2 \cdot\sqrt 2}= \sqrt 2^2=2 \notin \mathbb Q$ - ¡Contradicción!

De hecho, un intuicionista se quejaría de que no exhibimos un par $(a,b)$ con $a,b \notin \mathbb Q$ y $a^b \in \mathbb Q$ . En cambio, sólo mostramos que $( \sqrt 2, \sqrt 2)$ o $(u, \sqrt 2)$ es un par. Convertir la prueba dada arriba en una prueba directa y constructiva requeriría de hecho probar una de las dos opciones posibles $u \in \mathbb Q$ o $u \notin\mathbb Q$ .

Answer 4

Mira este post: ¿Las pruebas por contradicción son más débiles que otras pruebas? .
Hay algunas respuestas maravillosas relacionadas con su pregunta - y se dirige, directamente, a su "aparte": Vea, en particular, lo que escribe JDH.

---

Una de las ventajas de construir pruebas directas de las proposiciones, cuando esto es factible, es que se pueden descubrir otras proposiciones útiles en el proceso. Es decir, las pruebas directas ayudan a aclarar las condiciones necesarias y suficientes que hacen que un teorema sea verdadero, y proporcionan una estructura que demuestra cómo se relacionan estas condiciones, y cómo la cadena de implicaciones implica la conclusión.

Las pruebas indirectas, por otro lado (alias "pruebas por contradicción") sólo nos dicen que suponer que una proposición es de otra manera lleva a una contradicción en algún momento. Pero tal prueba no proporciona realmente el tipo de comprensión que se puede obtener de las pruebas directas.

Esto no quiere decir que las pruebas indirectas no tengan su lugar (por ejemplo, ¡son útiles cuando se les pide que prueben las proposiciones durante un examen de tiempo limitado!) A menudo ayudan a "descartar" ciertas proposiciones sobre la base de que contradicen axiomas o teoremas bien establecidos. Además, las pruebas indirectas son a veces más intuitivas que las pruebas directas. Por ejemplo, probar que $ \sqrt {2}$ no es racional usando una prueba por contradicción es limpia, e intuitiva.

A veces una prueba indirecta surgirá primero, después de lo cual se puede tratar de proceder a construir una prueba directa para probar la misma proposición. Es decir, proporcionar una prueba indirecta de una proposición a menudo motiva la construcción de pruebas directas.

---

Editar:

Encontré esta entrada en el blog (Gowers's Weblog) ¿Cuándo es necesaria una prueba por contradicción . de la cual citaré un comentario introductorio:

Parece posible clasificar los teoremas en tres tipos: aquellos en los que sería ridículo utilizar la contradicción, aquellos en los que hay pruebas igualmente sensatas utilizando la contradicción o no utilizando la contradicción, y aquellos en los que la contradicción parece forzada. ¿Pero qué es lo que pone a un teorema en una de estas tres categorías?

El correo sigue inmediatamente con una agradable respuesta de Terence Tao.

Answer 5

Algunos puntos de mi (limitada) experiencia:

• Me encanta la prueba por contradicción y la he usado en clases de nivel graduado y a nadie pareció importarle mientras la lógica fuera infalible.
• Para mí, es mucho más fácil pensar en una propuesta en términos de "¿Y si esto no fuera cierto?". Ese es usualmente mi primer instinto, esto hace que la prueba por contradicción sea la primera opción natural. Por ejemplo, si me pidieran que probara algo como "Probar que una matriz no singular tiene un único inverso". Mi primer instinto sería "¿Y si una matriz no singular tuviera 2 inversos?" y a partir de ahí, la prueba sigue limpiamente.
• A veces, sin embargo, las contradicciones no son claras y la prueba por simples deducciones lógicas tomaría probablemente 5 líneas mientras que la contradicción tomaría millones. Podría señalarle pruebas específicas pero tendré que hacer algunas averiguaciones. Además, si miras cada prueba e intentas usar la Prueba por Contradicción, otro problema al que te enfrentarás es que a veces, declararás tu intención de contradicción pero nunca la usarás. En otras palabras, resuelve usando la prueba directa.
• Otro aspecto de Proof by Contradiction (IMHO) es que realmente debes conocer todas las definiciones y sus declaraciones equivalentes bastante bien para llegar a una bonita contradicción. De lo contrario, terminará probando varios lemas en el camino, lo que parece limpio en una prueba directa, pero no tanto en una Prueba por Contradicción, pero de nuevo, esto podría ser una elección personal.

En resumen, si te resulta más fácil pensar en términos de "Qué pasa si no" entonces adelante, úsalo pero asegúrate de que tus habilidades de prueba usando otras estrategias son tan buenas porque $ \exists $ clavo que no puedes golpear con el martillo de PbC que llevarás.