Teorema de representación de Birkhoff

Esto trata sobre la teoría de retículos . Para otros resultados con nombres similares, véase el teorema de Birkhoff (desambiguación) .

En matemáticas , el teorema de representación de Birkhoff para retículos distributivos establece que los elementos de cualquier retículo distributivo finito pueden representarse como conjuntos finitos , de tal manera que las operaciones del retículo corresponden a uniones e intersecciones de conjuntos. Aquí, un retículo es una estructura abstracta con dos operaciones binarias , las operaciones de "encuentro" y "unión", que deben obedecer ciertos axiomas; es distributivo si estas dos operaciones obedecen la ley distributiva . Las operaciones de unión e intersección, en una familia de conjuntos que es cerrada bajo estas operaciones, forman automáticamente un retículo distributivo, y el teorema de representación de Birkhoff establece que (salvo isomorfismo) todo retículo distributivo finito puede formarse de esta manera. Recibe su nombre de Garrett Birkhoff , quien publicó una demostración del mismo en 1937. ^{[ 1 ]}

El teorema puede interpretarse como una correspondencia biunívoca entre retículos distributivos y órdenes parciales , entre espacios de conocimiento cuasi-ordinales y preórdenes , o entre espacios topológicos finitos y preórdenes.

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 booleanas como familias de conjuntos cerradas bajo unión, intersección y complemento (los llamados cuerpos de conjuntos , estrechamente relacionados con los anillos de conjuntos utilizados por Birkhoff para representar retículos distributivos), 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 para retículos distributivos finitos . ^{[ 2 ]}

Muchas retículas pueden definirse de tal manera que sus elementos se representen mediante conjuntos, la operación de unión se represente mediante la unión de conjuntos y la operación de intersección mediante la intersección de conjuntos. Por ejemplo, la retícula booleana definida a partir de la familia de todos los subconjuntos de un conjunto finito posee esta propiedad. De forma más general, cualquier espacio topológico finito tiene una retícula de conjuntos como su familia de conjuntos abiertos. Dado que las uniones e intersecciones de conjuntos obedecen la ley distributiva , cualquier retícula definida de esta manera es una retícula distributiva. El teorema de Birkhoff afirma que, de hecho, todas las retículas distributivas finitas pueden obtenerse de esta forma, y ​​generalizaciones posteriores del teorema de Birkhoff establecen algo similar para retículas distributivas infinitas.

Consideremos los divisores de algún número compuesto , como (en la figura) 120, parcialmente ordenados por divisibilidad. Cualquier par de divisores de 120, como 12 y 20, tienen un único máximo común divisor 12  ∧  20  =  4, el mayor número que los divide a ambos, y un único mínimo común múltiplo 12  ∨  20  =  60; ambos números también son divisores de 120. Estas dos operaciones ∨ y ∧ satisfacen la ley distributiva, en cualquiera de 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 lo tanto, los divisores forman una red distributiva finita .                       

Se puede asociar cada divisor con el conjunto de potencias primas que lo dividen: así, 12 se asocia con el conjunto {2,3,4}, mientras que 20 se asocia con el conjunto {2,4,5}. Entonces, 12  ∧  20  =  4 se asocia con el conjunto {2,3,4}  ∩  {2,4,5}  =  {2,4}, mientras que 12  ∨  20  =  60 se asocia con el conjunto {2,3,4}  ∪  {2,4,5}  =  {2,3,4,5}, por lo que las operaciones de unión e intersección del retículo corresponden a la unión e intersección de conjuntos.

Las potencias primas 2, 3, 4, 5 y 8 que aparecen como elementos en estos conjuntos pueden estar parcialmente ordenadas 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 subconjuntos de este orden parcial más pequeño, subconjuntos de elementos tales que si x ≤ y y y pertenece al subconjunto, entonces x también debe pertenecer al subconjunto. A partir de cualquier subconjunto L , se puede recuperar el divisor asociado calculando el mínimo común múltiplo de las potencias primas en L. Por lo tanto, el orden parcial en las cinco potencias primas 2, 3, 4, 5 y 8 contiene suficiente información para recuperar toda la red de divisibilidad original de 16 elementos.

El teorema de Birkhoff establece que esta relación entre las operaciones ∧ y ∨ del retículo de divisores y las operaciones ∩ y ∪ de los conjuntos asociados de potencias primas no es casual ni depende de las propiedades específicas de los números primos y la divisibilidad: los elementos de cualquier retículo distributivo finito pueden asociarse con conjuntos inferiores de un orden parcial de la misma manera.

Como otro ejemplo, consideremos el retículo de subconjuntos de un conjunto de n elementos, parcialmente ordenado por inclusión. El teorema de Birkhoff muestra que este retículo se produce mediante los conjuntos inferiores del retículo distributivo libre sobre n generadores, cuyo número de elementos viene dado por los números de Dedekind .

En un retículo, un elemento x es irreducible por unión si x no es la unión de un conjunto finito de otros elementos. De forma equivalente, x es irreducible por unión si no es ni el elemento inferior del retículo (la unión de cero elementos) ni la unión de dos elementos menores cualesquiera. Por ejemplo, en el retículo de divisores de 120, no hay ningún par de elementos cuya unión sea 4, por lo que 4 es irreducible por unión. Un elemento x es primo por unión si difiere del elemento inferior y siempre que x  ≤ y ∨ z , entonces x ≤ y o x ≤ z . En el mismo retículo, 4 es primo por unión: siempre que mcm( y , z ) sea divisible por 4, al menos uno de y o z debe ser divisible por 4.       

En cualquier retículo, un elemento join-prime debe ser join-irreducible. De forma equivalente, un elemento que no es join-irreducible no es join-prime. Pues, si un elemento x no es join-irreducible, existen elementos y y z menores tales que x  = y ∨ z . Pero entonces x ≤ y ∨ z , y x no es menor ni igual que y ni que z , lo que demuestra que no es join-prime.       

Existen retículos en los que los elementos de unión primos forman un subconjunto propio de los elementos de unión irreducibles, pero en un retículo distributivo los dos tipos de elementos coinciden. Por ejemplo, supongamos que x es de unión irreducible y que x  ≤ y ∨ z . Esta desigualdad es equivalente a la afirmación de que x = x ∧ ( y ∨ z ), y por la ley distributiva x = ( x ∧ y ) ∨ ( x ∧ z ). Pero como x es de unión irreducible, al menos uno de los dos términos en esta unión debe ser x mismo, lo que demuestra que o bien x = x ∧ y (equivalentemente x ≤ y ) o bien x = x ∧ z (equivalentemente x ≤ z ).                             

El ordenamiento reticular en el subconjunto de elementos irreducibles por unión forma un orden parcial ; el teorema de Birkhoff establece que el propio retículo puede recuperarse a partir de los conjuntos inferiores de este orden parcial.

En cualquier orden parcial, los conjuntos inferiores forman un retículo en el que el orden parcial viene dado por la inclusión de conjuntos, la operación de unión corresponde a la unión de conjuntos y la operación de intersección corresponde a la intersección de conjuntos, ya que las uniones e intersecciones conservan la propiedad de ser un conjunto inferior. Dado que las uniones e intersecciones de conjuntos obedecen la ley distributiva, se trata de un retículo distributivo. El teorema de Birkhoff establece que cualquier retículo distributivo finito puede construirse de esta manera.

Teorema . Cualquier retículo distributivo finito L es isomorfo al retículo de conjuntos inferiores del orden parcial de los elementos irreducibles por unión de L .

Es decir, existe una correspondencia biunívoca que preserva 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 de L irreducibles por unión que son menores o iguales a x , y el elemento de L correspondiente a un conjunto inferior S de elementos irreducibles por unión es la unión de S.

Para cualquier conjunto inferior S de elementos irreducibles por unión, sea x la unión de S , y sea T el conjunto inferior de los elementos irreducibles por unión menores o iguales a x . Entonces S  = T. Porque, cada elemento de S pertenece claramente a T , y cualquier elemento irreducible por unión menor o igual a x debe (por primalidad de unión) ser menor o igual a uno de los miembros de S , y por lo tanto debe (por la suposición de que S es un conjunto inferior) pertenecer a S mismo. Recíprocamente, para cualquier elemento x de L , sea S los elementos irreducibles por unión menores o iguales a x , y sea y la unión de S. Entonces x = y . Porque, como una unión de elementos menores o iguales a x , y no puede ser mayor que x mismo, pero si x es irreducible por unión entonces x pertenece a S mientras que si x es la unión de dos o más elementos irreducibles por unión entonces deben pertenecer nuevamente a S , por lo que y ≥ x . Por lo tanto, la correspondencia es biunívoca y el teorema queda demostrado.     

Birkhoff (1937) definió un anillo de conjuntos como una familia de conjuntos cerrada bajo las operaciones de unión e intersección de conjuntos; posteriormente, motivados por aplicaciones en psicología matemática , Doignon y Falmagne (1999) denominaron a esta misma estructura espacio de conocimiento cuasi-ordinal . Si los conjuntos de un anillo de conjuntos se ordenan por inclusión, forman un retículo distributivo. A los elementos de los conjuntos se les puede asignar un preorden tal que x  ≤ y siempre que algún conjunto del anillo contenga x pero no y . El anillo de conjuntos es entonces la familia de conjuntos inferiores de este preorden, y cualquier preorden da lugar a un anillo de conjuntos de esta manera. 

El teorema de Birkhoff, como se mencionó anteriormente, establece una correspondencia entre órdenes parciales individuales y retículos distributivos. Sin embargo, también puede extenderse a una correspondencia entre funciones que preservan el orden de los órdenes parciales y homomorfismos acotados de los retículos distributivos correspondientes. En esta correspondencia, la dirección de estas aplicaciones se invierte.

Sea 2 el orden parcial en el conjunto de dos elementos {0, 1}, con la relación de orden 0 < 1, y (siguiendo a Stanley) sea J(P) el retículo distributivo de conjuntos inferiores de un orden parcial finito P. Entonces los elementos de J(P) corresponden uno a uno a las funciones que preservan el orden de ^{P a 2. [ 2} ] Porque , ^si ƒ ^es tal función, ƒ ⁻¹ (0) forma un conjunto inferior, y recíprocamente si L es un conjunto inferior se puede definir una función que preserva el orden ƒ _L que mapea L a 0 y que mapea los elementos restantes de P a 1. Si g es cualquier función que preserva el 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 asigna Q a 2 y, por lo tanto, corresponde a un elemento g *( L ) = (ƒ _L ∘ g ) ⁻¹ (0) de J(Q) . Además, para cualesquiera x e y en J(P) , g *( x ∧ y ) = g *( x ) ∧ g *( y ) (un elemento de Q es asignado por g al conjunto inferior x ∩ y si y solo si pertenece tanto al conjunto de elementos asignados a x como al conjunto de elementos asignados a y ) y simétricamente g *( x ∨ y ) = g *( x ) ∨ g *( y ). Adicionalmente, el elemento inferior de J(P) (la función que asigna todos los elementos de P a 0) es asignado por g * al elemento inferior de J(Q) , y el elemento superior de J(P) es asignado por g * al elemento superior de J(Q) . Es decir, g                   * es un homomorfismo de retículos acotados.

Sin embargo, los elementos de P se corresponden uno a uno con homomorfismos de retículos acotados de J(P) a 2. Porque, si x es cualquier elemento de P , se puede definir un homomorfismo de retículos acotado j _x que mapea todos los conjuntos inferiores que contienen x a 1 y todos los demás conjuntos inferiores a 0. Y, para cualquier homomorfismo de retículos de J(P) a 2 , los elementos de J(P) que se mapean a 1 deben tener un único elemento mínimo x (la intersección de todos los elementos mapeados a 1), que debe ser irreducible por unión (no puede ser la unión de ningún conjunto de elementos mapeados a 0), por lo que todo homomorfismo de retículos tiene la forma j _x para algún x . Nuevamente, a partir de cualquier homomorfismo de retículos acotado h de J(P) a J(Q) se puede usar la composición de funciones para definir un mapeo que preserva el orden h * de Q a P. Se puede verificar que g **  = g para cualquier aplicación g que preserve el orden de Q a P y que h ** = h para cualquier homomorfismo reticular acotado h de J(P) a J(Q) .   

En la terminología de la teoría 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 aplicaciones que preservan el orden, y por otro lado la categoría de retículos distributivos finitos y homomorfismos de retículos acotados.

• Retículo de emparejamientos estables , que también representa todo retículo distributivo finito.

• Barthélemy, J.-P.; Constantin, J. (1993), "Grafos medianos, paralelismo y conjuntos parcialmente ordenados", Matemáticas Discretas , 111 ( 1–3 ): 49–63 , doi : 10.1016/0012-365X(93)90140-O.
• Birkhoff, Garrett (1937), "Anillos de conjuntos", 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 retículos distributivos" , Bulletin of the 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), "Retículos distributivos de encuentro y el cierre anti-intercambio", Algebra Universalis , 10 (1): 290–299 , doi : 10.1007/BF02482912.
• Johnstone, Peter (1982), "II.3 Lugares coherentes", Stone Spaces , Cambridge University Press, pp. 62–69 , ISBN  978-0-521-33779-3.
• Priestley, HA (1970), "Representación de retículos distributivos mediante espacios de Stone ordenados", Bulletin of the 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 retículos distributivos", Actas de la Sociedad Matemática de Londres , 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, pp . 104–112 .