No existe un número par mayor que todos

Demuestra que no existe un número par mayor que todos los demás.

Escribe la negación como primera línea: Supongamos, por reducción al absurdo, que existe un número par mayor que todos, $N$ = Suposición: $N$ es par y $N \ge$ cualquier número par

Usa la definición de par: $N = 2k$ para algún entero $k$, así que $N + 2 = 2k + 2 = 2(k + 1)$ = $N + 2$ es par

Compara los dos números: $N + 2 > N$ = Existe un número par mayor que $N$

Localiza la contradicción y concluye: $N$ es el mayor número par, pero $N + 2$ es un número par mayor = La suposición es falsa

Answer: La suposición lleva a una contradicción, así que no existe un número par mayor que todos. c. q. d.

De 13 personas, dos nacieron el mismo mes

Demuestra que en cualquier grupo de 13 personas, al menos dos nacieron el mismo mes.

Escribe la negación: Supongamos, por reducción al absurdo, que las 13 personas nacieron en meses distintos = Suposición: 13 meses distintos

Cuenta lo que exige la suposición: 13 personas sin ningún mes repetido necesitan al menos 13 meses distintos = Hacen falta al menos $13$ meses

Compara con los hechos: Un año solo tiene $12$ meses, y $13 > 12$ = Imposible

Concluye: La suposición es falsa = Dos personas comparten mes

Answer: Al menos dos de las 13 personas nacieron el mismo mes. Es el principio del palomar: 13 palomas, 12 nidos. c. q. d.

No existe un número racional positivo menor que todos

Demuestra que no existe un número racional positivo menor que todos los demás.

Escribe la negación: Supongamos, por reducción al absurdo, que $r$ es el menor número racional positivo = Suposición: $r > 0$, $r$ racional, ninguno es menor

Construye un número nuevo: Si $r = \frac{a}{b}$, entonces $\frac{r}{2} = \frac{a}{2b}$, una fracción de enteros = $\frac{r}{2}$ es racional

Comprueba su tamaño: $r > 0$, así que $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ es positivo y menor que $r$

Localiza la contradicción y concluye: $r$ era el menor, pero $\frac{r}{2}$ es menor = La suposición es falsa

Answer: No existe un número racional positivo menor que todos. Por ejemplo, si alguien propone $\frac{1}{1000}$, entonces $\frac{1}{2000}$ es menor. c. q. d.

La raíz cuadrada de 2 es irracional

Demuestra que $\sqrt{2}$ es irracional.

Escribe la negación: Supongamos, por reducción al absurdo, que $\sqrt{2}$ es racional: $\sqrt{2} = \frac{a}{b}$ con $a, b$ enteros, $b \neq 0$, y la fracción irreducible = $a$ y $b$ no tienen ningún factor común

Eleva ambos miembros al cuadrado: $2 = \frac{a^2}{b^2}$, así que $a^2 = 2b^2$ = $a^2$ es par

Deduce que a es par: Si $a$ fuera impar, $a^2$ sería impar (demostrado en la lección de demostración directa) = $a = 2k$ para algún entero $k$

Sustituye: $(2k)^2 = 2b^2$, así que $4k^2 = 2b^2$, así que $b^2 = 2k^2$ = $b^2$ es par, así que $b$ es par

Localiza la contradicción: $a$ y $b$ son ambos pares, así que ambos son divisibles entre $2$ = Esto contradice "irreducible"

Answer: La suposición de que $\sqrt{2}$ es racional lleva a una contradicción, así que $\sqrt{2}$ es irracional. c. q. d.

Hay infinitos números primos (Euclides)

Demuestra que hay infinitos números primos.

Escribe la negación: Supongamos, por reducción al absurdo, que solo hay una cantidad finita de primos: $p_1, p_2, \ldots, p_n$ = La lista contiene todos los primos

Construye un número nuevo: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Divide N entre cada primo de la lista: $N$ es uno más que un múltiplo de cada $p_i$ = El resto siempre es $1$, así que ningún $p_i$ divide a $N$

Usa un hecho conocido: Todo entero mayor que $1$ tiene al menos un factor primo = $N$ tiene un factor primo que no está en la lista

Localiza la contradicción: Se suponía que la lista contenía todos los primos = La suposición es falsa

Answer: Hay infinitos números primos. Cuidado: $N$ no tiene por qué ser primo. Con los primos hasta 13, $N = 30031 = 59 \times 509$, y 59 y 509 son primos que faltan en la lista. c. q. d.

Mistake: Negar "Hay infinitos números primos" como "No hay números primos"

Why: Lo contrario de "infinitos" no es "ninguno". La negación debe cubrir todos los casos en los que el enunciado falla, y eso es "solo una cantidad finita".

Correct: Supón "Solo hay una cantidad finita de números primos". Del mismo modo, la negación de "todo primo es impar" es "al menos un primo no es impar", no "todo primo es par".

Mistake: Negar $x > 5$ como $x < 5$

Why: Se olvida el caso $x = 5$. Si la demostración solo descarta $x < 5$, el número $5$ sigue siendo posible.

Correct: La negación de $x > 5$ es $x \le 5$, y la negación de $x \ge 5$ es $x < 5$.

Mistake: Olvidar "irreducible" en la demostración de que $\sqrt{2}$ es irracional

Why: Sin esa condición, descubrir que $a$ y $b$ son ambos pares no es ninguna contradicción: $\frac{4}{2}$ tiene numerador y denominador pares.

Correct: Escribe $\sqrt{2} = \frac{a}{b}$ como fracción irreducible. Toda fracción se puede simplificar, así que no cuesta nada, y es justo el hecho que la demostración rompe después.

Mistake: Llamar contradicción a un resultado sorprendente

Why: Un resultado que parece raro (un número muy grande, una fracción inesperada) no es imposible. Una contradicción tiene que chocar con la suposición o con un hecho conocido.

Correct: Nombra los dos enunciados que chocan, por ejemplo "$r$ es el menor" y "$\frac{r}{2} < r$", y después escribe la conclusión.

Calcetines iguales a oscuras

El principio del palomar, demostrado por reducción al absurdo, te dice el menor número de objetos que garantiza una repetición.

Un cajón tiene calcetines negros, blancos y grises. Si pudieras sacar 4 calcetines todos de colores distintos, necesitarías 4 colores, pero solo hay 3. Así que 4 calcetines siempre contienen una pareja del mismo color.

Colisiones de hash en informática

Los ordenadores asignan a los archivos códigos cortos llamados hashes. Como hay más archivos posibles que códigos, a veces dos archivos distintos tienen que compartir código.

Un sistema asigna a cada archivo un código del 00 al 99. Con 101 archivos, suponer que todos los códigos son distintos exigiría 101 códigos, pero solo hay 100, así que dos archivos comparten código.

Por qué la calculadora nunca muestra la raíz de 2 exacta

Como $\sqrt{2}$ es irracional, su expresión decimal nunca termina ni se repite. Cualquier decimal en la pantalla es solo una aproximación, algo que los ingenieros deben tener en cuenta al calcular diagonales.

Una baldosa cuadrada de 1 m de lado tiene una diagonal de $\sqrt{2} \approx 1{,}4142$ m. El valor 1,4142 se acerca, pero no es exacto.

Q: ¿Por qué basta con llegar a una contradicción?

A: Un razonamiento correcto a partir de enunciados verdaderos solo produce enunciados verdaderos. Si llegamos a algo imposible, al menos un punto de partida era falso, y el único punto de partida que añadimos nosotros fue la suposición $\neg P$. Así que $\neg P$ es falso y $P$ es verdadero.

Q: ¿Cuándo debo usar la reducción al absurdo?

A: Es una buena elección cuando el enunciado dice que algo no existe (ningún número mayor que todos, ninguna fracción igual a $\sqrt{2}$) o que hay infinitos de algo. En esos casos, suponer lo contrario te da un objeto concreto con el que trabajar.

Q: ¿Es la reducción al absurdo lo mismo que la demostración por contrarrecíproca?

A: No. La demostración por contrarrecíproca prueba directamente "si no q, entonces no p" y termina en "no p". La reducción al absurdo supone que el enunciado es falso y puede terminar en cualquier imposibilidad. Toda demostración por contrarrecíproca se puede reescribir como reducción al absurdo, pero no toda reducción al absurdo es una demostración por contrarrecíproca.

Q: ¿Qué significa c. q. d. y qué es "reductio ad absurdum"?

A: c. q. d. ("como queríamos demostrar", en latín quod erat demonstrandum) marca el final de una demostración. Reductio ad absurdum, "reducción al absurdo", es el nombre latino de este método.