Todo subconjunto no vacío de los números naturales tiene un elemento mínimo. Esta propiedad, aparentemente simple, permite demostrar resultados mediante el contraejemplo más pequeño y fundamenta la inducción matemática.
Los números naturales tienen una propiedad especial: cualquier colección no vacía de naturales posee un menor elemento. Esta afirmación se denomina principio del buen orden y es una de las bases lógicas de la matemática discreta.
El principio permite atacar una afirmación universal de forma indirecta. Si pensamos que hay casos para los que la propiedad falla, podemos tomar el menor de esos casos. Luego mostramos que su existencia contradice las propiedades de los casos anteriores.
El elemento mínimo debe pertenecer al conjunto. Esto lo diferencia de una cota inferior: por ejemplo, 0 es una cota inferior de {1, 2, 3, ...}, pero el mínimo de ese conjunto es 1 porque 1 pertenece a él.
| Conjunto de naturales | ¿No vacío? | Mínimo |
|---|---|---|
| {4, 9, 15, 20} | Sí | 4 |
| {n ∈ N | n ≥ 100} | Sí | 100 |
| {n ∈ N | n es múltiplo de 7 y n > 0} | Sí | 7 |
| ∅ | No | No tiene mínimo |
La condición «no vacío» es indispensable. No puede existir un elemento que pertenezca al conjunto vacío, por lo que ese conjunto no tiene mínimo.
Los naturales están ordenados de manera que no podemos descender indefinidamente. En cambio, los enteros no satisfacen el buen orden usual: el conjunto de todos los enteros no tiene mínimo porque, para cualquier entero z, existe z - 1, que es menor.
También los números reales con su orden usual fallan esta propiedad. El intervalo abierto (0, 1) no tiene mínimo: si elegimos un real positivo x, entonces x/2 también pertenece al intervalo y es menor.
En programación se usa la palabra «mínimo» en varios sentidos. En una lista finita, el mínimo es el menor valor almacenado. En un grafo o una función pueden aparecer mínimos locales. El principio del buen orden se refiere específicamente al mínimo global de un subconjunto no vacío de naturales.
function minimo(numeros) {
if (numeros.length === 0) {
throw new Error("El arreglo no puede estar vacío");
}
return numeros.reduce((menor, numero) => Math.min(menor, numero));
}
console.log(minimo([12, 4, 19, 7])); // 4El código encuentra un mínimo en un conjunto finito representado por un arreglo. El principio del buen orden afirma algo más general: incluso un conjunto infinito de naturales, si no está vacío, tiene mínimo.
Para demostrar que una propiedad P(n) vale para todo natural n a partir de cierto punto, suponemos lo contrario: existe al menos un contraejemplo. Entonces el conjunto C de todos los contraejemplos no es vacío y, por el buen orden, tiene un menor elemento m.
Esta técnica suele producir demostraciones muy naturales cuando la propiedad de un número depende de propiedades de números menores.
Demostraremos que todo entero n > 1 tiene al menos un divisor primo.
Supongamos que existen enteros mayores que 1 sin divisor primo. Sea m el menor de ellos. El número m no puede ser primo, porque entonces m sería divisor primo de sí mismo. Por lo tanto m es compuesto.
El algoritmo recorre posibles divisores desde el menor hacia arriba. Si encuentra uno, necesariamente es el menor divisor mayor que 1; además, ese divisor debe ser primo.
function menorDivisorPrimo(n) {
if (!Number.isInteger(n) || n <= 1) {
throw new Error("n debe ser un entero mayor que 1");
}
for (let divisor = 2; divisor <= n; divisor++) {
if (n % divisor === 0) return divisor;
}
}
console.log(menorDivisorPrimo(91)); // 7
console.log(menorDivisorPrimo(97)); // 97La idea de recorrer de menor a mayor es una aplicación concreta del orden sobre los naturales. En la práctica se puede optimizar el límite de búsqueda, pero la propiedad lógica se mantiene.
Podemos demostrar que todo entero n ≥ 2 es producto de primos usando el mismo razonamiento. Supongamos que hay enteros que no admiten factorización prima y sea m el menor.
Esta prueba es equivalente en espíritu a la inducción fuerte del tema anterior. En lugar de suponer correctos todos los casos menores, toma el menor caso que supuestamente falla.
El principio del buen orden, la inducción simple y la inducción fuerte son equivalentes: cada uno puede demostrarse a partir de cualquiera de los otros. Son diferentes formas de expresar la estructura de los naturales.
| Herramienta | Idea central |
|---|---|
| Inducción simple | Un caso correcto implica el siguiente. |
| Inducción fuerte | Todos los casos anteriores implican el siguiente. |
| Buen orden | Si hay contraejemplos, existe uno mínimo. |
La elección es una cuestión de claridad. Si el problema habla naturalmente de «el menor que falla», el buen orden suele ser la mejor presentación.
El buen orden permite razonar sobre terminación. Si en cada paso de un algoritmo una medida natural no negativa disminuye estrictamente, el algoritmo no puede continuar para siempre. De lo contrario existiría una sucesión infinita de naturales cada vez menores.
Esta medida se llama a veces función variante. Es un complemento del invariante: el invariante ayuda a probar corrección; la variante ayuda a probar terminación.
En el algoritmo de Euclides, mientras el segundo valor b sea distinto de cero, se reemplaza por el resto de dividir a entre b. Ese resto satisface 0 ≤ resto < b. Por lo tanto, la medida b disminuye y permanece como natural no negativo.
function mcdConPasos(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
console.log(`a = ${a}, b = ${b}`);
[a, b] = [b, a % b];
}
console.log(`MCD = ${a}`);
return a;
}
mcdConPasos(252, 105); // MCD = 21El algoritmo termina porque no puede existir una cadena infinita de restos naturales positivos estrictamente decrecientes.
El razonamiento por mínimo contraejemplo también es útil al depurar. Si una propiedad debería cumplirse para todas las entradas de tamaño n, podemos buscar la entrada más pequeña que produce un fallo. Su tamaño reducido suele revelar el caso límite omitido.
Por ejemplo, si una función que ordena arreglos falla, el menor arreglo que falla puede tener longitud 0, 1, 2 o 3. Examinar ese caso es más informativo que observar un conjunto de datos enorme.
El programa siguiente busca el primer valor para el que una conjetura incorrecta falla. La conjetura es «n² + n + 41 siempre es primo». Funciona para muchos valores iniciales, pero no para todos.
function esPrimo(n) {
if (n < 2) return false;
for (let d = 2; d * d <= n; d++) {
if (n % d === 0) return false;
}
return true;
}
function primerContraejemplo(limite) {
for (let n = 0; n <= limite; n++) {
if (!esPrimo(n * n + n + 41)) return n;
}
return null;
}
console.log(primerContraejemplo(100)); // 40Para n = 40 se obtiene 41² = 1681, que no es primo. Un solo contraejemplo refuta una afirmación universal; el menor de ellos ayuda a comprender dónde deja de funcionar una regla propuesta.
Una colección finita de enteros tiene mínimo siempre que no esté vacía. Esto puede verse como un caso particular del buen orden. En algoritmos aparecen operaciones como «extraer el menor», por ejemplo en colas de prioridad y en el algoritmo de Dijkstra.
En un conjunto finito puede ser sencillo recorrer todos los elementos. En problemas grandes, las estructuras de datos permiten mantener el mínimo sin volver a buscarlo desde cero.
El principio no dice que todo conjunto tenga mínimo. Requiere trabajar con un subconjunto no vacío de naturales, o con otra estructura que esté bien ordenada. Aplicarlo fuera de ese contexto puede producir conclusiones falsas.
| Conjunto | ¿Tiene mínimo con el orden usual? | Motivo |
|---|---|---|
| Números naturales positivos | Sí, 1 | Están bien ordenados. |
| Todos los enteros | No | Se puede descender indefinidamente. |
| Reales en (0, 1) | No | Para cada x existe x/2 menor. |
| Reales en [0, 1] | Sí, 0 | 0 pertenece al conjunto. |
El principio del buen orden convierte la idea de «el primer caso que falla» en una herramienta rigurosa. Al no poder existir una sucesión infinita de naturales cada vez menores, podemos justificar demostraciones y algoritmos que progresan hacia un caso base.
En el próximo tema estudiaremos sucesiones discretas, listas ordenadas de términos que permiten describir cambios y patrones dependientes de un índice.