Semilattice - Semilattice

En matemáticas , una unión-semirredura (o semirrejilla superior ) es un conjunto parcialmente ordenado que tiene una unión (un límite superior mínimo ) para cualquier subconjunto finito no vacío . Dualmente , una semirreticulación de encuentro (o semirreticulado inferior ) es un conjunto parcialmente ordenado que tiene un encuentro (o límite inferior más grande ) para cualquier subconjunto finito no vacío. Cada semirrejilla de unión es una semirrejilla de reunión en el orden inverso y viceversa.

Las semretículas también se pueden definir algebraicamente : join y meet son operaciones binarias asociativas , conmutativas e idempotentes , y cualquier operación de este tipo induce un orden parcial (y el orden inverso respectivo) de modo que el resultado de la operación para dos elementos cualesquiera sea el límite superior mínimo. (o límite inferior mayor) de los elementos con respecto a este orden parcial.

Una celosía es un conjunto parcialmente ordenado que es a la vez una semirrejilla de unión y de unión con respecto al mismo orden parcial. Algebraicamente, una celosía es un conjunto con dos operaciones binarias asociativas, conmutativas idempotentes vinculadas por las correspondientes leyes de absorción .

Definición de la teoría del orden

Un conjunto S parcialmente ordenado por la relación binaria ≤ es una semirrejilla de encuentro si

Para todos los elementos de x y y de S , el extremo inferior del conjunto { x , y } existe.

El límite inferior más grande del conjunto { x , y } se llama el encuentro de x e y , denotado x ∧ y .

Reemplazar "límite inferior más grande" por " límite superior mínimo " da como resultado el concepto dual de unión-semirrejilla . El límite superior mínimo de { x , y } se llama unión de x e y , denotado x ∨ y . Encuentran y se unen son operaciones binarias en S . Un simple argumento de inducción muestra que la existencia de todos los supremos supremos (infima) por pares posibles, según la definición, implica la existencia de todos los supremos finitos (infima) no vacíos.

Una unión-semirrejilla está acotada si tiene un elemento mínimo , la unión del conjunto vacío. Dualmente , un encuentro-semirreticulado está acotado si tiene un elemento mayor , el encuentro del conjunto vacío.

Se pueden asumir otras propiedades; consulte el artículo sobre completitud en la teoría del orden para obtener más información sobre este tema. Ese artículo también analiza cómo podemos reformular la definición anterior en términos de la existencia de conexiones de Galois adecuadas entre posets relacionados, un enfoque de especial interés para las investigaciones teóricas de categorías del concepto.

Definición algebraica

Un semirretículo-encuentro es una estructura algebraica que consiste en un conjunto S con una operación binaria ∧, llamada encuentro , tal que para todos los miembros x , y y z de S , se cumplen las siguientes identidades : ${\ Displaystyle \ langle S, \ land \ rangle}$

Asociatividad: x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z
Conmutatividad: x ∧ y = y ∧ x
Idempotencia: x ∧ x = x

A conocer-semilattice está delimitada si S incluye un elemento de identidad 1 de tal manera que x ∧ 1 = x para todo x en S . ${\ Displaystyle \ langle S, \ land \ rangle}$

Si el símbolo ∨, llamado unión , reemplaza a ∧ en la definición que se acaba de dar, la estructura se llama unión-semirrejilla . Uno puede ser ambivalente acerca de la elección particular de símbolo para la operación y hablar simplemente de semirretículas .

A semilattice es un conmutativa , idempotente semigrupo ; es decir, una banda conmutativa . Un semirretículo acotado es un monoide conmutativo idempotente .

Se induce un orden parcial en una semirrejilla de encuentro estableciendo x ≤ y siempre que x ∧ y = x . Para una unión-semirrejilla, el orden se induce estableciendo x ≤ y siempre que x ∨ y = y . En una acotada Meet-semilattice, la identidad 1 es el mayor elemento de S . De manera similar, un elemento de identidad en una semirrejilla de unión es un elemento mínimo.

Conexión entre las dos definiciones

Una orden teórico Meet-semilattice ⟨ S , ≤⟩ da lugar a una operación binaria ∧ tal que ⟨ S , ∧⟩ es un meet-semilattice algebraica. A la inversa, el Meet-semilattice ⟨ S , ∧⟩ da lugar a una relación binaria ≤ que parcialmente órdenes de S de la siguiente manera: para todos los elementos x y y en S , x ≤ y si y sólo si x = x ∧ y .

La relación ≤ introducida de esta manera define un ordenamiento parcial a partir del cual se puede recuperar la operación binaria ∧. Por el contrario, la orden inducida por la semilattice algebraicamente definido ⟨ S , ∧⟩ coincide con la inducida por ≤.

Por lo tanto, las dos definiciones pueden usarse indistintamente, dependiendo de cuál sea más conveniente para un propósito particular. Una conclusión similar es válida para las semirretículas de unión y el ordenamiento dual ≥.

Ejemplos de

Las semirretículas se emplean para construir otras estructuras de orden, o junto con otras propiedades de completitud.

Una celosía es a la vez una unión y una unión semirreticulada. La interacción de estas dos semirredes a través de la ley de absorción es lo que realmente distingue a una celosía de una semirreticular.
Los elementos compactos de una red algebraica , bajo el orden parcial inducido, forman una unión-semirrejilla acotada.
Cualquier semirretículo finito está acotado por inducción.
Un conjunto totalmente ordenado es un retículo distributivo , por lo tanto, en particular, un semirreticulado de encuentro y un semirretrato de unión: dos elementos distintos tienen uno mayor y uno menor, que son su encuentro y unión.
- Un conjunto bien ordenado es además una unión-semirrejilla acotada , ya que el conjunto como un todo tiene un elemento mínimo, por lo tanto está acotado.
  - Los enteros no negativos ℕ, con su orden habitual ≤, son una unión-semirrejilla acotada, con el elemento mínimo 0, aunque no tienen el elemento mayor: son el conjunto infinito más pequeño bien ordenado.
Cualquier árbol de una sola raíz (con la raíz única como el elemento mínimo) de altura es una semirrejilla de encuentro (generalmente ilimitada). Considere, por ejemplo, el conjunto de palabras finitas sobre algún alfabeto, ordenadas por orden de prefijo . Tiene un elemento mínimo (la palabra vacía), que es un elemento aniquilador de la operación de encuentro, pero no un elemento mayor (identidad). ${\ Displaystyle \ leq \ omega}$
Un dominio de Scott es una semirrejilla de encuentro.
La pertenencia a cualquier conjunto L puede tomarse como un modelo de una semirred con el conjunto base L , porque una semirrejilla captura la esencia de la extensionalidad del conjunto . Deje un ∧ b denotan un ∈ L y b ∈ L . Dos conjuntos que difieren solo en uno o en ambos:

Orden en el que se enumeran sus miembros;
Multiplicidad de uno o más miembros,

son de hecho el mismo conjunto. Conmutatividad y asociatividad de ∧ asegurar (1), idempotencia , (2). Esta es la semirretículo semirretículo libre sobre l . No está limitado por L , porque un conjunto no es miembro de sí mismo.

La mereología extensional clásica define una unión-semirretículo, con unión leída como fusión binaria. Esta semirrejilla está delimitada desde arriba por el individuo del mundo.
Dado un conjunto S , la colección de particiones de S es una semirrejilla de unión. De hecho, el orden parcial viene dado por if tal que y la unión de dos particiones está dada por . Esta semirrejilla está acotada, siendo el elemento menor la partición singleton . ${\ Displaystyle \ xi}$ ${\ Displaystyle \ xi \ leq \ eta}$ ${\ Displaystyle \ forall Q \ in \ eta, \ existe P \ in \ xi}$ ${\ Displaystyle Q \ subconjunto P}$ ${\ Displaystyle \ xi \ vee \ eta = \ {P \ cap Q \ mid P \ in \ xi \ \ & \ Q \ in \ eta \}}$ ${\ Displaystyle \ {S \}}$

Morfismos de semirreduras

La definición algebraica anterior de semirreticulado sugiere una noción de morfismo entre dos semirreticulos. Dadas dos semirretículas de unión ( S , ∨) y ( T , ∨) , un homomorfismo de (unión-) semirretículas es una función f : S → T tal que

f ( x ∨ y ) = f ( x ) ∨ f ( y ).

Por tanto, f es solo un homomorfismo de los dos semigrupos asociados con cada semirred. Si S y T incluyen al menos un elemento 0, entonces f también debería ser un homomorfismo monoide , es decir, además requerimos que

f (0) = 0.

En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de semirreticulaciones de unión es una función que conserva las uniones binarias y los mínimos elementos, si los hay. El dual obvio, reemplazando ∧ con ∨ y 0 con 1, transforma esta definición de un homomorfismo de unión-semirrejilla en su equivalente de reunión-semirrejilla.

Tenga en cuenta que cualquier homomorfismo de semirred es necesariamente monótono con respecto a la relación de ordenación asociada. Para obtener una explicación, consulte la preservación de los límites de la entrada .

Equivalencia con celosías algebraicas

Existe una equivalencia bien conocida entre la categoría de semirreticulos de unión con cero con -homomorfismos y la categoría de celosías algebraicas con compacidad -preservando homomorfismos de unión completos, como sigue. Con una unión-semirrejilla con cero, asociamos su celosía ideal . Con un -homomorfismo de -semilattices, asociamos el mapa , que con cualquier ideal de asocia el ideal de generado por . Esto define un funtor . A la inversa, con cada retícula algebraica asociamos la semirrejilla de todos los elementos compactos de , y con cada homomorfismo de unión completo que conserva la compacidad entre las retículas algebraicas asociamos la restricción . Esto define un funtor . El par define una equivalencia de categoría entre y . ${\ Displaystyle {\ mathcal {S}}}$ ${\ Displaystyle (\ vee, 0)}$ ${\ Displaystyle {\ mathcal {A}}}$ ${\ Displaystyle S}$ ${\ Displaystyle \ operatorname {Id} \ S}$ ${\ Displaystyle (\ vee, 0)}$ ${\ Displaystyle f \ colon S \ to T}$ ${\ Displaystyle (\ vee, 0)}$ ${\ Displaystyle \ operatorname {Id} \ f \ colon \ operatorname {Id} \ S \ to \ operatorname {Id} \ T}$ ${\ Displaystyle I}$ ${\ Displaystyle S}$ ${\ Displaystyle T}$ ${\ Displaystyle f (I)}$ ${\ Displaystyle \ operatorname {Id} \ colon {\ mathcal {S}} \ to {\ mathcal {A}}}$ ${\ Displaystyle A}$ ${\ Displaystyle (\ vee, 0)}$ ${\ Displaystyle K (A)}$ ${\ Displaystyle A}$ ${\ Displaystyle f \ colon A \ to B}$ ${\ Displaystyle K (f) \ dos puntos K (A) \ a K (B)}$ ${\ Displaystyle K \ colon {\ mathcal {A}} \ to {\ mathcal {S}}}$ ${\ displaystyle (\ operatorname {Id}, K)}$ ${\ Displaystyle {\ mathcal {S}}}$ ${\ Displaystyle {\ mathcal {A}}}$

Semirretículos distributivos

Sorprendentemente, existe una noción de "distributividad" aplicable a las semirreduras, aunque la distributividad requiere convencionalmente la interacción de dos operaciones binarias. Esta noción requiere una sola operación y generaliza la condición de distributividad para las celosías. Una semirrejilla de unión es distributiva si para todo a , b y x con x ≤ a ∨ b existen a ' ≤ a y b' ≤ b tales que x = a ' ∨ b' . Las semirreticulaciones de encuentro distributivas se definen dualmente. Estas definiciones se justifican por el hecho de que cualquier semirretículo de unión distributiva en el que existan encuentros binarios es un retículo distributivo. Consulte la distributividad de entrada (teoría del orden) .

Una semirrejilla de unión es distributiva si y solo si la rejilla de sus ideales (bajo inclusión) es distributiva.

Semirretillas completas

Hoy en día, el término "semirred completa" no tiene un significado generalmente aceptado, y existen varias definiciones mutuamente inconsistentes. Si se considera que la completitud requiere la existencia de todas las uniones infinitas, o todas las uniones infinitas, cualquiera que sea el caso, así como las finitas, esto conduce inmediatamente a órdenes parciales que son de hecho retículas completas . Para saber por qué la existencia de todas las combinaciones infinitas posibles implica la existencia de todas las combinaciones infinitas posibles (y viceversa), consulte la completitud de la entrada (teoría del orden) .

Sin embargo, la literatura en ocasiones todavía considera que las semirredes de unión o encuentro completas son celosías completas. En este caso, "completitud" denota una restricción en el alcance de los homomorfismos . Específicamente, una semirrejilla de unión completa requiere que los homomorfismos conserven todas las uniones, pero contrariamente a la situación que encontramos para las propiedades de completitud, esto no requiere que los homomorfismos conserven todas las uniones. Por otro lado, podemos concluir que cada mapeo de este tipo es el adjunto inferior de alguna conexión de Galois . El adjunto superior correspondiente (único) será entonces un homomorfismo de semirretículos de encuentro completos. Esto da lugar a una serie de útiles dualidades categóricas entre las categorías de todas las semirretículas completas con morfismos que preservan todos los encuentros o uniones, respectivamente.

Otro uso de "completo encuentro-semilattice" se refiere a un cpo completo acotado . En este sentido, una semirrejilla de encuentro completa es posiblemente la semirrejilla de encuentro "más completa" que no es necesariamente una retícula completa. De hecho, una semirrejilla de encuentro completa tiene todas las reuniones no vacías (lo que equivale a estar acotado completo) y todas las combinaciones dirigidas . Si tal estructura tiene también un elemento más grande (el encuentro del conjunto vacío), también es una celosía completa. Por lo tanto, una semirrejilla completa resulta ser "una celosía completa que posiblemente carece de una parte superior". Esta definición es de interés específicamente en la teoría de dominios , donde los cpos algebraicos completos acotados se estudian como dominios de Scott . Por lo tanto, los dominios de Scott se han denominado semirretículos algebraicos .

Las nociones de completitud restringidas por cardinalidad para semirretículos rara vez se han considerado en la literatura.

Semirretices libres

Esta sección presupone cierto conocimiento de la teoría de categorías . En diversas situaciones, existen semirretículos libres . Por ejemplo, el functor olvidadizo de la categoría de semirreticulados de unión (y sus homomorfismos) a la categoría de conjuntos (y funciones) admite un adjunto izquierdo . Por lo tanto, la unión libre-semirrejilla F ( S ) sobre un conjunto S se construye tomando la colección de todos los subconjuntos finitos no vacíos de S , ordenados por inclusión de subconjuntos. Claramente, S se puede incrustar en F ( S ) mediante un mapeo e que lleva cualquier elemento s en S al conjunto singleton { s }. Entonces, cualquier función f desde una S a una unión-semirreticulado T (más formalmente, al conjunto subyacente de T ) induce un homomorfismo único f ' entre las uniones-semirreticulado F ( S ) y T , tal que f = f' o e . Explícitamente, f ' viene dada por f' ( A ) = { f ( s ) | s en A }. Ahora bien, la unicidad obvia de f ' basta para obtener la adjunción requerida —la parte de morfismo— del funtor F puede derivarse de consideraciones generales (véanse los functores adjuntos ). El caso de las semirretículas de encuentro libre es dual, utilizando la inclusión del subconjunto opuesto como orden. Para las uniones semirretículas con fondo, simplemente agregamos el conjunto vacío a la colección de subconjuntos anterior. ${\ Displaystyle \ vee}$

Además, las semirreticulaciones a menudo sirven como generadores de objetos libres dentro de otras categorías. En particular, tanto los functores olvidadizos de la categoría de marcos y homomorfismos de marcos , como de la categoría de retículas distributivas y homomorfismos de retículas, tienen un adjunto izquierdo.

Ver también

Conjunto dirigido , generalización de semirrejilla de unión.
Lista de temas de pedidos
Semiring

Notas

Referencias

Davey, BA; Priestley, HA (2002). Introducción a las celosías y el orden (segunda ed.). Prensa de la Universidad de Cambridge . ISBN 0-521-78451-4 .
Vickers, Steven (1989). Topología vía lógica . Prensa de la Universidad de Cambridge . ISBN 0-521-36062-5 . CS1 maint: parámetro desalentado ( enlace )

A menudo ocurre que los tratamientos estándar de la teoría de la celosía definen una semirrejilla, si es así, y luego no dicen nada más. Consulte las referencias en la teoría del orden de las entradas y la teoría de la red . Además, no hay literatura sobre semirreduras de magnitud comparable a la de semigrupos .

enlaces externos

Página de estructuras de álgebra de Jipsen : Semretículos.

Languages

In other projects