En matemáticas , un retículo distributivo es un retículo en el que las operaciones de unión y encuentro se distribuyen entre sí. Los ejemplos prototípicos de tales estructuras son colecciones de conjuntos para los que las operaciones de celosía pueden darse por unión e intersección de conjuntos . De hecho, estas celosías de conjuntos describen el escenario por completo: toda celosía distributiva es —hasta el isomorfismo— dada como tal celosía de conjuntos.
Definición
Como en el caso de las celosías arbitrarias, se puede optar por considerar una celosía distributiva L como una estructura de la teoría del orden o de álgebra universal . Ambos puntos de vista y su correspondencia mutua se discuten en el artículo sobre celosías . En la situación actual, la descripción algebraica parece ser más conveniente:
Una red ( L , ∨, ∧) es distributiva si la siguiente identidad adicional se cumple para todo x , y y z en L :
- x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ).
Al ver las celosías como conjuntos parcialmente ordenados, esto dice que la operación de encuentro conserva las uniones finitas no vacías. Es un hecho básico de la teoría de celosía que la condición anterior es equivalente a su dual : [1]
- x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) para todo x , y , y z en L . [2]
En cada celosía, definiendo p ≤ q como de costumbre para significar p ∧ q = p , la desigualdad x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ) se cumple así como su desigualdad dual x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ). Una celosía 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 sobre distributividad (teoría del orden) .
Morfismos
Un morfismo de celosías distributivas es solo un homomorfismo de celosía como se indica en el artículo sobre celosías , es decir, una función que es compatible con las dos operaciones de celosía. Debido a que tal morfismo de celosías conserva la estructura de celosía, en consecuencia también preservará la distributividad (y por lo tanto será un morfismo de celosías distributivas).
Ejemplos de
Las redes distributivas son estructuras ubicuas pero también bastante específicas. Como ya se mencionó, el ejemplo principal de las celosías distributivas son las celosías de conjuntos, donde join y meet vienen dados por 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 apoyan la conjunción y la disyunción es una red distributiva, es decir, "y" distribuye "o" y viceversa.
- Cada álgebra de Boole es una red distributiva.
- Cada álgebra de Heyting es una red distributiva. Especialmente esto incluye todas las configuraciones regionales y, por lo tanto, todas las celosías abiertas de espacios topológicos . También tenga en cuenta que las álgebras de Heyting pueden verse como álgebras de Lindenbaum de lógica intuicionista , lo que las convierte en un caso especial del primer ejemplo.
- Cada conjunto totalmente ordenado es una celosía distributiva con max como join y min como meet.
- Los números naturales forman una red distributiva (condicionalmente completa) tomando el máximo común divisor como igual y el mínimo común múltiplo como unión. Esta celosía también tiene un elemento mínimo, a saber, 1, que por lo tanto sirve como elemento de identidad para uniones.
- Dado un entero positivo n , el conjunto de todos los divisores positivos de n forma una red distributiva, nuevamente con el máximo común divisor como meet y el mínimo común múltiplo como join. Esta es un álgebra booleana si y solo si n es libre de cuadrados .
- Un espacio vectorial ordenado en celosía es un enrejado distributivo.
- La celosía de Young dada por el orden de inclusión de los diagramas de Young que representan particiones enteras es una celosía distributiva.
- Los puntos de un politopo distributivo (un politopo convexo cerrado bajo operaciones coordinadas mínimo y coordinado máximo), con estas dos operaciones como las operaciones de unión y encuentro de la celosía. [3]
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. [4] [5] Sin embargo, las pruebas de independencia fueron dadas por Schröder , Voigt, ( de ) Lüroth , Korselt , [6] y Dedekind . [4]
Propiedades caracteristicas
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 :
- ( xy ) ( yz ) ( zx ) = ( xy ) ( yz ) ( zx ).
De manera similar, L es distributiva si y solo si
- Xz = yz y xz = yz siempre implica x = y .
El entramado de diamantes M 3 no es distributivo: x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ 0 = 0 ∨ 0 = ( x ∧ y ) ∨ ( x ∧ z ) .
La red del pentágono N 5 no es distributiva: x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ z = 0 ∨ z = ( x ∧ y ) ∨ ( x ∧ z ) .
Las celosías no distributivas más simples son M 3 , la "celosía de diamante", y N 5 , la "celosía del pentágono". Un retículo es distributivo si y solo si ninguno de sus subrretículos es isomórfico a M 3 o N 5 ; una subred es un subconjunto que se cierra bajo las operaciones de encuentro y unión del enrejado original. Tenga en cuenta que esto no es lo mismo que ser un subconjunto que es una celosía en 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 afirmar el mismo hecho es que cada retícula distributiva es un producto subdirecto de copias de la cadena de dos elementos , o que el único miembro subdirectamente irreductible de la clase de retículas distributivas es la cadena de dos elementos. Como corolario, cada celosía booleana también tiene esta propiedad. [7]
Finalmente, la distributividad conlleva varias otras propiedades agradables. Por ejemplo, un elemento de una red distributiva es meet-prime si y solo si es meet-irreducible , aunque esta última es en general una propiedad más débil. Por dualidad, lo mismo es cierto para los elementos join-prime y join-irreductibles . [8] Si un retículo es distributivo, su relación de cobertura forma un gráfico mediano . [9]
Además, cada celosía distributiva también es modular .
Teoría de la representación
La introducción ya insinuaba la caracterización más importante de las celosías distributivas: una celosía es distributiva si y solo si es isomorfa a una celosía de conjuntos (cerrada bajo unión e intersección de conjuntos ). (La última estructura a veces se denomina anillo de conjuntos en este contexto.) Que la unión y la intersección de conjuntos sean de hecho 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 indican a continuación. La idea importante de esta caracterización es que las identidades (ecuaciones) que se mantienen en todas las redes distributivas son exactamente las que se mantienen en todas las redes de conjuntos en el sentido anterior.
Teorema de representación de Birkhoff para los estados enrejados distributivos que cada finita distributiva celosía es isomorfo a la red de conjuntos inferiores del conjunto parcialmente ordenado de su unirse de alto riesgo (equivalentemente: Join-irreductible) elementos. Esto establece una biyección (hasta isomorfismo ) entre la clase de todos los posets finitos y la clase de todos los retículos distributivos finitos. Esta biyección puede extenderse a una dualidad de categorías entre homomorfismos de redes distributivas finitas y funciones monótonas de conjuntos finitos. Sin embargo, generalizar este resultado a celosías infinitas requiere agregar más estructura.
Otro teorema de representación temprano se conoce ahora como teorema de representación de Stone para retículas distributivas (el nombre honra a Marshall Harvey Stone , quien lo demostró por primera vez). Caracteriza las celosías distributivas como las celosías 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 álgebras de Boole y como una especialización del entorno general de la dualidad de Stone .
Hilary Priestley estableció otra representación importante en su teorema de representación para celosías distributivas . En esta formulación, se usa una celosía distributiva para construir un espacio topológico con un orden parcial adicional en sus puntos, produciendo un espacio de Stone ordenado (completamente separado en orden ) (o espacio de Priestley ). La celosía original se recupera como conjunto de conjuntos inferiores abiertos de este espacio.
Como consecuencia de los teoremas de Stone y Priestley, se ve fácilmente que cualquier retícula distributiva es realmente isomórfica a una retícula de conjuntos. Sin embargo, las demostraciones de ambos enunciados requieren el teorema del ideal primo de Boole , una forma débil del axioma de elección .
Celosías distributivas libres
La celosía distributiva libre sobre un conjunto de generadores G se puede construir mucho más fácilmente que una celosía libre general. La primera observación es que, usando las leyes de la distributividad, cada término formado por las operaciones binarias y en un conjunto de generadores se puede transformar en la siguiente forma normal equivalente :
dónde son finitos cumple de elementos de G . Además, dado que ambos meet y join son asociativos , conmutativos e idempotentes , se pueden ignorar los duplicados y el orden, y representar una combinación de encuentros como el anterior como un conjunto de conjuntos:
donde el 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 es un subconjunto de En este caso el encuentro de estará por debajo del encuentro de y por lo tanto, se puede eliminar de forma segura el conjunto redundantesin 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 elementosson mutuamente incomparables (con respecto al orden de subconjuntos); es decir, cuando forma un antichain de conjuntos finitos .
Ahora el retículo distributivo libre sobre un conjunto de generadores G se define en el conjunto de todos los conjuntos de irredundant finitos de subconjuntos finitos de G . La unión de dos conjuntos irredundantes finitos se obtiene de su unión eliminando todos los conjuntos redundantes. Asimismo, el encuentro de dos conjuntos S y T es la versión irredundante deLa 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 se conocen solo para n ≤ 8; ellos son
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (secuencia A000372 en la OEIS ).
Los números anteriores cuentan el número de elementos en celosías distributivas libres en las que las operaciones de celosía son uniones y encuentros de conjuntos finitos de elementos, incluido el conjunto vacío. Si las uniones vacías y las reuniones vacías no están permitidas, las celosías distributivas libres resultantes tienen dos elementos menos; sus números de elementos forman la secuencia
- 0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (secuencia A007153 en la OEIS ).
Ver también
- Celosía completamente distributiva : una celosía en la que infinitas uniones se distribuyen sobre infinitos encuentros
- Teoría de la dualidad para redes distributivas
- Espacio espectral
Referencias
- ^ Birkhoff, Garrett (1967). Teoría de celosía . Publicaciones del coloquio (3ª ed.). Sociedad Matemática Estadounidense. pag. 11 . ISBN 0-8218-1025-1. §6, Teorema 9
- ^ Para elementos individuales x , y , z , por ejemplo, la primera ecuación puede violarse, pero la segunda puede ser válida; vea laimagen deN 5 como ejemplo.
- ^ Felsner, Stefan; Knauer, Kolja (2011), "Rejillas distributivas, poliedros y flujos generalizados", European Journal of Combinatorics , 32 (1): 45–59, doi : 10.1016 / j.ejc.2010.07.011 , MR 2727459.
- ^ a b Peirce, Charles S .; Fisch, MH; Kloesel, CJW (1989), Escritos de Charles S. Peirce: 1879–1884 , Indiana University Press, pag. xlvii.
- ^ Charles S. Peirce (1880). "Sobre el álgebra de la lógica". Revista Estadounidense de Matemáticas . 3 : 15–57. doi : 10.2307 / 2369442 . JSTOR 2369442 ., pag. 33 abajo
- ^ A. Korselt (1894). "Bemerkung zur Algebra der Logik" . Mathematische Annalen . 44 : 156-157. doi : 10.1007 / bf01446978 .El ejemplo de celosía no distributiva de Korselt es una variante de M 3 , con 0, 1 y x , y , z correspondientes al conjunto vacío, una línea y tres puntos distintos en él, respectivamente.
- ^ Balbes y Dwinger (1975), p. 63 citando a Birkhoff, G. "Uniones subdirectas en álgebra universal", Bull. Amer. Matemáticas. Soc. SO (1944), 764-768.
- ^ Ver teorema de representación de Birkhoff # El orden parcial de los irreducibles de unión .
- ^ Birkhoff, Garrett ; Kiss, SA (1947), "Una operación ternaria en celosías distributivas" , Boletín de la American Mathematical Society , 53 (1): 749–752, doi : 10.1090 / S0002-9904-1947-08864-9 , MR 0021540.
Otras lecturas
- Burris, Stanley N .; Sankappanavar, HP (1981). Un curso de álgebra universal . Springer-Verlag. ISBN 3-540-90578-2.
- Secuencia OEIS A006982 (Número de celosías distributivas sin etiquetar con n elementos)