Demostración por reducción al absurdo

La demostración por reducción al absurdo es una técnica de demostración muy popular. Si queremos demostrar que se cumple cierta proposición, la negamos, suponemos que su negación es verdadera e intentamos llegar a una contradicción. El objetivo es demostrar que la hipótesis que hemos elegido conduce a un sinsentido.

Un ejemplo trivial

Tomemos el enunciado «no existe el menor número racional positivo». Lo demostraremos por reducción al absurdo: primero lo negamos, «existe el menor número racional positivo», y llamamos q a ese número. Si q es el menor número racional positivo, no podemos encontrar un número racional positivo más pequeño, porque entonces q no sería el menor.

Aprovecharemos esto para buscar la contradicción. Si a pesar de todo encontramos un número menor que q, que podemos elegir libremente, habremos llegado a una contradicción y el enunciado negado no se cumple. Si elegimos como menor número, por ejemplo, 0,1, vemos que 0,01 es menor. Además, 0,001 es todavía menor, 0,0001 es de nuevo menor y así sucesivamente. Basta dividir el número q entre diez para obtener un número menor. En realidad basta dividirlo entre cualquier número mayor que uno, por ejemplo entre dos: la mitad de q será sin duda menor que el número q entero.

Es decir, el número q/2 es sin duda menor que q y, a la vez, es un número racional positivo. Con ello hemos llegado a una contradicción con el enunciado negado; por tanto, el enunciado negado no se cumple y, en consecuencia, se cumple el enunciado original sin negar.

Los números interesantes

Un clásico ejemplo humorístico que ilustra el principio de la reducción al absurdo es el siguiente. Supongamos que existen números naturales que son interesantes de alguna manera. Por ejemplo, el número 2 es interesante porque se cumple que 2 · 2 = 2 + 2, una propiedad bastante atípica. El número 42 es interesante porque es la respuesta a todo. Y así sucesivamente. La pregunta es: ¿existen infinitos números interesantes?

Supongamos lo contrario, es decir, que solo existe una cantidad finita de números interesantes y que algunos números no son interesantes. Reunimos estos números naturales no interesantes en un conjunto de números no interesantes. Ahora elegimos el menor número no interesante. Un momento, ¿el menor número no interesante? Suena bastante interesante, ¿no? :-)

Con ello hemos llegado a una contradicción, porque el menor número no interesante es en realidad bastante interesante; por tanto, no puede existir el menor número no interesante y, en consecuencia, el conjunto de los números no interesantes tiene que ser necesariamente vacío.

Por supuesto, es un sinsentido: no hemos definido con rigor qué es un número interesante, pero el procedimiento de la demostración en sí es correcto.

Demostración de que hay infinitos números primos

En este ejemplo mostraremos un procedimiento parecido al del apartado anterior, pero esta vez será correcto en todos los sentidos.

Un número primo es un número divisible solo entre dos números distintos: entre sí mismo y entre uno. Fíjate en que el uno no cumple la definición y el dos sí.

La descomposición en factores primos, o factorización, es la descomposición de un número natural, salvo el uno, en un producto de números primos. Es una propiedad bastante interesante de los números naturales. Tomes el número natural que tomes (salvo el uno), se cumple que se puede descomponer en un producto de varios números primos (que pueden repetirse). Ejemplos:

$\begin{array}{rcl} 8 & = & 2 \cdot 2 \cdot 2 \\ 15 & = & 3 \cdot 5 \\ 26 & = & 2 \cdot 13 \\ 1800 & = & 2^{3} \cdot 3^{2} \cdot 5^{2} \end{array}$

El enunciado sobre la descomposición en factores primos se llama teorema fundamental de la aritmética. Entre otras cosas, nos dice que tal descomposición es única, es decir, que no encontraremos dos descomposiciones en factores primos distintas de un mismo número natural. Además, solo los números primos tienen una descomposición formada por un único número: ellos mismos. Es decir, la descomposición en factores primos del siete sería el número siete. Utilizaremos estos hechos al construir la demostración del siguiente enunciado.

Ahora demostraremos el enunciado «hay infinitos números primos». De nuevo negamos el enunciado: «hay una cantidad finita de números primos». Supongamos que la sucesión de números

$a_{1}, a_{2}, a_{3}, \dots, a_{n}$

representa todos los números primos que existen. Si en esta sucesión están todos los números primos, entonces seguro que ya no podremos encontrar un número que sea primo y que a la vez no esté en esta sucesión. Tenemos todos los números primos en la sucesión; fuera de ella no puede aparecer ningún número primo más.

Si queremos llegar a una contradicción, debemos construir un número primo que no esté en esta sucesión. Para ello nos ayudará el número q, que construimos multiplicando todos los números primos de la sucesión y sumando uno:

$q = a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n} + 1$

Ahora tenemos que mostrar que este número o bien es primo, o bien genera de algún modo un número primo. Sabemos que q es un número natural y que todo número natural se puede expresar como un producto de números primos. Sin embargo, ningún número primo a_i divide exactamente a q: al dividir siempre sobra uno. Si intentáramos dividir q, por ejemplo, entre el número primo a₂, obtendríamos lo siguiente:

$\frac{a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n} + 1}{a_{2}} = \frac{a_{1} \cdot a_{2} \cdot a_{3} \cdot \dots \cdot a_{n}}{a_{2}} + \frac{1}{a_{2}} =$

$= a_{1} \cdot a_{3} \cdot a_{4} \cdot \dots \cdot a_{n} + \frac{1}{a_{2}}$

Primero descomponemos la fracción en dos. En la primera fracción simplificamos a₂ y nos queda un producto de números primos, que es simplemente otro número entero sin importancia. En la segunda fracción no hay nada que simplificar; esta fracción será siempre un número no entero (porque el denominador no puede ser uno, ya que el uno no es primo). En la suma obtenemos, por tanto, un número que no es entero; es decir, el número primo a₂ no divide al número q.

Con ello hemos demostrado que ninguno de los números primos de la sucesión a_n divide al número q. (Nota: lo hemos mostrado solo para a₂, pero se puede generalizar fácilmente si sustituimos a₂ por un a_i general.) Pero como todo número natural se puede descomponer en un producto de números primos, tienen que existir otros números primos que no están en la sucesión a_n, pero que forman la factorización del número q. Incluso el propio número q puede ser primo, y entonces la descomposición en factores primos incluirá solo al número q. Así que repasemos una vez más todo el razonamiento:

Todo número natural se puede expresar como un producto de números primos.
Por hipótesis, la sucesión a_n contiene todos los números primos que existen.
Modificamos el primer enunciado: todo número natural se puede expresar como un producto de términos escogidos de la sucesión a_n, porque esta contiene todos los números primos.
Hemos demostrado que ningún número de la sucesión a_n divide al número q.
Así surge una contradicción con la hipótesis → si tenemos que ser capaces de descomponer todo número natural en un producto de números primos y la sucesión a_n no contiene ningún número que divida a q, entonces tienen que existir otros números primos que dividen a q y que forman la descomposición en factores primos del número q.

Con esto hemos llegado a una contradicción. La descomposición en factores primos del número q incluye números primos que no están contenidos en la sucesión que suponíamos que contenía todos los números primos. Por tanto, no se cumple el enunciado negado y se cumple el enunciado original sin negar. Hay infinitos números primos.

Capítulos: Qué es una demostración, Demostración por reducción al absurdo, Inducción matemática

« Anterior: Demostraciones

Siguiente: Inducción matemática »