Red distributiva

En matemáticas , una red distributiva es una red en la que las operaciones de unión y encuentro se distribuyen entre sí. Los ejemplos prototípicos de tales estructuras son colecciones de conjuntos para las cuales las operaciones de red pueden darse mediante la unión y la intersección de conjuntos . De hecho, estas redes de conjuntos describen el escenario por completo: toda red distributiva está dada, salvo isomorfismo , como una red de conjuntos.

Definición

Como en el caso de los retículos arbitrarios, se puede optar por considerar un retículo distributivo 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 retículos . En la situación actual, la descripción algebraica parece ser más conveniente.

Una red ( L ,∨,∧) es distributiva si se cumple la siguiente identidad adicional para todos los x , y y z en L :

x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ).

Si consideramos las redes como conjuntos parcialmente ordenados, esto indica que la operación de encuentro preserva las uniones finitas no vacías. Es un hecho básico de la teoría de redes que la condición anterior es equivalente a su dual : ^[1]

x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) para todos x , y y z en L .

En cada red, si se define la relación de orden p ≤ q como es habitual, es decir p ∧ q = p , entonces la desigualdad x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ) y su dual x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ) son siempre verdaderas. Una red es distributiva si también se cumple una de las desigualdades inversas. 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) .

Morfismos

Un morfismo de retículos distributivos es simplemente un homomorfismo de retículos como el que se da en el artículo sobre retículos , es decir, una función que es compatible con las dos operaciones de retículos. Debido a que dicho morfismo de retículos preserva la estructura de retículo, en consecuencia también preservará la distributividad (y, por lo tanto, será un morfismo de retículos distributivos).

Ejemplos

Celosía de Young

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 se dan mediante las operaciones habituales de la teoría de conjuntos. Otros ejemplos incluyen:

• El álgebra de Lindenbaum de la mayoría de las lógicas que admiten conjunción y disyunción es una red distributiva, es decir, "y" se distribuye sobre "o" y viceversa.
• Toda álgebra de Boole es una red distributiva.
• Toda álgebra de Heyting es una red distributiva. Esto incluye especialmente todas las localidades y, por lo tanto, todas las redes de conjuntos abiertos de espacios topológicos . Nótese también que las álgebras de Heyting pueden considerarse álgebras de Lindenbaum de lógica intuicionista , lo que las convierte en un caso especial del primer ejemplo.
• Todo conjunto totalmente ordenado es una red distributiva con max como unión y min como encuentro.
• Los números naturales forman una red distributiva (condicionalmente completa) tomando como punto de encuentro el máximo común divisor y como punto de unión el mínimo común múltiplo . Esta red también tiene un elemento mínimo, a saber, el 1, que sirve por tanto como elemento de identidad para los puntos de unión.
• Dado un entero positivo n , el conjunto de todos los divisores positivos de n forma una red distributiva, donde nuevamente el máximo común divisor es el punto de encuentro y el mínimo común múltiplo es el de unión. Se trata de un álgebra booleana si y solo si n es un entero libre de cuadrados .
• Un espacio vectorial ordenado en red es una red distributiva.
• La red de Young dada por el orden de inclusión de los diagramas de Young que representan particiones enteras es una red distributiva.
• Los puntos de un politopo distributivo (un politopo convexo cerrado bajo operaciones de mínimo y máximo coordinado), con estas dos operaciones como las operaciones de unión y encuentro de la red. ^[2]

Al principio del desarrollo de la teoría de redes, Charles S. Peirce creía que todas las redes son distributivas, es decir, la distributividad se deduce del resto de los axiomas de redes. ^{[3] [4] Sin embargo,} Schröder , Voigt, ^(de) Lüroth , Korselt , ^[5] y Dedekind dieron pruebas de independencia . ^[3]

Propiedades características

Diagramas de Hasse de las dos redes prototípicas no distributivas. La red romboidal M ₃ no es distributiva porque x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ 0 = 0 ∨ 0 = ( x ∧ y ) ∨ ( x ∧ z ) , mientras que la red pentagonal N ₅ no es distributiva porque x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ z = 0 ∨ z = ( x ∧ y ) ∨ ( x ∧ z )

Existen varias formulaciones equivalentes a la definición anterior. Por ejemplo, L es distributiva si y solo si se cumple lo siguiente para todos los elementos x , y , z en L : De manera similar, L es distributiva si y solo si $${\displaystyle (x\wedge y)\vee (y\wedge z)\vee (z\wedge x)=(x\vee y)\wedge (y\vee z)\wedge (z\vee x).}$$

${\displaystyle x\wedge z=y\wedge z}$y siempre implica ${\displaystyle x\vee z=y\vee z}$ ${\displaystyle x=y.}$

Red distributiva que contiene N5 (líneas continuas, izquierda) y M3 (derecha) como subconjunto , pero no como subred

Las redes no distributivas más simples son M ₃ , la "red de diamante", y N ₅ , la "red de pentágonos". Una red es distributiva si y solo si ninguna de sus subredes es isomorfa a M ₃ o  N ₅ ; una subred es un subconjunto que está cerrado bajo las operaciones de encuentro y unión de la red original. Nótese que esto no es lo mismo que ser un subconjunto que es una red bajo el orden original (pero posiblemente con diferentes operaciones de encuentro y unión). Otras caracterizaciones se derivan de la teoría de la representación en la siguiente sección.

Una forma alternativa de enunciar 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, cada 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-conjunta si y solo si es irreducible-conjunta , aunque esta última es en general una propiedad más débil. Por dualidad, lo mismo es cierto para elementos primos-conjunta e irreducibles-conjunta . ^[7] Si una red es distributiva, su relación de recubrimiento forma un grafo mediano . ^[8]

Además, cada red distributiva también es modular .

Teoría de la representación

La introducción ya ha dado pistas sobre la caracterización más importante de los retículos distributivos: un retículo es distributivo si y sólo si es isomorfo a un retículo de conjuntos (cerrado bajo la unión e intersección de conjuntos ). (A esta última estructura a veces se la llama anillo de conjuntos en este contexto). Que la unión e intersección de conjuntos sean de hecho distributivos en el sentido antes mencionado es un hecho elemental. La otra dirección es menos trivial, ya que requiere los teoremas de representación que se indican a continuación. La idea importante de esta caracterización es que las identidades (ecuaciones) que se cumplen en todos los retículos distributivos son exactamente las que se cumplen en todos los retículos de conjuntos en el sentido antes mencionado.

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 conjunto parcial de sus elementos primos en la unión (equivalentemente: irreducibles en la unión). Esto establece una biyección (hasta el isomorfismo ) entre la clase de todos los conjuntos parciales 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 conjuntos parciales finitos. Sin embargo, generalizar este resultado a redes infinitas requiere agregar más estructura.

Otro teorema de representación temprano es el conocido actualmente como teorema de representación de Stone para redes distributivas (el nombre rinde homenaje a Marshall Harvey Stone , quien lo demostró por primera vez). Caracteriza las redes distributivas como las redes de conjuntos abiertos compactos de ciertos espacios topológicos . Este resultado puede considerarse tanto una generalización del famoso teorema de representación de Stone para las álgebras de Boole como una especialización del contexto 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, lo que produce un espacio de Stone ordenado (o espacio de Priestley ) (completamente separado por orden ). La red original se recupera como la colección de conjuntos inferiores clopen de este espacio.

Como consecuencia de los teoremas de Stone y Priestley, se ve fácilmente que cualquier red distributiva es en realidad isomorfa a una red de conjuntos. Sin embargo, las demostraciones de ambas afirmaciones requieren el teorema del ideal primo de Boole , una forma débil del axioma de elección .

Redes distributivas libres

Redes distributivas libres en generadores cero, uno, dos y tres. Los elementos etiquetados como "0" y "1" son la unión y encuentro vacíos, y el elemento etiquetado como "mayoría" es ( x ∧ y ) ∨ ( x ∧ z ) ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) ∧ ( y ∨ z ).

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 distributividad, cada término formado por las operaciones binarias y sobre un conjunto de generadores se puede transformar en la siguiente forma normal equivalente : ${\displaystyle \lor }$ ${\displaystyle \land }$

${\displaystyle M_{1}\lor M_{2}\lor \cdots \lor M_{n},}$

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: ${\displaystyle M_{i}}$

${\displaystyle \{N_{1},N_{2},\ldots ,N_{n}\},}$

donde son subconjuntos finitos de G . Sin embargo, todavía es posible que dos de estos términos denoten el mismo elemento de la red distributiva. Esto ocurre cuando hay índices j y k tales que es 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 de todo el término. 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 forme una anticadena de conjuntos finitos . ${\displaystyle N_{i}}$ ${\displaystyle N_{j}}$ ${\displaystyle N_{k}.}$ ${\displaystyle N_{k}}$ ${\displaystyle N_{j},}$ ${\displaystyle N_{k}}$ ${\displaystyle N_{i}}$

Ahora bien, la red distributiva libre sobre un conjunto de generadores G se define sobre el conjunto de todos los conjuntos irredundantes finitos de subconjuntos finitos de G . La unión de dos conjuntos irredundantes finitos se obtiene a partir de su unión eliminando todos los conjuntos redundantes. Asimismo, la unión de dos conjuntos S y T es la versión irredundante de La verificación de que esta estructura es una red distributiva con la propiedad universal requerida es rutinaria. ${\displaystyle \{N\cup M\mid N\in S,M\in T\}.}$

El número de elementos en redes distributivas libres con n generadores está dado por los números de Dedekind . Estos números crecen rápidamente y se conocen solo para n  ≤ 9; son

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 (secuencia A000372 en la OEIS ).

Los números anteriores cuentan el número de elementos en retículos distributivos libres en los que las operaciones de retículo son uniones y encuentros de conjuntos finitos de elementos, incluido el conjunto vacío. Si no se permiten las uniones y encuentros vacíos, los retículos distributivos libres resultantes tienen dos elementos menos; sus números de elementos forman la secuencia

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786, 286386577668298411128469151667598498812364 (secuencia A007153 en la OEIS ).

Véase también

• Red completamente distributiva : una red en la que las uniones infinitas se distribuyen sobre encuentros infinitos
• Teoría de dualidad para redes distributivas
• Espacio espectral

Referencias

1. Birkhoff, Garrett (1967). Teoría de retículos . Colloquium Publications (3.ª ed.). American Mathematical Society. pág. 11. ISBN. 0-8218-1025-1.§6, Teorema 9
2. Felsner, Stefan; Knauer, Kolja (2011), "Redes distributivas, poliedros y flujos generalizados", European Journal of Combinatorics , 32 (1): 45–59, doi : 10.1016/j.ejc.2010.07.011 , MR  2727459.
3. Peirce, Charles S.; Fisch, MH; Kloesel, CJW (1989), Escritos de Charles S. Peirce: 1879–1884, Indiana University Press, pág. xlvii.
4. Charles S. Peirce (1880). "Sobre el álgebra de la lógica". American Journal of Mathematics . 3 : 15–57. doi :10.2307/2369442. JSTOR  2369442., pág. 33 abajo
5. A. Korselt (1894). "Bemerkung zur Algebra der Logik". Annalen Matemáticas . 44 : 156-157. doi :10.1007/bf01446978.El ejemplo de red no distributiva de Korselt es una variante de M ₃ , donde 0, 1 y x , y , z corresponden al conjunto vacío, una línea y tres puntos distintos en ella, respectivamente.
6. Balbes y Dwinger (1975), pág. 63, citando a Birkhoff, G. "Subdirect unions in universal algebra", Bull. Amer. Math. Soc. SO (1944), 764-768.
7. Véase el teorema de representación de Birkhoff#El orden parcial de los irreducibles de unión .
8. Birkhoff, Garrett ; Kiss, SA (1947), "Una operación ternaria en redes distributivas", Boletín de la Sociedad Matemática Americana , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR  0021540.

Lectura adicional

• Burris, Stanley N.; Sankappanavar, HP (1981). Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2.
• Secuencia OEIS A006982 (Número de redes distributivas no etiquetadas con n elementos)