La demostración por contradicción supone temporalmente que la afirmación buscada es falsa. Si esa suposición obliga a aceptar una imposibilidad, la afirmación original debe ser verdadera.
Hay afirmaciones cuya prueba directa resulta poco natural. En esos casos podemos adoptar una estrategia indirecta: suponer que lo que queremos demostrar no es cierto y estudiar las consecuencias lógicas de esa suposición.
Si las consecuencias incluyen una contradicción —por ejemplo, que un número sea simultáneamente par e impar, o que un valor sea menor y mayor que otro bajo las mismas condiciones— la suposición inicial no puede ser verdadera. Por lo tanto, la afirmación original se mantiene.
Una contradicción es una proposición de la forma R y ¬R. En la lógica clásica, una contradicción no puede ser verdadera. Por eso, si una hipótesis H conduce necesariamente a una contradicción, concluimos que ¬H.
| Tipo | Ejemplo |
|---|---|
| Propiedad y su negación | n es par y n es impar. |
| Desigualdades incompatibles | x < 4 y x ≥ 4. |
| Violación de una definición | Un máximo que tiene un elemento mayor. |
| Violación de una hipótesis conocida | Un arreglo declarado ordenado contiene a[i] > a[i + 1]. |
| Resultado imposible | Un entero positivo estrictamente menor que 1. |
La contradicción debe ser genuina y debe derivarse mediante pasos válidos. No basta con llegar a un resultado sorprendente o poco intuitivo.
Ambas técnicas son indirectas, pero no son iguales. En contraposición, para demostrar P → Q se demuestra ¬Q → ¬P. En contradicción se supone la negación de lo que se quiere probar y se busca un absurdo.
| Método | Suposición inicial | Objetivo intermedio |
|---|---|---|
| Contraposición | ¬Q | Derivar ¬P. |
| Contradicción | ¬P, si se busca probar P | Derivar una imposibilidad. |
En algunos problemas se pueden usar ambas. Elegiremos la que produzca una cadena de razonamiento más transparente.
Demostraremos que no existe un entero que sea mayor o igual que todos los enteros.
La prueba usa una propiedad estructural de los enteros: siempre podemos sumar uno y obtener otro entero mayor.
El código ilustra la idea para un valor concreto. Ningún programa puede enumerar todos los enteros, pero puede mostrar cómo construir uno mayor a partir de cualquiera dado.
function enteroMayor(n) {
return n + 1;
}
const candidato = 1000;
console.log(`Candidato: ${candidato}`);
console.log(`Entero mayor: ${enteroMayor(candidato)}`); // 1001Este es un ejemplo clásico de contradicción. Una versión completa requiere algunos resultados previos sobre fracciones irreducibles y paridad. Demostraremos que no puede escribirse √2 como cociente de dos enteros.
La potencia de esta prueba no está en calcular decimales de √2, sino en demostrar que ninguna fracción de enteros puede representarla exactamente.
La contradicción también sirve para probar imposibilidades dentro de un dominio. Por ejemplo, no existe un número entero x que satisfaga simultáneamente x > 3 y x < 4.
El dominio importa: entre 3 y 4 sí existen números reales, como 3,5. La contradicción depende de que x sea entero.
Muchas demostraciones deben establecer que un objeto existe y que es único. La contradicción suele ayudar con la unicidad: suponemos que hay dos objetos distintos que cumplen la misma propiedad y mostramos que necesariamente son iguales.
Por ejemplo, un arreglo no vacío tiene un único valor máximo como número, aunque ese valor pueda aparecer en más de una posición. Si dos valores m y M fueran ambos máximos, entonces m ≥ M y M ≥ m; por lo tanto m = M.
La técnica es muy útil para propiedades de grafos. Para demostrar que un árbol no contiene ciclos, podemos usar la definición de árbol como grafo conexo con un único camino simple entre cada par de vértices.
Supongamos que un árbol contiene un ciclo. Tomemos dos vértices distintos del ciclo. Podemos ir de uno al otro siguiendo el ciclo por un lado o por el otro, obteniendo dos caminos simples diferentes. Esto contradice la unicidad del camino en un árbol.
La búsqueda binaria sobre un arreglo ordenado descarta la mitad de los elementos en cada paso. Para justificar que puede descartar una mitad, usamos una idea de contradicción.
Si el elemento buscado es menor que el elemento central, supongamos que aparece en la mitad derecha. Como el arreglo está ordenado, todos los elementos de esa mitad son mayores o iguales que el central, y por lo tanto mayores que el buscado. Eso contradice que allí aparezca el buscado.
function busquedaBinaria(numeros, buscado) {
let izquierda = 0;
let derecha = numeros.length - 1;
while (izquierda <= derecha) {
const centro = Math.floor((izquierda + derecha) / 2);
if (numeros[centro] === buscado) return centro;
if (buscado < numeros[centro]) derecha = centro - 1;
else izquierda = centro + 1;
}
return -1;
}
const numeros = [3, 7, 11, 15, 21, 28, 35];
console.log(busquedaBinaria(numeros, 21)); // 4
console.log(busquedaBinaria(numeros, 18)); // -1El algoritmo solo es correcto bajo la precondición de que el arreglo esté ordenado. Sin esa condición, el razonamiento que descarta una mitad deja de ser válido.
Los programas robustos verifican que no se alcancen estados imposibles. Si una variable representa un mes, su valor debe estar entre 1 y 12. Si llegamos a un valor fuera de ese rango, algo contradice la especificación del sistema.
function nombreDelMes(mes) {
const meses = ["enero", "febrero", "marzo", "abril", "mayo", "junio",
"julio", "agosto", "septiembre", "octubre", "noviembre", "diciembre"];
if (!Number.isInteger(mes) || mes < 1 || mes > 12) {
return "mes inválido";
}
return meses[mes - 1];
}
console.log(nombreDelMes(4)); // abril
console.log(nombreDelMes(13)); // mes inválidoUna validación no es una demostración formal por sí sola, pero expresa en código las restricciones que la prueba debe respetar.
En lógica clásica, a partir de una contradicción puede derivarse cualquier proposición. Este hecho, llamado principio de explosión, explica por qué una teoría con contradicciones no puede usarse de manera confiable: si aceptamos a la vez P y ¬P, perdemos la capacidad de distinguir conclusiones válidas de inválidas.
En ingeniería de software hay una analogía práctica: si las invariantes internas de un programa se rompen, los resultados posteriores pueden dejar de tener significado. Por eso es importante validar entradas y detectar estados imposibles cuanto antes.
La frase «para obtener una contradicción» aclara que la suposición es temporal. La conclusión debe señalar explícitamente cuál fue la incompatibilidad obtenida.
| Tipo de afirmación | Utilidad de contradicción |
|---|---|
| No existe un objeto con cierta propiedad | Muy alta: suponer que existe suele generar un conflicto. |
| Un objeto es único | Alta: asumir dos objetos distintos puede forzar igualdad. |
| Propiedad de una estructura | Alta: una configuración prohibida contradice una definición. |
| Propiedad algebraica simple | A menudo innecesaria: la prueba directa puede ser mejor. |
| Implicación con una negación sencilla | Evaluar también contraposición. |
La contradicción es una técnica poderosa porque convierte una afirmación difícil en el análisis de las consecuencias de negarla. Cuando esa negación destruye una propiedad conocida o fuerza una imposibilidad, la afirmación queda demostrada.
En el próximo tema estudiaremos la inducción matemática, el método fundamental para demostrar propiedades que dependen de todos los números naturales.