En matemáticas , una red distributiva es una red en la que las operaciones de unirse y encontrarse se distribuyen entre sí. Los ejemplos prototípicos de tales estructuras son colecciones de conjuntos para los cuales las operaciones de red pueden darse mediante unión e intersección de conjuntos . De hecho, estos retículos de conjuntos describen el escenario completamente: cada retículo distributivo está –hasta el isomorfismo– dado como tal retículo de conjuntos.
Como en el caso de las redes arbitrarias, se puede optar por considerar una red distributiva L como una estructura de la teoría del orden o del álgebra universal . Ambos puntos de vista y su correspondencia mutua se analizan en el artículo sobre celosías . En la situación actual, la descripción algebraica parece más conveniente.
Una red ( L ,∨,∧) es distributiva si la siguiente identidad adicional se cumple para todos los x , y y z en L :
Al ver las celosías como conjuntos parcialmente ordenados, esto dice que la operación de encuentro preserva las uniones finitas no vacías. Es un hecho básico de la teoría de la red que la condición anterior es equivalente a su dual : [1]
En cada red, si uno define la relación de orden p ≤ q como de costumbre para significar p ∧ q = p , entonces la desigualdad x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ) y su dual x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ) siempre son verdaderas. Una red es distributiva si una de las desigualdades inversas también se cumple. Se puede encontrar más información sobre la relación de esta condición con otras condiciones de distributividad de la teoría del orden en el artículo Distributividad (teoría del orden) .
Un morfismo de redes distributivas es simplemente un homomorfismo de red como se indica en el artículo sobre redes , es decir, una función que es compatible con las dos operaciones de red. Debido a que tal morfismo de redes preserva la estructura de la red, en consecuencia también preservará la distributividad (y por lo tanto será un morfismo de redes distributivas).
Las redes distributivas son estructuras ubicuas pero también bastante específicas. Como ya se mencionó, el principal ejemplo de redes distributivas son las redes de conjuntos, donde la unión y el encuentro vienen dados por las operaciones habituales de la teoría de conjuntos. Otros ejemplos incluyen:
Al principio del desarrollo de la teoría de la red, Charles S. Peirce creía que todas las redes son distributivas, es decir, la distributividad se deriva del resto de los axiomas de la red. [3] [4] Sin embargo, Schröder , Voigt, (de) Lüroth , Korselt , [5] y Dedekind dieron pruebas de independencia . [3]
Existen varias formulaciones equivalentes a la definición anterior. Por ejemplo, L es distributiva si y sólo si lo siguiente se cumple para todos los elementos x , y , z en L :
Las redes no distributivas más simples son M 3 , la "red de diamante" y N 5 , la "red de pentágono". Una red es distributiva si y sólo si ninguna de sus subredes es isomorfa a M 3 o N 5 ; una subred es un subconjunto que se cierra bajo las operaciones de encuentro y unión de la red original. Tenga en cuenta que esto no es lo mismo que ser un subconjunto que es una red según el orden original (pero posiblemente con diferentes operaciones de unión y encuentro). Otras caracterizaciones se derivan de la teoría de la representación en la siguiente sección.
Una forma alternativa de plantear el mismo hecho es que cada red distributiva es un producto subdirecto de copias de la cadena de dos elementos , o que el único miembro subdirectamente irreducible de la clase de redes distributivas es la cadena de dos elementos. Como corolario, toda red booleana también tiene esta propiedad. [6]
Finalmente, la distributividad implica varias otras propiedades agradables. Por ejemplo, un elemento de una red distributiva es primo si y sólo si es irreducible , aunque esta última es en general una propiedad más débil. Por dualidad, lo mismo ocurre con los elementos primos unidos y irreducibles . [7] Si una red es distributiva, su relación de cobertura forma un gráfico de mediana . [8]
Además, cada red distributiva también es modular .
La introducción ya insinuó la caracterización más importante de las redes distributivas: una red es distributiva si y solo si es isomorfa a una red de conjuntos (cerrada bajo unión e intersección de conjuntos ). (Esta última estructura a veces se denomina anillo de conjuntos en este contexto). Que la unión y la intersección de conjuntos sean distributivas en el sentido anterior es un hecho elemental. La otra dirección es menos trivial, ya que requiere los teoremas de representación que se exponen a continuación. La idea importante de esta caracterización es que las identidades (ecuaciones) que se cumplen en todas las redes distributivas son exactamente las que se cumplen en todas las redes de conjuntos en el sentido anterior.
El teorema de representación de Birkhoff para redes distributivas establece que cada red distributiva finita es isomorfa a la red de conjuntos inferiores del poset de sus elementos primos de unión (equivalentemente: irreducibles de unión). Esto establece una biyección (hasta el isomorfismo ) entre la clase de todos los posets finitos y la clase de todas las redes distributivas finitas. Esta biyección se puede extender a una dualidad de categorías entre homomorfismos de redes distributivas finitas y funciones monótonas de posets finitos. Sin embargo, generalizar este resultado a redes infinitas requiere agregar más estructura.
Otro teorema de representación temprano se conoce ahora como teorema de representación de Stone para redes distributivas (el nombre honra a Marshall Harvey Stone , quien lo demostró por primera vez). Caracteriza las redes distributivas como redes de conjuntos abiertos compactos de ciertos espacios topológicos . Este resultado puede verse como una generalización del famoso teorema de representación de Stone para las álgebras de Boole y como una especialización del escenario general de la dualidad de Stone .
Hilary Priestley estableció otra representación importante en su teorema de representación para redes distributivas . En esta formulación, se utiliza una red distributiva para construir un espacio topológico con un orden parcial adicional en sus puntos, produciendo un espacio de Stone ordenado (o espacio de Priestley ) (completamente separado en orden ). Se recupera la celosía original como conjunto de conjuntos inferiores abiertos de este espacio.
Como consecuencia de los teoremas de Stone y Priestley, se ve fácilmente que cualquier red distributiva es realmente isomorfa a una red de conjuntos. Sin embargo, las pruebas de ambos enunciados requieren el teorema del ideal primo booleano , una forma débil del axioma de elección .
La red distributiva libre sobre un conjunto de generadores G se puede construir mucho más fácilmente que una red libre general. La primera observación es que, utilizando las leyes de la distributividad, todo término formado por las operaciones binarias y sobre un conjunto de generadores puede transformarse en la siguiente forma normal equivalente :
donde son encuentros finitos de elementos de G . Además, dado que tanto el encuentro como la unión son asociativos , conmutativos e idempotentes , se pueden ignorar los duplicados y el orden, y representar una unión de encuentros como la anterior como un conjunto de conjuntos:
donde son subconjuntos finitos de G . Sin embargo, todavía es posible que dos de esos términos denoten el mismo elemento de la red distributiva. Esto ocurre cuando hay índices j y k tales que son un subconjunto de. En este caso, el encuentro de estará por debajo del encuentro de y, por lo tanto, se puede eliminar con seguridad el conjunto redundante sin cambiar la interpretación del término completo. En consecuencia, un conjunto de subconjuntos finitos de G se llamará irredundante siempre que todos sus elementos sean mutuamente incomparables (con respecto al orden de los subconjuntos); es decir, cuando forma una anticadena de conjuntos finitos .
Ahora la red distributiva libre sobre un conjunto de generadores G se define en el conjunto de todos los conjuntos finitos irredundantes de subconjuntos finitos de G. La unión de dos conjuntos finitos irreundantes se obtiene de su unión eliminando todos los conjuntos redundantes. Asimismo, el encuentro de dos conjuntos S y T es la versión irreundante de La verificación de que esta estructura es una red distributiva con la propiedad universal requerida es rutinaria.
El número de elementos en redes distributivas libres con n generadores viene dado por los números de Dedekind . Estos números crecen rápidamente y sólo se conocen para n ≤ 9; ellos son
Los números anteriores cuentan el número de elementos en redes distributivas libres en las que las operaciones de red son uniones y encuentros de conjuntos finitos de elementos, incluido el conjunto vacío. Si no se permiten uniones vacías y encuentros vacíos, las redes distributivas libres resultantes tienen dos elementos menos; sus números de elementos forman la secuencia
