En matemáticas , un semirretículo de unión (o semirretículo superior ) es un conjunto parcialmente ordenado que tiene un conjunto de unión (un límite superior mínimo ) para cualquier subconjunto finito no vacío . Dualmente , un semirretículo de encuentro (o semirretículo inferior ) es un conjunto parcialmente ordenado que tiene un encuentro (o límite inferior máximo ) para cualquier subconjunto finito no vacío. Cada semirretículo de unión es un semirretículo de encuentro en el orden inverso y viceversa.
Las semirredes también se pueden definir algebraicamente : unir y encontrarse son operaciones binarias asociativas , conmutativas e idempotentes , y cualquier operación de este tipo induce un orden parcial (y el respectivo orden inverso) tal que el resultado de la operación para cualesquiera dos elementos es el límite superior menor (o el 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 semirretícula 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 vinculadas por leyes de absorción correspondientes .
Un conjunto S parcialmente ordenado por la relación binaria ≤ es un semirretículo de encuentro si
El límite inferior máximo del conjunto { x , y } se denomina encuentro de x e y , denotado x ∧ y .
Reemplazar "máximo límite inferior" por " mínimo límite superior " da como resultado el concepto dual de semirretículo de unión . El mínimo límite superior de { x , y } se denomina unión de x e y , denotado x ∨ y . El encuentro y la unión son operaciones binarias en S . Un argumento de inducción simple muestra que la existencia de todos los suprema (ínfimos) posibles por pares, según la definición, implica la existencia de todos los suprema (ínfimos) finitos no vacíos.
Un semirretículo de unión está acotado si tiene un elemento menor , el de unión del conjunto vacío. Dualmente , un semirretículo de encuentro está acotado si tiene un elemento mayor , el de encuentro del conjunto vacío.
Se pueden suponer otras propiedades; véase el artículo sobre completitud en la teoría del orden para 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 conjuntos de elementos relacionados, un enfoque de especial interés para las investigaciones de la teoría de categorías del concepto.
Un semirretículo de 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 :
Una semirretícula de encuentro está acotada si S incluye un elemento identidad 1 tal que x ∧ 1 = x para todo x en S.
Si el símbolo ∨ , llamado join , reemplaza a ∧ en la definición que acabamos de dar, la estructura se denomina semirretículo de join . Se puede ser ambivalente en cuanto a la elección particular del símbolo para la operación y hablar simplemente de semirretículos .
Una semirretícula es un semigrupo conmutativo e idempotente ; es decir, una banda conmutativa . Una semirretícula acotada es un monoide conmutativo idempotente .
Se induce un orden parcial en un semirretículo de encuentro estableciendo x ≤ y siempre que x ∧ y = x . Para un semirretículo de unión, el orden se induce estableciendo x ≤ y siempre que x ∨ y = y . En un semirretículo de encuentro acotado, la identidad 1 es el elemento mayor de S . De manera similar, un elemento identidad en un semirretículo de unión es un elemento menor.
Un semirretículo de encuentro teórico de orden ⟨ S , ≤⟩ da lugar a una operación binaria ∧ tal que ⟨ S , ∧⟩ es un semirretículo de encuentro algebraico. Por el contrario, el semirretículo 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 ≤ introducida de esta manera define un ordenamiento parcial a partir del cual se puede recuperar la operación binaria ∧ . Por el contrario, el orden inducido por la semirretícula 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 se aplica a los semirretículos de unión y al ordenamiento dual ≥.
Las semirredes se emplean para construir otras estructuras de orden o en conjunción con otras propiedades de completitud.
La definición algebraica anterior de un semirretículo sugiere una noción de morfismo entre dos semirretículos. Dados dos semirretículos de unión ( S , ∨) y ( T , ∨) , un homomorfismo de semirretículos (de unión) es una función f : S → T tal que
Por lo tanto, f es simplemente un homomorfismo de los dos semigrupos asociados con cada semirretículo. Si S y T incluyen ambos un elemento mínimo 0, entonces f también debería ser un homomorfismo monoide , es decir, además requerimos que
En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de semirretículos de unión es una función que preserva los semirretículos de unión y los elementos mínimos, si los hay. El dual obvio (reemplazar ∧ por ∨ y 0 por 1) transforma esta definición de un homomorfismo de semirretículo de unión en su equivalente de semirretículo de encuentro.
Obsérvese que cualquier homomorfismo de semirretículo es necesariamente monótono con respecto a la relación de ordenación asociada. Para una explicación, véase la entrada sobre conservación de límites .
Existe una equivalencia bien conocida entre la categoría de semirretículos de unión con cero con -homomorfismos y la categoría de retículos algebraicos con homomorfismos de unión completos que preservan la compacidad , como sigue. Con un semirretículo de unión con cero, asociamos su retículo ideal . Con un -homomorfismo de -semirretículos, asociamos la función , que con cualquier ideal de asocia el ideal de generado por . Esto define un funtor . Por el contrario, con cada retículo algebraico asociamos el -semirretículo de todos los elementos compactos de , y con cada homomorfismo de unión completo que preserva la compacidad entre retículos algebraicos 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 los semirretículos, aunque la distributividad convencionalmente requiere la interacción de dos operaciones binarias. Esta noción requiere sólo una única operación y generaliza la condición de distributividad para los retículos. Un semirretículo de unión es distributivo si para todos a , b y x con x ≤ a ∨ b existen a ' ≤ a y b ' ≤ b tales que x = a ' ∨ b ' . Los semirretículos de encuentro distributivos se definen dualmente. Estas definiciones se justifican por el hecho de que cualquier semirretículo de unión distributivo en el que existen encuentros binarios es un retículo distributivo. Véase la entrada distributividad (teoría del orden) .
Una semirretícula de unión es distributiva si y sólo si la red de sus ideales (bajo inclusión) es distributiva.
En la actualidad, el término "semirretículo completo" 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 todos los encuentros infinitos, según sea el caso, así como de los finitos, esto conduce inmediatamente a órdenes parciales que son, de hecho, retículos completos . Para saber por qué la existencia de todas las posibles uniones infinitas implica la existencia de todos los posibles encuentros infinitos (y viceversa), véase la entrada completitud (teoría del orden) .
Sin embargo, en ocasiones la literatura todavía considera que los semirretículos de unión o encuentro completos son retículos completos. En este caso, "completitud" denota una restricción en el alcance de los homomorfismos . Específicamente, un semirretículo de unión completo requiere que los homomorfismos preserven todos los encuentros, pero al contrario de la situación que encontramos para las propiedades de completitud, esto no requiere que los homomorfismos preserven todos los encuentros. Por otro lado, podemos concluir que cada una de estas aplicaciones 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 dualidades categóricas útiles entre las categorías de todos los semirretículos completos con morfismos que preservan todos los encuentros o las uniones, respectivamente.
Otro uso de "semirretículo completo" se refiere a un cpo completo acotado . Un semirretículo completo en este sentido es posiblemente el semirretículo "más completo" que no es necesariamente un retículo completo. De hecho, un semirretículo completo tiene todos los encuentros no vacíos (lo que equivale a ser completo acotado) y todas las uniones dirigidas . Si una estructura de este tipo tiene también un elemento mayor (el encuentro del conjunto vacío), también es un retículo completo. Por lo tanto, un semirretículo completo resulta ser "un retículo completo al que posiblemente le falte un vértice". Esta definición es de interés específicamente en la teoría de dominios , donde los cpo algebraicos completos acotados se estudian como dominios de Scott . Por lo tanto, los dominios de Scott se han llamado semirretículos algebraicos .
En la literatura rara vez se han considerado nociones de completitud restringidas por cardinalidad para semirretículos. [1]
Esta sección presupone algún conocimiento de la teoría de categorías . En varias situaciones, existen semirretículos libres . Por ejemplo, el funtor olvidadizo de la categoría de semirretículos de unión (y sus homomorfismos) a la categoría de conjuntos (y funciones) admite un adjunto izquierdo . Por lo tanto, el semirretículo 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 puede ser incorporado en F ( S ) mediante una aplicación e que lleva cualquier elemento s en S al conjunto singleton { s }. Entonces, cualquier función f de un S a un semirretículo de unión T (más formalmente, al conjunto subyacente de T ) induce un homomorfismo único f' entre los semirretículos 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 adjunción requerida: la parte morfista del funtor F se puede derivar de consideraciones generales (ver funtores adjuntos ). El caso de semirretículos de encuentro libres es dual, utilizando la inclusión del subconjunto opuesto como ordenamiento. Para semirretículos de unión con fondo, simplemente agregamos el conjunto vacío a la colección anterior de subconjuntos.
Además, las semirretículas a menudo sirven como generadores de objetos libres dentro de otras categorías. Cabe destacar que tanto los funtores 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.
Suele suceder que los tratamientos estándar de la teoría de retículos definen un semirretículo, si es que lo hacen, y luego no dicen nada más. Véanse las referencias en las entradas teoría del orden y teoría de retículos . Además, no hay literatura sobre semirretículos de magnitud comparable a la de los semigrupos .
