- Se trata de la teoría de la celosía . Para obtener otros resultados con nombres similares, consulte el teorema de Birkhoff (desambiguación) .
En matemáticas , teorema de representación de Birkhoff para enrejados distributivos estados que los elementos de cualquier finito distributiva celosía puede representarse como conjuntos finitos , de tal manera que las operaciones de celosía corresponden a las uniones y las intersecciones de los conjuntos. El teorema se puede interpretar como una correspondencia biunívoca entre retículas distributivas y órdenes parciales , entre espacios de conocimiento cuasi ordinales y preordenes , o entre espacios topológicos finitos y preordenes. Lleva el nombre de Garrett Birkhoff, quien publicó una prueba de ello en 1937. [1]
El nombre "teorema de representación de Birkhoff" también se ha aplicado a otros dos resultados de Birkhoff, uno de 1935 sobre la representación de álgebras de Boole como familias de conjuntos cerrados bajo unión, intersección y complemento (los llamados campos de conjuntos , estrechamente relacionados con los anillos de conjuntos utilizados por Birkhoff para representar redes distributivas), y el teorema HSP de Birkhoff que representa álgebras como productos de álgebras irreducibles. El teorema de representación de Birkhoff también se ha denominado teorema fundamental de las redes distributivas finitas . [2]
Entendiendo el teorema
Se pueden definir muchas celosías de tal manera que los elementos de la celosía se representen mediante conjuntos, la operación de unión de la celosía se represente mediante la unión de conjuntos y la operación de encuentro de la celosía se represente mediante la intersección de conjuntos. Por ejemplo, la red booleana definida a partir de la familia de todos los subconjuntos de un conjunto finito tiene esta propiedad. De manera más general, cualquier espacio topológico finito tiene un entramado de conjuntos como su familia de conjuntos abiertos. Debido a que las uniones e intersecciones de conjuntos obedecen a la ley distributiva , cualquier retícula definida de esta manera es una retícula distributiva. El teorema de Birkhoff establece que, de hecho, todas las celosías distributivas finitas se pueden obtener de esta manera, y las generalizaciones posteriores del teorema de Birkhoff establecen algo similar para las celosías distributivas infinitas.
Ejemplos de
Considere los divisores de algún número compuesto, como (en la figura) 120, parcialmente ordenados por divisibilidad. Dos divisores cualesquiera de 120, como 12 y 20, tienen un máximo común divisor único 12 ∧ 20 = 4, el número más grande que divide a ambos, y un mínimo común múltiplo único 12 ∨ 20 = 60; ambos números son también divisores de 120. Estas dos operaciones ∨ y ∧ satisfacen la ley distributiva , en cualquiera de las dos formas equivalentes: ( x ∧ y ) ∨ z = ( x ∨ z ) ∧ ( y ∨ z ) y ( x ∨ y ) ∧ z = ( x ∧ z ) ∨ ( y ∧ z ), para todo x , y y z . Por tanto, los divisores forman una red distributiva finita .
Se puede asociar cada divisor con el conjunto de potencias primos que lo dividen: así, 12 está asociado con el conjunto {2,3,4}, mientras que 20 está asociado con el conjunto {2,4,5}. Entonces 12 ∧ 20 = 4 está asociado con el conjunto {2,3,4} ∩ {2,4,5} = {2,4}, mientras que 12 ∨ 20 = 60 está asociado con el conjunto {2,3,4 } ∪ {2,4,5} = {2,3,4,5}, por lo que las operaciones de unión y encuentro de la celosía corresponden a la unión y la intersección de conjuntos.
Los poderes primos 2, 3, 4, 5 y 8 que aparecen como elementos en estos conjuntos pueden estar ordenados parcialmente por divisibilidad; en este orden parcial más pequeño, 2 ≤ 4 ≤ 8 y no hay relaciones de orden entre otros pares. Los 16 conjuntos que están asociados con divisores de 120 son los conjuntos inferiores de este orden parcial más pequeña, subconjuntos de elementos tal que si x ≤ y y y pertenece al subconjunto, entonces x debe también pertenecen al subconjunto. De cualquier conjunto inferior L , se puede recuperar el divisor asociada calculando el mínimo común múltiplo de los poderes principales en L . Por lo tanto, el orden parcial de las cinco potencias primas 2, 3, 4, 5 y 8 lleva suficiente información para recuperar la red de divisibilidad de 16 elementos original completa.
El teorema de Birkhoff establece que esta relación entre las operaciones ∧ y ∨ de la red de divisores y las operaciones ∩ y ∪ de los conjuntos asociados de potencias primas no es coincidente ni depende de las propiedades específicas de los números primos y la divisibilidad: los elementos de cualquier red distributiva finita puede asociarse con conjuntos inferiores de un orden parcial de la misma manera.
Como otro ejemplo, la aplicación del teorema de Birkhoff a la familia de subconjuntos de un conjunto de n elementos, parcialmente ordenados por inclusión, produce la red distributiva libre con n generadores. El número de elementos en esta celosía viene dado por los números de Dedekind .
El orden parcial de las uniones irreducibles
En una celosía, un elemento x es uniones irreductibles si x no es la unión de un conjunto finito de otros elementos. De manera equivalente, x es unir-irreductible si no es el elemento inferior de la celosía (la unión de elementos cero) ni la unión de dos elementos más pequeños. Por ejemplo, en la celosía de divisores de 120, no hay un par de elementos cuya unión sea 4, por lo que 4 es unión irreducible. Un elemento x es unir-primo si difiere del elemento inferior, y siempre que x ≤ y ∨ z , ya sea x ≤ y o x ≤ z . En el mismo enrejado, 4 es unirse-prime: siempre que lcm ( y , z ) es divisible por 4, al menos uno de Y y Z debe ser en sí mismo divisible por 4.
En cualquier celosía, un elemento join-prime debe ser join-irreducible. De manera equivalente, un elemento que no es join-irreducible no es join-prime. Para, si un elemento x no se unen-irreducible, existen más pequeño y y z de tal manera que x = y ∨ z . Pero entonces x ≤ y ∨ z , y x no es menor o igual que y o z , lo que demuestra que no es un número primo de unión.
Existen celosías en las que los elementos primos de unión forman un subconjunto propio de los elementos irreductibles de unión, pero en una celosía distributiva los dos tipos de elementos coinciden. Para, suponga que x es unir-irreductible, y que x ≤ y ∨ z . Esta desigualdad es equivalente al enunciado de que x = x ∧ ( y ∨ z ), y por la ley distributiva x = ( x ∧ y ) ∨ ( x ∧ z ). Pero dado que x es irreducible por la unión, al menos uno de los dos términos en esta unión debe ser el mismo x , lo que muestra que x = x ∧ y (equivalentemente x ≤ y ) o x = x ∧ z (equivalentemente x ≤ z ).
El orden de celosía en el subconjunto de elementos irreducibles de unión forma un orden parcial ; El teorema de Birkhoff establece que la propia red se puede recuperar de los conjuntos inferiores de este orden parcial.
Teorema de Birkhoff
En cualquier orden parcial, los conjuntos inferiores forman una celosía en la que el orden parcial de la celosía viene dado por la inclusión de conjuntos, la operación de combinación corresponde a la unión de conjuntos y la operación de encuentro corresponde a la intersección de conjuntos, porque las uniones e intersecciones conservan la propiedad de ser un conjunto. conjunto inferior. Debido a que las uniones e intersecciones de conjuntos obedecen a la ley distributiva, esta es una red distributiva. El teorema de Birkhoff establece que cualquier red distributiva finita se puede construir de esta manera.
- Teorema . Cualquier finito distributiva celosía L es isomorfo a la red de conjuntos inferiores de la orden parcial de los elementos de unirse-irreducibles de L .
Es decir, existe una correspondencia uno a uno que conserva el orden entre los elementos de L y los conjuntos inferiores del orden parcial. El conjunto inferior correspondiente a un elemento x de L es simplemente el conjunto de elementos irreductibles de unión de L que son menores o iguales ax , y el elemento de L correspondiente a un conjunto inferior S de elementos irreductibles de unión es la unión de S .
Para cualquier conjunto inferior S de elementos de unión irreductibles, sea x la unión de S y sea T el conjunto inferior de elementos de unión irreductibles menores o iguales que x . Entonces S = T . Porque, cada elemento de S pertenece claramente a T , y cualquier elemento irreducible de unión menor o igual ax debe (por primalidad de unión) ser menor o igual a uno de los miembros de S , y por lo tanto debe (por el supuesto que S es un conjunto inferior) pertenecen al propio S. A la inversa, para cualquier elemento x de L , vamos S ser la unión-irreducibles elementos menor o igual a x , y sea y ser la unión de S . Entonces x = y . Porque, como una unión de elementos menores o iguales ax , y no puede ser mayor que la propia x , pero si x es unión irreducible, entonces x pertenece a S, mientras que si x es la unión de dos o más elementos irreductibles de unión, entonces deben pertenecer nuevamente a S , entonces y ≥ x . Por lo tanto, la correspondencia es uno a uno y se demuestra el teorema.
Anillos de sets y preordenes
Birkhoff (1937) definió un anillo de conjuntos como una familia de conjuntos que se cierra bajo las operaciones de uniones de conjuntos e intersecciones de conjuntos; más tarde, motivados por aplicaciones en psicología matemática , Doignon y Falmagne (1999) llamaron a la misma estructura un espacio de conocimiento cuasi ordinal . Si los conjuntos en un anillo de conjuntos están ordenados por inclusión, forman una red distributiva. Los elementos de los conjuntos pueden tener un preorden en el que x ≤ y siempre que algún conjunto en el anillo contenga x pero no y . El anillo de conjuntos en sí mismo es entonces la familia de conjuntos inferiores de este preorden, y cualquier preorden da lugar a un anillo de conjuntos de esta manera.
Functorialidad
El teorema de Birkhoff, como se indicó anteriormente, es una correspondencia entre órdenes parciales individuales y retículas distributivas. Sin embargo, también puede extenderse a una correspondencia entre funciones preservadoras de orden de órdenes parciales y homomorfismos acotados de las redes distributivas correspondientes. La dirección de estos mapas se invierte en esta correspondencia.
Deje 2 denotan el orden parcial en el conjunto de dos elementos {0, 1}, con la relación de orden 0 <1, y (después de Stanley) dejar que J (P) denota el retículo distributivo de los conjuntos inferiores de un orden parcial finita P . Entonces los elementos de J (P) corresponden uno por uno a las funciones de preservación del orden de P a 2 . [2] Porque, si ƒ es una función de este tipo, ƒ −1 (0) forma un conjunto inferior y, a la inversa, si L es un conjunto inferior, se puede definir una función de conservación del orden ƒ L que mapea L a 0 y que mapea el elementos restantes de P a 1. Si g es cualquier función de preservación de orden de Q a P , se puede definir una función g * de J (P) a J (Q) que usa la composición de funciones para mapear cualquier elemento L de J (P) a ƒ L ∘ g . Esta función compuesta mapea Q a 2 y por lo tanto corresponde a un elemento g * ( L ) = (ƒ L ∘ g ) −1 (0) de J (Q) . Además, para cualquier x y y en J (P) , g * ( x ∧ y ) = g * ( x ) ∧ g * ( y ) (un elemento de Q se asigna por g a la inferior conjunto x ∩ y si y solo si pertenece tanto al conjunto de elementos mapeados ax como al conjunto de elementos mapeados a y ) y simétricamente g * ( x ∨ y ) = g * ( x ) ∨ g * ( y ). Además, el elemento inferior de J (P) (la función que asigna todos los elementos de P a 0) se asigna mediante g * al elemento inferior de J (Q) , y el elemento superior de J (P) se asigna mediante g * al elemento superior de J (Q) . Es decir, g * es un homomorfismo de celosías acotadas.
Sin embargo, los elementos de P se corresponden uno por uno con homomorfismos de celosía acotada de J (P) a 2 . Porque, si x es cualquier elemento de P , se puede definir un homomorfismo reticular acotado j x que mapea todos los conjuntos inferiores que contienen xa 1 y todos los demás conjuntos inferiores a 0. Y, para cualquier homomorfismo reticular de J (P) a 2 , los elementos de J (P) que se asignan a 1 deben tener un elemento mínimo único x (la reunión de todos los elementos asignados a 1), que debe ser irreductible por la combinación (no puede ser la combinación de ningún conjunto de elementos asignados a 0 ), por lo que todo homomorfismo de celosía tiene la forma j x para algún x . Una vez más, desde cualquier homomorfismo enrejado limitado h de J (P) a J (Q) se puede utilizar la composición de funciones para definir un orden de preservación mapa h * de Q a P . Se puede verificar que g ** = g para cualquier mapa de preservación del orden g de Q a P y que y h ** = h para cualquier homomorfismo de red acotado h de J (P) a J (Q) .
En terminología teórica de categorías , J es un hom-functor contravariante J = Hom (-, 2 ) que define una dualidad de categorías entre, por un lado, la categoría de órdenes parciales finitos y mapas de preservación de orden, y por otro lado la categoría de celosías distributivas finitas y homomorfismos de celosía acotada.
Generalizaciones
Rejillas distributivas infinitas
En una red distributiva infinita, puede que no sea el caso de que los conjuntos inferiores de los elementos irreductibles de unión estén en correspondencia uno a uno con los elementos de la red. De hecho, es posible que no haya uniones irreductibles en absoluto. Esto sucede, por ejemplo, en la red de todos los números naturales, ordenados con el orden inverso de la divisibilidad habitual (por lo que x ≤ y cuando y divide x ): cualquier número x puede expresarse como la unión de los números xp y xq donde p y q son distintos números primos . Sin embargo, los elementos en celosías distributivas infinitas aún pueden representarse como conjuntos a través del teorema de representación de Stone para celosías distributivas, una forma de dualidad de Stone en la que cada elemento de celosía corresponde a un conjunto abierto compacto en un cierto espacio topológico . Este teorema de representación generalizada se puede expresar como una dualidad teórica de categorías entre retículas distributivas y espacios espectrales (a veces llamados espacios coherentes, pero no lo mismo que los espacios coherentes en lógica lineal ), espacios topológicos en los que los conjuntos abiertos compactos están cerrados bajo intersección. y formar una base para la topología. [3] Hilary Priestley mostró que el teorema de representación de Stone podría interpretarse como una extensión de la idea de representar elementos de celosía mediante conjuntos inferiores de un orden parcial, utilizando la idea de Nachbin de espacios topológicos ordenados. Los espacios de piedra con un orden parcial adicional vinculado con la topología a través del axioma de separación de Priestley también se pueden usar para representar celosías distributivas limitadas. Estos espacios se conocen como espacios de Priestley . Además, ciertos espacios bitopológicos , a saber, los espacios de Stone por parejas , generalizan el enfoque original de Stone al utilizar dos topologías en un conjunto para representar una red distributiva abstracta. Por lo tanto, el teorema de representación de Birkhoff se extiende al caso de retículos distributivos infinitos (acotados) en al menos tres formas diferentes, resumidas en la teoría de la dualidad para retículos distributivos .
El teorema de representación de Birkhoff también puede generalizarse a estructuras finitas distintas de las redes distributivas. En una red distributiva, la operación mediana auto-dual [4]
da lugar a un álgebra mediana , y la relación de cobertura de la celosía forma un gráfico mediano . Las álgebras de medianas finitas y las gráficas de medianas tienen una estructura dual como el conjunto de soluciones de una instancia de satisfacibilidad 2 ; Barthélemy y Constantin (1993) formulan esta estructura de manera equivalente como la familia de conjuntos estables iniciales en un gráfico mixto . [5] Para un retículo distributivo, el gráfico mixto correspondiente no tiene bordes no dirigidos, y los conjuntos estables iniciales son solo los conjuntos inferiores del cierre transitivo del gráfico. De manera equivalente, para una red distributiva, el gráfico de implicaciones de la instancia de 2-satisfacibilidad se puede dividir en dos componentes conectados , uno en las variables positivas de la instancia y el otro en las variables negativas; el cierre transitivo del componente positivo es el orden parcial subyacente de la red distributiva.
Matroides y celosías de unión-distributiva finitas
Otro resultado análogo al teorema de representación de Birkhoff, pero que se aplica a una clase más amplia de retículas, es el teorema de Edelman (1980) de que cualquier retícula distributiva de unión finita puede representarse como un antimatroide , una familia de conjuntos cerrados bajo uniones pero en cuyo cierre bajo intersecciones ha sido reemplazado por la propiedad de que cada conjunto no vacío tiene un elemento removible.
Ver también
- Celosía de emparejamientos estables , que también representa cada celosía distributiva finita
Notas
- ^ Birkhoff (1937) .
- ↑ a b Stanley (1997) .
- ^ Johnstone (1982) .
- ^ Birkhoff y Kiss (1947) .
- ^ Una diferencia menor entre las formulaciones de 2-SAT y el conjunto estable inicial es que este último presupone la elección de un punto base fijo del gráfico mediano que corresponde al conjunto estable inicial vacío.
Referencias
- Barthélemy, J.-P .; Constantin, J. (1993), "Gráficos medianos, paralelismo y posets", Matemáticas discretas , 111 (1-3): 49-63, doi : 10.1016 / 0012-365X (93) 90140-O.
- Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215 / S0012-7094-37-00334-X.
- 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.
- Doignon, J.-P .; Falmagne, J.-Cl. (1999), Espacios de conocimiento , Springer-Verlag, ISBN 3-540-64501-2.
- Edelman, Paul H. (1980), "Meet-distributive lattices y el cierre anti-exchange", Algebra Universalis , 10 (1): 290-299, doi : 10.1007 / BF02482912.
- Johnstone, Peter (1982), "II.3 Locales coherentes", Stone Spaces , Cambridge University Press, págs. 62–69, ISBN 978-0-521-33779-3.
- Priestley, HA (1970), "Representación de celosías distributivas mediante espacios de piedra ordenados", Boletín de la London Mathematical Society , 2 (2): 186-190, doi : 10.1112 / blms / 2.2.186.
- Priestley, HA (1972), "Espacios topológicos ordenados y la representación de celosías distributivas", Proceedings of the London Mathematical Society , 24 (3): 507–530, doi : 10.1112 / plms / s3-24.3.507 , hdl : 10338 .dmlcz / 134149.
- Stanley, RP (1997), Combinatoria enumerativa, Volumen I , Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, págs. 104–112.