Prueba por contradicción
# Prueba por contradicción

Se entiende que la prueba por contradicción es una forma de demostración utilizada en lógica proposicional del tipo indirecta y esta sigue los siguientes pasos cuando es aplicada para demostrar alguna afirmación:

* Se quiere demostrar que una afirmación P es verdadera.
* Se asume que P es falsa.
* Se muestran las consecuencias del hecho de que P sea falsa.
* Se llega a un absurdo o imposibilidad.
* Como la afirmación P puede ser verdadera o falsa, y ya se demostró que no puede ser falsa ya que esto conlleva a incongruencias matemáticas, se prueba así que P debe ser verdadera.

## Ejemplo

$Probar:A$

$Premisas\left\{{\begin{matrix}\left(\sim B\vee C\right)\rightarrow A&\\B\rightarrow D&\\C\vee \sim D\end{matrix}}\right.$

Como nos muestra Bruce Ikenaga, en lógica se usa la siguiente notación para explicar la prueba por contradicción:

* $\sim A$
* $\left(\sim B\vee C\right)\rightarrow A$
* $\sim \left(\sim B\vee C\right)$
* $B\wedge \sim C$
* $B$
* $\sim C$
* $B\rightarrow D$
* $D$
* $C\vee \sim D$
* $C$
* $C\wedge \sim C$
* $A$

## Tipos de pruebas

Como afirman Körner y Neale en su artículo: al ser una ciencia exacta, el concepto de demostración es clave en matemáticas. Existen una gran variedad de formas utilizadas para probar alguna proposición, corolario, teorema, etc. en esta ciencia. Generalmente, las pruebas utilizadas en matemáticas son de dos tipos: directas e indirectas. En las directas, se empieza con una afirmación P y hay que demostrar que a partir de esa afirmación, utilizando principios ya demostrados, se llega a una condición Q. Algunas de las pruebas directas más comunes son:

* Prueba por inducción matemática: Una de las pruebas más sólidas que existen en las matemáticas aplicadas. Se comienza con una base de inducción y se termina con una hipótesis de inducción.
* Prueba por contraejemplo: En este caso, se busca un ejemplo específico que cumpla con una afirmación P, pero no con la condición Q.
* Prueba por exhaución: La condición Q se divide en un número finito de casos, al demostrar todos los casos se demuestra Q.

Por otro lado existen las pruebas indirectas, las cuales empiezan con una afirmación P y se quiere llegar a la condición Q. Pero en este tipo de pruebas se empieza asumiendo que P implica no Q y a partir de ahí se desarrolla hasta llegar a una imposibilidad, demostrando entonces que P sí implica Q. Los 2 tipos de pruebas indirectas más comunes son: prueba por contrapositivo y por contradicción.

Con base en lo anterior, cabe destacar que la prueba por contradicción es significativamente diferente de las formas más tradicionales de demostrar afirmaciones, ya que parte de que lo que queremos probar es falso, aun cuando la lógica dicta que no debería ser así.Siempre es más recomendable demostrar una afirmación con una prueba directa que con una prueba indirecta como la de contradicción, ya que las directas son más sólidas. Sin embargo, hay casos donde no se pueden emplear pruebas directas, como en el siguiente ejemplo:

Proposición: Demostrar que √2 es un número irracional. (Nota: Un número irracional es aquel que no se puede escribir como cociente de 2 números enteros.)

Al analizar por un momento el problema, una prueba directa de esta proposición implicaría que se probaran enteros p y q, hasta encontrarse una pareja (p, q) que cumpliera con que: $2=p^2/q^2.$ El problema es que existen infinitos números enteros, por lo que es imposible tratar de resolver este problema a través de una prueba directa. Siguiendo los pasos establecidos anteriormente, vamos a demostrar la proposición dada por contradicción:

* Paso 1: Asumimos que la proposición es falsa, es decir, que es racional.
* Paso 2: Se hace el siguiente razonamiento:

    ${\sqrt {2}}=p/q$
    Donde al menos uno de los 2 es impar. Sin pérdida de generalidad, asumir que q es impar.
    $2=p^{2}/q^{2}$
    $2q^{2}=p^{2}$
    Entonces $p^{2}$ es divisible entre 2, lo cual implica que p también lo es. Escribimos $p=2r$.
    $2q^{2}=p^{2}=\left(2r\right)^{2}=4r^{2}$
    Simplificando tenemos:
    $q^{2}=\left(2r\right)^{2}$
* Paso 3: Entonces $q^{2}$ es par y por tanto q también lo es. Pero q es impar, lo que nos lleva a una contradicción ya que q no puede ser par e impar al mismo tiempo.
* Paso 4: Como demostramos que si ${\sqrt {2}}$ es racional se llega a una incongruencia, ${\sqrt {2}}$ no puede ser racional. Siendo entonces irracional ya que un número solo puede ser racional o irracional.

## Reductio ad absurdum

Reductio ad absurdum (en latín, que en español significa “reducción al absurdo”) es sin lugar a dudas uno de los argumentos más utilizados cuando se utiliza la prueba por contradicción. En el ejemplo dado anteriormente se utilizó este argumento para demostrar que la raíz cuadrada de dos es un número irracional. La reducción al absurdo empezó asumiendo que uno de los dos enteros es par y acabó cuando se mostró que el denominador era par e impar al mismo tiempo, lo cual es un absurdo. A continuación se muestra una definición formal de este término dada por la Internet Encyclopedia of Philosophy:

Un ejemplo clásico del uso de este argumento al demostrar una proposición por contradicción es la siguiente:

Proposición: Demostrar que la suma de un número racional y un número irracional es otro irracional. En este caso, al utilizar el reductio ad absurdum, se llega a que un número es racional e irracional al mismo tiempo, lo cual es un absurdo y así se demuestra la proposición. Aunque el argumento reductio ad absurdum es una herramienta vital de las pruebas por contradicción es importante notar que prueba por contradicción no implica reductio ad absurdum ya que en una prueba por contradicción se llega a una imposibilidad. Un absurdo es un tipo de imposibilidad pero no es la única, como se verá más adelante.

## Descenso infinito

Como se mencionó anteriormente se analizará un método que se basa en la prueba por contradicción sin llegar a un absurdo pero aun así llegando a una imposibilidad. El método se llama descenso infinito y fue descubierto por el matemático y abogado francés Pierre de Fermat alrededor de 1640, cuando lo usó por primera vez para demostrar el caso n=4 de uno de los teoremas más importantes y conocidos de las matemáticas puras: el último teorema de Fermat.

El método se basa en 2 herramientas muy importantes:

* La prueba por contradicción.
* El orden de los números naturales.

El descenso infinito es una herramienta de demostración que funciona de la siguiente forma:

* La idea es llegar a una imposibilidad.
* Se comienza con 2 propiedades de los números naturales muy importantes: que llevan un orden y que tienen un límite inferior, es decir, empiezan de cero.
* Conociendo lo anterior, la idea es demostrar que si ciertas propiedades o relaciones existen en un grupo de números naturales, entonces existe un procedimiento a seguir que generará otro grupo de números con las mismas propiedades, excepto que tienen un valor absoluto menor que sus equivalentes del grupo precedente, creando un descenso infinito.
* Pero se sabe que no puede existir un descenso infinito en los números naturales ya que existe el límite inferior de cero, creando una contradicción.

A continuación se pone de ejemplo la demostración del caso n=4 del último teorema de Fermat para dar una mejor idea de cómo funciona este método basado en la prueba por contradicción:

Teorema. No existen enteros x, y, z que satisfagan la siguiente ecuación diofántica: $z^4+y^4=x^4$

Demostración:

* El primer paso es reescribir la ecuación de la siguiente forma: $(z^2)^2+y^4=x^4$
* Notar que (z, $y^2,$ $x^2)$ es una Terna Pitagórica Primitiva (TPP). Esto se asume ya que si no fueran coprimos, simplemente se divide toda la terna entre el MCD creando una terma primitiva.
* Usando la fórmula de Euclides para generar TPP’s, sabemos que: $x^2=a^2+b^2$ y que $y^2=a^2-b^2$ o $y^2=2ab.$
* Asumiendo que $y^2=a^2-b^2$ tenemos que $x^2(y^2)=a^4-b^4=(xy)^2.$ Notar que hemos encontrado entonces otra TPP (xy, $a^2,$ $b^2)$ menor que la original (z, $y^2,$ $x^2),$ creando un descenso infinito lo cual es imposible. Por lo tanto , $y^2≠a^2-b^2.$
* Asumiendo entonces que $y^2=2ab$ con a>b. Sin pérdida de generalidad, asumamos que a es par y b es impar. Tenemos lo siguiente:

    $x^2=a^2+b^2$
    $x=c^2+d^2$
    a=2cd
    $b=c^2-d^2$
    Con c>d y coprimos
    $y^2=2ab=2(2cd)(c^2-d^2)$
    y dividiendo ambos lados por 4 se tiene:
    $y^2/4=(cd)(c^2-d^2)=(y/2)^2$
* Nos podemos dar cuenta que el producto de c, d y $c^2–d^2$ es un cuadrado perfecto, por lo que cada uno de ellos es un cuadrado perfecto:

    $c^2=e^2$
    $d^2=f^2$
    $c^2–d^2=g^2$
* Remplazando c y d por e y f respectivamente en la última ecuación tenemos: $(e^2)^2-(f^2)^2=g^2=e^4-f^4$
* Hemos encontrado otra TPP (g, $f^2,$ $e^2)$ menor que la original (z, $y^2,$ $x^2),$ creando un descenso infinito, lo cual es imposible. Por lo tanto, podemos concluir afirmando que la ecuación Diofántica $z^4+y^4=x^4$ no tiene soluciones enteras. Q.E.D.

## Más Ejemplos

Otros ejemplos de problemas donde se utiliza la prueba por contradicción son los siguientes:

    1. Proposición.- Demuestre que $n^4$ + $4^n$ nunca es primo para n>1: Se divide el problema en 2 casos, para n par y para n impar. El primer caso es bastante obvio ya que ambos sumandos son múltiplos de 16, y por tanto se llega a una contradicción. El segundo caso es mucho más complejo y requiere un dominio en leyes de los exponentes y factorización. Al final, se llega a una factorización de $n^4$ + $4^n,$ siendo esto una contradicción.
    2. Teorema Cataldi-Fermat.- Si $2^n-1$ es primo, entonces n es primo: Se empieza asumiendo que n es compuesto y al ser compuesto $2^n-1$ se puede factorizar en 2 términos, ambos mayores que uno, por lo que se llega a una contradicción con la hipótesis.
    3. Proposición.- ¿Puede un número de 600 seises y algunos ceros ser un cuadrado?: En este problema se utiliza el método de descenso infinito junto con la aritmética modular para demostrar que no existe tal número.
