Retículo distributivo

Enmatemática, unretículo distributivoes unretículoen el cual las operaciones de unión (join) e intersección (meet) sedistribuyenla una sobre la otra. El ejemplo típico de estas estructuras es una colección de conjuntos, donde los operadores quedan dados por launión de conjuntosy laintersección de conjuntos. De hecho, dicho ejemplo describe el escenario por completo: todo retículo distributivo esisomorfoa un retículo de conjuntos.
Como en el caso de los retículos arbitrarios, un retículo distributivoLpuede definirse equivalentemente como una estructura desde el punto de vista de lateoría del ordeno delálgebra universal.
Un retículo (L,∨{\displaystyle \vee },∧{\displaystyle \wedge }) esdistributivosi lo siguiente se cumple para todox,y,zenL:
Viendo los retículos comoconjuntos parcialmente ordenados, se dice que el operadormeet"preserva" un número finito y no vacío de operadoresjoin. Un resultado básico de la teoría de retículos es que la condición de arriba es equivalente a sudual:
Otra definición equivalente es decir queLes distributivosi y sólo silo siguiente se cumple para cualesquiera elementosx,y,zenL:
Lo que a su vez es equivalente a decir
Unmorfismode retículos distributivos es una función que es compatible con los dos operadoresmeetyjoin.
Los retículos distributivos son estructuras ubicuas y al mismo tiempo muy específicas. El ejemplo típico es lafamilia de conjuntosprovista de los operadores deunióneintersección. Otros ejemplos son:
Los retículosno-distributivosmás simples son el "retículo diamante",M3, y el "retículo pentágono",N5. Un retículo es distributivo si y sólo si ninguno de sus subretículos es isomorfo aM3oN5; unsubretículoes unsubconjuntocerrado bajo los operadores meet y join del retículo original.
Un elemento de un retículo distributivo esmeet-primooínfimo-primosi y sólo si es meet-irreducible o ínfimo-irreducible, aunque esta última se considera en general una propiedad más débil. Por dualidad, lo mismo es cierto para los elementos join-primo (supremo-primo) y join-irreducibles (supremo-irreducibles).​ Si un retículo es distributivo, surelación de coberturaforma ungrafo mediano.​
Finalmente, todo retículo distributivo es tambiénmodular.
En la introducción se señaló la caracterización más importante para los retículos distributivos. Dado un retículoL:
Que la unión e intersección son distributivas en el sentido de arriba, es decir, afirmar que se cumple elbicondicionalde derecha a izquierda, es un hecho elemental. La implicación en sentido contrario es menos trivial, pues requiere deteoremas de representación. La idea de esta caracterización es que las identidades o ecuaciones que se mantienen en todos los retículos distributivos son exactamente las mismas que se cumplen en todos los retículos de conjuntos descritos anteriormente.
ElTeorema de representación de Birkhoffpara retículos distributivos establece que todo retículo distributivofinitoes isomorfo al retículo deconjuntos superioresdelposetde sus elementos join-primos (o equivalentemente, join-irreducibles). Esto establece unabiyección(salvoisomorfismo) entre la clase de todos los posets y la clase de todos los retículos distributivos finitos. Esta biyección puede extenderse a unadualidad de categoríasentre homomorfismos de retículos distributivos finitos yfunciones monótonasde posets finitos. Generalizar estos resultados a retículos infinitos, sin embargo, requiere del uso de estructuras adicionales.
Otro antiguo teorema de representación es ahora conocido como elTeorema de representación de Stone para retículos distributivos(llamado así en honor aMarshall Harvey Stone, quien fue el primero en demostrarlo). Este teorema caracteriza retículos distributivos como retículos de conjuntosabiertoscompactosde ciertosespacios topológicos. Este resultado puede ser visto como una generalización delTeorema de representación de Stone para álgebras booleanasy como una especialización del marco general de ladualidad de Stone.
Una representación importante fue establecida porHilary Priestleyen suTeorema de representación de Priestley para retículos distributivos. En esta formulación, un retículo distributivo se utiliza para construir un espacio topológico con un orden parcial adicional sobre sus puntos, obteniendo unespacio de Stoneordenado(oespacio de Priestley). El retículo original es recuperado como la colección de conjuntosclopeninferiores en este espacio.
Como consecuencia de los teoremas de Stone y de Priestley, es fácil deducir que cualquier retículo distributivo es realmente isomorfo a un retículo de conjuntos. Sin embargo, las demostraciones de ambas aseveraciones requieren delteorema del primo ideal booleano, una forma débil delaxioma de elección.
Elretículo distributivolibresobre un conjunto de generadoresGpuede construirse más fácilmente que unretículo libregeneral. Una primera observación es que, usando las propiedades de distributividad, cada término formado por los operadores binarios∨{\displaystyle \vee }y∧{\displaystyle \wedge }en un conjunto de generadores puede ser transformado equivalentemente en la siguienteforma normal:
dondeMison meets finitos de elementos deG. Además, como el meet y el join sonconmutativoseidempotentes, se pueden ignorar los órdenes y los duplicados, para así representar un join de meets como el de arriba como un conjunto de conjuntos:
dondeNison subconjuntos finitos deG. Sin embargo, es todavía posible que dos de estos términos denoten el mismo elemento de retículos distributivos. Esto ocurre cuando existen índicesjyktales queNjes un subconjunto deNk. En este caso el meet deNkestará debajo del meet deNj, y por lo tanto se puede retirar con seguridad el conjuntoredundanteNksin cambiar la representación del término total. En consecuencia, un conjunto de subconjuntos finitos deGse llamaráirredundantesiempre que todos sus elementosNisean mutuamente incomparables (con respecto al ordenamiento del subconjunto); lo que se cumple cuando este forma unaanticadenade conjuntos finitos.
Ahora el retículo distributivo libre sobre un conjunto de generadoresGes definido como el conjunto de todos los conjuntos irredundantes finitos de subconjuntos deG(o lo que es lo mismo, como unhipergrafoirredundante). El join de dos conjuntos finitos irredundantes se obtiene de sus uniones removiendo todos los conjuntos redundantes. Asimismo, el meet de dos conjuntosSyTes la versión irredundante de {N∩{\displaystyle \cap }M|NenS,MenT}. Esta estructura es un retículo distributivo con la requeridapropiedad universal.
El número de elementos en un retículo distributivo libre conngeneradores está dado por losnúmeros de Dedekind. Estos números crecen rápidamente, y son conocidos sólo paran≤ 8; estos son
Los números de arriba cuentan el número de estos retículos en que las operaciones son uniones e intersecciones de conjuntos de elementos finitos, incluyendo alconjunto vacío. Si no permitimos las uniones e intersecciones vacías, el retículo distributivo libre tiene dos elementos menos; sus números de elementos forman la secuencia