En matemáticas , una semired de unión (o semired 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 semired de encuentro (o semired inferior ) es un conjunto parcialmente ordenado que tiene un encuentro (o límite inferior máximo ) para cualquier subconjunto finito no vacío. Cada semirrejilla de unión es una semirrejilla de encuentro en orden inverso y viceversa.
Las semiredes también se pueden definir algebraicamente : unirse y reunirse son operaciones binarias asociativas , conmutativas e idempotentes , y cualquier operación de este tipo induce un orden parcial (y el respectivo orden inverso) 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 red es un conjunto parcialmente ordenado que es a la vez una semired de encuentro y de unión con respecto al mismo orden parcial. Algebraicamente, una red es un conjunto con dos operaciones binarias idempotentes conmutativas y asociativas unidas por las correspondientes leyes de absorción .
Un conjunto S parcialmente ordenado por la relación binaria ≤ es una semired de encuentro si
El límite inferior mayor del conjunto { x , y } se llama encuentro de xey , denotado x ∧ y .
Reemplazar el "límite inferior mayor" por el " límite superior mínimo " da como resultado el concepto dual de semirrejilla de unión . El límite superior mínimo de { x , y } se llama unión de x e y , denotado x ∨ y . Meet y join son operaciones binarias en S . Un argumento de inducción simple muestra que la existencia de todos los supremas (infima) por pares posibles, según la definición, implica la existencia de todos los supremas (infima) finitos no vacíos.
Una semired de unión está acotada si tiene un elemento mínimo , la unión del conjunto vacío. Dualmente , una semired de encuentro está acotada si tiene un elemento mayor , el encuentro del conjunto vacío.
Se pueden suponer otras propiedades; consulte el artículo sobre la teoría de la integridad en el 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 del concepto en teoría de categorías .
Una semirretícula de encuentro es una estructura algebraica que consta de un conjunto S con una operación binaria ∧ , llamada encuentro , tal que para todos los miembros x , y y z de S , se mantienen las siguientes identidades :
Una semirretícula de encuentro está acotada si S incluye un elemento de identidad 1 tal que x ∧ 1 = x para todo x en S .
Si el símbolo ∨ , llamado unión , reemplaza a ∧ en la definición que acabamos de dar, la estructura se llama semirrejilla de unión . Uno puede ser ambivalente acerca de la elección particular del símbolo para la operación y hablar simplemente de semiredes .
Una semired es un semigrupo conmutativo e idempotente ; es decir, una banda conmutativa . Una semired acotada es un monoide conmutativo idempotente .
Se induce un orden parcial en una semired de encuentro estableciendo x ≤ y siempre que x ∧ y = x . Para una semired de unión, el orden se induce estableciendo x ≤ y siempre que x ∨ y = y . En una semired de encuentro acotada, la identidad 1 es el mayor elemento de S. De manera similar, un elemento de identidad en una semired de unión es un elemento mínimo.
Una semirrejilla de encuentro teórica de orden ⟨ S , ≤⟩ da lugar a una operación binaria ∧ tal que ⟨ S , ∧⟩ es una semirrejilla de encuentro algebraica. Por el contrario, la semired de encuentro ⟨ S , ∧⟩ da lugar a una relación binaria ≤ que ordena parcialmente S de la siguiente manera: para todos los elementos x e y en S , x ≤ y si y solo si x = x ∧ y .
La relación ≤ así introducida define un ordenamiento parcial del que se puede recuperar la operación binaria ∧ . Por el contrario, el orden inducido por la semired definida algebraicamente ⟨ S , ∧⟩ coincide con el inducido 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 semiredes de unión y el orden dual ≥.
Las semiredes se emplean para construir otras estructuras de orden o en conjunto con otras propiedades de completitud.
La definición algebraica anterior de semired sugiere una noción de morfismo entre dos semiredes. Dadas dos semirrejillas de unión ( S , ∨) y ( T , ∨) , un homomorfismo de semirrejillas (de unión) es una función f : S → T tal que
Por tanto, f es simplemente un homomorfismo de los dos semigrupos asociados con cada semired. Si S y T incluyen al menos el elemento 0, entonces f también debería ser un homomorfismo monoide , es decir, requerimos adicionalmente que
En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de semiredes de unión es una función que preserva las uniones binarias y los elementos mínimos, si los hay. El dual obvio (reemplazar ∧ con ∨ y 0 con 1) transforma esta definición de homomorfismo de semired de unión en su equivalente de semired de encuentro.
Tenga en cuenta que cualquier homomorfismo de semired es necesariamente monótono con respecto a la relación de orden asociada. Para obtener una explicación, consulte la entrada preservación de límites .
Existe una equivalencia bien conocida entre la categoría de semiredes de unión con cero con homomorfismos y la categoría de celosías algebraicas con homomorfismos de unión completos que preservan la compacidad , como se muestra a continuación. Con una semired de unión con cero, asociamos su red ideal . Con un -homomorfismo de -semiredes, asociamos el mapa , que con cualquier ideal de asocia el ideal de generado por . Esto define un funtor . Por el contrario, con cada red algebraica asociamos la -semired de todos los elementos compactos de , y con cada homomorfismo de unión completo que preserva la compacidad entre redes algebraicas asociamos la restricción . Esto define un funtor . El par define una equivalencia de categoría entre y .
Sorprendentemente, existe una noción de "distributividad" aplicable a las semiredes, aunque la distributividad convencionalmente requiere la interacción de dos operaciones binarias. Esta noción requiere una sola operación y generaliza la condición de distributividad para las redes. Una semired de unión es distributiva si para todos a , b y x con x ≤ a ∨ b existen a' ≤ a y b ' ≤ b tales que x = a' ∨ b' . Las semirretículas distributivas se definen de forma dual. Estas definiciones se justifican por el hecho de que cualquier semirrejilla de unión distributiva en la que existan encuentros binarios es una red distributiva. Ver la entrada distributividad (teoría del orden) .
Una semired conjunta es distributiva si y sólo si la red de sus ideales (bajo inclusión) es distributiva.
Hoy en día, el término "semired 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, de hecho, son redes completas . Para saber por qué la existencia de todas las uniones infinitas posibles implica la existencia de todas las uniones infinitas posibles (y viceversa), consulte la entrada Completitud (teoría del orden) .
Sin embargo, en ocasiones la literatura todavía considera que las semirrejillas 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 semired 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 semirrejillas de encuentro completas. Esto da lugar a una serie de dualidades categóricas útiles entre las categorías de todas las semiredes completas con morfismos que preservan todos los encuentros o uniones, respectivamente.
Otro uso de "reunión-semirrejilla completa" se refiere a un cpo completo acotado . Una semirretícula de encuentro completa en este sentido es posiblemente la semirretícula de encuentro "más completa" que no es necesariamente una red completa. De hecho, una semirretícula de encuentro completa tiene todos los encuentros no vacíos (lo que equivale a estar acotado por completo) y todas las uniones dirigidas . Si tal estructura tiene también un elemento mayor (el encuentro del conjunto vacío), también es una red completa. Por lo tanto, una semired completa resulta ser "una red completa que posiblemente carece de 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 . De ahí que los dominios de Scott hayan sido denominados semiredes algebraicas .
Las nociones de completitud restringidas por cardinalidad para semiredes rara vez se han considerado en la literatura. [1]
Esta sección presupone algunos conocimientos de la teoría de categorías . En diversas situaciones existen semiredes libres . Por ejemplo, el functor olvidadizo de la categoría de semirrejillas de unión (y sus homomorfismos) a la categoría de conjuntos (y funciones) admite un adjunto izquierdo . Por lo tanto, la semired de unión libre 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 de S a una semirrejilla de unión T (más formalmente, al conjunto subyacente de T ) induce un homomorfismo único f' entre las semirrejillas de unión F ( S ) y T , tal que f = f' ○ e . Explícitamente, f' está dada por Ahora, la unicidad obvia de f' es suficiente para obtener la conjunción requerida: la parte de morfismo del funtor F puede derivarse de consideraciones generales (ver funtores adjuntos ). El caso de las semirretículas de encuentro libres es dual, y utiliza la inclusión del subconjunto opuesto como ordenamiento. Para semirrejillas de unión con fondo, simplemente agregamos el conjunto vacío a la colección de subconjuntos anterior.
Además, las semiredes suelen servir 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 redes distributivas y homomorfismos de redes, tienen un adjunto izquierdo.
A menudo ocurre que los tratamientos estándar de la teoría de la red definen una semired, en todo caso, y luego no dicen nada más. Véanse las referencias en las entradas teoría del orden y teoría de la red . Además, no existe literatura sobre semiredes de magnitud comparable a la de semigrupos .
