Un retículo es un orden parcial en el que cualquier par de elementos tiene una mejor cota inferior y una mejor cota superior. Esta estructura unifica operaciones tan conocidas como intersección y unión de conjuntos, o mcd y mcm de enteros.
Los órdenes parciales permiten que algunos elementos sean incomparables. Los retículos agregan una garantía muy útil: para dos elementos cualesquiera existe una forma canónica de combinarlos «hacia abajo» y otra «hacia arriba» dentro del orden.
Estas dos operaciones aparecen en conjuntos, permisos, jerarquías de tipos, análisis de programas y sistemas distribuidos. Aunque el nombre inglés lattice suele traducirse como retículo, no se refiere aquí a una matriz de puntos geométrica.
Un orden parcial es una relación reflexiva, antisimétrica y transitiva. Se suele escribir a ≤ b, aunque el símbolo representa una relación general, no necesariamente el orden numérico.
Un retículo parte de un conjunto con orden parcial. Si la relación no es un orden parcial, las nociones de cota inferior y superior no describen la estructura buscada.
Sea S un subconjunto de un conjunto parcialmente ordenado P. Un elemento u de P es una cota superior de S si cada elemento de S es menor o igual que u.
Una colección puede tener varias cotas superiores o ninguna. La cota superior más pequeña, si existe, recibe un nombre especial: supremo o mínimo común superior.
Un elemento l de P es una cota inferior de S si l es menor o igual que cada elemento de S.
La cota inferior más grande, si existe, se llama ínfimo o máximo común inferior. Las palabras «superior» e «inferior» se interpretan siempre respecto del orden elegido.
El supremo de S, denotado sup S, es la menor de todas sus cotas superiores. El ínfimo, denotado inf S, es la mayor de todas sus cotas inferiores.
«Menor» y «mayor» no significan necesariamente cantidad de elementos. En el orden por inclusión, un conjunto es menor cuando está contenido en el otro.
Un mínimo de un subconjunto S es un elemento que es menor o igual que todos los elementos de S. Un elemento minimal solo no tiene otro elemento estrictamente menor dentro de S.
El ínfimo es una cota inferior máxima y no debe confundirse con un elemento minimal de S. Esta distinción es esencial al leer diagramas de Hasse.
En un retículo, para dos elementos a y b, el ínfimo se llama encuentro y se denota a ∧ b. El supremo se llama unión o join y se denota a ∨ b.
En conjuntos, ∧ se convierte en intersección y ∨ en unión. En divisibilidad, se convierten en mcd y mcm. El mismo lenguaje describe ambas situaciones.
Un conjunto parcialmente ordenado P es un retículo si para todo par a, b de P existen a ∧ b y a ∨ b.
La definición solo exige operaciones para pares. En un retículo finito, esta condición permite obtener ínfimos y supremos de cualquier subconjunto finito no vacío repitiendo las operaciones binarias.
El conjunto de todos los subconjuntos de un conjunto U, llamado conjunto potencia y escrito P(U), ordenado por inclusión, es un retículo.
La intersección siempre está contenida en ambos conjuntos y es la mayor con esa propiedad. La unión siempre contiene a ambos y es la menor con esa propiedad.
Consideremos los divisores positivos de 12 ordenados por divisibilidad: {1, 2, 3, 4, 6, 12}. Este conjunto forma un retículo.
Al restringirnos a los divisores de 12, tanto el mcd como el mcm de dos elementos vuelven a pertenecer al conjunto. Esta clausura es parte de lo que hace funcionar el ejemplo.
El orden por divisibilidad de los divisores de 12 puede describirse por niveles:
Por ejemplo, 1 está por debajo de 12, pero no hace falta dibujar una arista directa porque existen cadenas intermedias. El encuentro de 4 y 6 se ubica hacia abajo; su unión, hacia arriba.
En los enteros positivos ordenados por divisibilidad, el encuentro de a y b es mcd(a, b), y la unión es mcm(a, b).
El mcd es el mayor divisor común según el orden usual de enteros, pero desde la perspectiva de divisibilidad es la mayor cota inferior. El mcm es la menor cota superior en ese mismo orden.
function mcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) [a, b] = [b, a % b];
return a;
}
function mcm(a, b) {
if (a === 0 || b === 0) return 0;
return Math.abs((a / mcd(a, b)) * b);
}
console.log({ encuentro: mcd(18, 24), union: mcm(18, 24) });
// { encuentro: 6, union: 72 }La función mcm divide antes de multiplicar para reducir el riesgo de desbordamiento. Para enteros mayores que el rango seguro de JavaScript debe emplearse una variante con BigInt.
Si representamos conjuntos finitos con Set, la intersección y la unión implementan directamente ∧ y ∨ del retículo de subconjuntos.
function interseccion(a, b) {
return new Set([...a].filter(valor => b.has(valor)));
}
function union(a, b) {
return new Set([...a, ...b]);
}
const a = new Set([1, 2]);
const b = new Set([2, 3]);
console.log([...interseccion(a, b)]); // [2]
console.log([...union(a, b)]); // [1, 2, 3]Como los conjuntos no tienen orden inherente, los arreglos resultantes se muestran solo para inspección. Lo importante es la pertenencia, no la posición de los valores.
Las operaciones ∧ y ∨ satisfacen leyes que recuerdan a la unión e intersección de conjuntos:
Estas leyes permiten tratar muchas expresiones sin referirse cada vez al diagrama de orden. Además, caracterizan algebraicamente a los retículos: una estructura con dos operaciones que las cumple puede interpretarse mediante un orden parcial.
Un retículo es acotado si tiene un elemento mínimo global 0 y un elemento máximo global 1. Estos símbolos son nombres estructurales y no tienen por qué ser los números cero y uno.
El segundo ejemplo muestra por qué conviene pensar en «mínimo» y «máximo» del orden, no en el valor numérico. Bajo divisibilidad, 1 es el mínimo porque divide a todos los elementos.
Un retículo es distributivo si encuentro y unión se distribuyen mutuamente, de forma análoga a multiplicación y suma:
El retículo de subconjuntos con intersección y unión es distributivo. Esta propiedad será importante al estudiar álgebra de Boole, donde además aparecen complementos.
En un retículo acotado, un complemento de a es un elemento b que cumple a ∧ b = 0 y a ∨ b = 1. No todos los retículos poseen complementos.
Un retículo acotado, distributivo y complementado es un álgebra de Boole. El curso profundizará en esta estructura en los próximos temas de lógica y circuitos.
No todo orden parcial tiene encuentro y unión para cada par. Consideremos elementos a y b, ambos por debajo de dos elementos incomparables c y d, sin un elemento menor común entre c y d que siga estando por encima de a y b.
Tener cotas superiores no basta. Debe existir una cota superior que sea menor o igual que todas las otras cotas superiores, es decir, una unión bien definida.
El modelo exacto depende del dominio. Antes de llamar «unión» a una operación de software, se debe comprobar qué orden representa y si realmente satisface las propiedades requeridas.
Los retículos muestran que operaciones cotidianas de unión y encuentro comparten una misma estructura abstracta. En el próximo tema estudiaremos el álgebra de Boole, que formaliza la lógica de valores verdaderos y falsos mediante operaciones relacionadas.