Demostración: cómo lo sabes, no cuán probable es

Los conjuntos, el álgebra booleana y la notación Big-O se apoyan en un paso que hasta ahora has dado en silencio: comprobar unos cuantos casos y decidir que el patrón se mantiene. Con un conjunto de dos elementos está bien, porque lo ves todo. Con una afirmación sobre todos los números enteros no lo está, y toda la diferencia entre un profesional y un principiante se esconde en ese hueco. Una demostración no es una prueba más fuerte. Es un objeto de otra clase: un razonamiento finito que cubre infinitos casos a la vez.

Primero lee la afirmación con cuidado, porque la mayoría de las malas demostraciones atacan una frase distinta de la que está en la pizarra. Una afirmación del tipo para todo entero n no tiene excepciones por definición, y una del tipo existe un n te pide que presentes un testigo. Son estrategias opuestas. La afirmación de abajo tiene un aspecto excelente. Ejecútala y se mantiene durante cuarenta valores consecutivos, mucho mejor que la mayoría de los patrones en los que has confiado.

claim: for every integer n >= 1,  n^2 + n + 41  is prime

n = 1    43         prime
n = 2    47         prime
n = 3    53         prime
n = 4    61         prime
n = 5    71         prime
n = 10   151        prime
n = 20   461        prime
n = 39   1601       prime
n = 40   1681 = 41 * 41   composite

confirmed: 39 cases before that one

En n = 40 el valor se descompone en un producto. Ese único caso es una refutación completa y definitiva, y cuesta una línea. Esta asimetría es lo más útil de toda la lección: para demostrar una afirmación universal hay que razonar sobre todos los casos a la vez, pero para destruirla basta exactamente uno. Fíjate también en cuánto valían los cuarenta aciertos: nada. No eran pruebas débiles a favor de la afirmación, no eran prueba alguna, porque la afirmación ya era falsa todo el tiempo. Cuando busques un contraejemplo, busca en los bordes: n = 0, n = 1, números negativos, la lista vacía, el valor más grande que admite tu tipo. La mayoría de las afirmaciones universales falsas sobre código mueren en un caso límite, no en el centro.

Una demostración directa es la de siempre: partir de las definiciones y llegar a la afirmación sin dar por sentado nada que no hayas establecido. Cuando el razonamiento funciona de forma distinta en situaciones distintas, divídelo en casos y asegúrate de que los casos lo cubren todo. La afirmación de abajo tiene una demostración de dos líneas, pero solo es una demostración porque la última línea afirma que todo entero cae en uno de los dos casos. Sin esa frase has mostrado dos ejemplos, no un teorema.

claim: for every integer n,  n^2 + n  is even

n^2 + n  =  n * (n + 1)

case A:  n = 2k       ->  n * (n + 1) = 2 * k * (n + 1)
case B:  n + 1 = 2k   ->  n * (n + 1) = 2 * k * n

int(n) = A union B

La demostración por contradicción sirve para afirmaciones difíciles de atacar de frente, normalmente para decir que algo no existe. Supones lo contrario y sigues las consecuencias hasta que dos hechos no puedan ser verdaderos a la vez. El ejemplo clásico está abajo. Cada paso es álgebra corriente más un hecho aritmético: si el cuadrado de a es par, entonces a es par. La contradicción no es que ocurra algo sorprendente, sino que el resultado ataca la suposición con la que empezaste: que a y b no tenían factor común.

claim: no integers a, b with  sqrt(2) = a / b

assume integers a, b exist, gcd(a, b) = 1

  a / b   = sqrt(2)
  a^2     = 2 * b^2
  a^2 even              ->  a = 2k
  4 * k^2 = 2 * b^2
  b^2     = 2 * k^2     ->  b = 2m
  gcd(a, b) >= 2  ->  contradicts gcd(a, b) = 1

assumption false

Justo aquí mueren la mayoría de las demostraciones por contradicción fallidas, y merece la pena ponerle nombre al callejón sin salida para que lo reconozcas. Si tu suposición era floja, la contradicción a la que llegas puede mostrar solo que la suposición era incómoda, no que fuera falsa. Suponiendo una fracción con factor común no habrías llegado a contradicción alguna. El remedio nunca es apretar más el álgebra, sino volver atrás y suponer la versión más fuerte y concreta de lo contrario. Una demostración por contradicción vale exactamente lo que vale la suposición que mata.

¿Cuánto vale entonces una prueba? Muchísimo, pero no es una demostración y no se convierte en una por añadir más pruebas. La evidencia sube la confianza; una demostración cierra la pregunta. La ingeniería real necesita ambas, y confundirlas es la razón de que se desplieguen sistemas con una afirmación que nadie comprobó de verdad. La postura honesta es estrecha y útil: mi demostración muestra que el algoritmo devuelve un arreglo ordenado, y mis pruebas muestran que termina dentro de la memoria que tenemos. Ninguna de las dos frases se hace pasar por la otra.