Semirretículo

En matemáticas , un semirretículo de unión (o semirretículo superior ) es un conjunto parcialmente ordenado que tiene una unión (el límite superior mínimo ) para cualquier subconjunto finito no vacío . De forma dual , un semirretículo de intersección (o semirretículo inferior ) es un conjunto parcialmente ordenado que tiene una intersección (o el límite inferior máximo ) para cualquier subconjunto finito no vacío. Todo semirretículo de unión es un semirretículo de intersección en orden inverso y viceversa.

Los semirretículos también se pueden definir algebraicamente : unir y encontrar son operaciones binarias asociativas , conmutativas e idempotentes , y cualquier operación de este tipo induce un orden parcial (y el orden inverso correspondiente) tal que el resultado de la operación para cualesquiera dos elementos es el límite superior más pequeño (o el límite inferior más grande) de los elementos con respecto a este orden parcial.

Un retículo es un conjunto parcialmente ordenado que es a la vez un semirretículo de intersección y de unión con respecto al mismo orden parcial. Algebraicamente, un retículo es un conjunto con dos operaciones binarias asociativas, conmutativas e idempotentes vinculadas por leyes de absorción correspondientes .

Un conjunto S parcialmente ordenado por la relación binaria ≤ es un semirretículo de intersección si

Para todos los elementos x e y de S , existe el mayor límite inferior del conjunto { x , y } .

El mayor límite inferior del conjunto { x , y } se llama el punto de intersección de x e y , denotado x ∧ y .

Sustituir "límite inferior máximo" por " límite superior mínimo " da como resultado el concepto dual de semirretículo de unión . El límite superior mínimo de { x , y } se denomina unión de x e y , denotada como x ∨ y . Las operaciones de encuentro y unión son binarias en S. Un sencillo argumento de inducción muestra que la existencia de todos los supremos (ínfimos) posibles por pares, según la definición, implica la existencia de todos los supremos (ínfimos) finitos no vacíos .

Un semirretículo de unión es acotado si tiene un elemento mínimo , la unión del conjunto vacío. De manera similar , un semirretículo de intersección es acotado si tiene un elemento máximo , la intersección del conjunto vacío.

Se pueden asumir otras propiedades; consulte el artículo sobre completitud en la teoría del orden para un análisis más detallado de este tema. Dicho 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 parcialmente ordenados relacionados, un enfoque de especial interés para las investigaciones del concepto desde la perspectiva de la teoría de categorías .

Un semirretículo de encuentro es una estructura algebraica.${\displaystyle \langle S,\land \rangle }$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 :

Asociatividad

x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z

Conmutatividad

x ∧ y = y ∧ x

Idempotencia

x ∧ x = x

Un encuentro semirremolque${\displaystyle \langle S,\land \rangle }$está acotada si S incluye un elemento 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 anterior, la estructura se denomina semirretículo de unión . Se puede ser ambivalente respecto a la elección del símbolo para la operación y hablar simplemente de semirretículos .

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

En un semirretículo de intersección, se induce un orden parcial al establecer x ≤ y siempre que x ∧ y = x . En un semirretículo de unión, el orden se induce al establecer x ≤ y siempre que x ∨ y = y . En un semirretículo de intersección acotado, el elemento 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. Recíprocamente, 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 forma define un orden parcial a partir del cual se puede recuperar la operación binaria ∧ . A la inversa, el orden inducido por el semirretículo definido algebraicamente ⟨ S , ∧ ⟩ coincide con el inducido por ≤.

Por lo tanto, ambas 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 orden dual ≥.

Las semirretículas se emplean para construir otras estructuras de orden, o en combinación con otras propiedades de completitud.

• Una red es a la vez una semired de unión y una semired de encuentro. La interacción de estas dos semiredes mediante la ley de absorción es lo que realmente distingue una red de una semired.
• Los elementos compactos de una red algebraica , bajo el ordenamiento parcial inducido, forman una semirretícula de unión acotada.
• Por inducción sobre el número de elementos, cualquier semirretículo finito no vacío de intersección tiene un elemento mínimo, y cualquier semirretículo finito no vacío de unión tiene un elemento máximo. (En ninguno de los casos el semirretículo será necesariamente acotado).
• Un conjunto totalmente ordenado es un retículo distributivo , y por lo tanto, en particular, un semirretículo de intersección y un semirretículo de unión: cualesquiera dos elementos distintos tienen uno mayor y otro menor, que son su intersección y su unión.
  • Un conjunto bien ordenado es además un semirretículo de unión acotado , ya que el conjunto en su conjunto tiene un elemento mínimo, por lo tanto, es acotado.
    • Los números naturales${\displaystyle \mathbb {N} }$, con su orden usual ≤, son un semirretículo de unión acotado, con elemento mínimo 0, aunque no tienen elemento máximo: son el conjunto infinito bien ordenado más pequeño.
• Cualquier árbol de raíz única (con la raíz única como el elemento más pequeño) de altura${\displaystyle \leq \omega }$es un semirretículo de encuentro (generalmente no acotado). Consideremos, por ejemplo, el conjunto de palabras finitas sobre algún alfabeto, ordenadas por el orden de prefijo . Tiene un elemento mínimo (la palabra vacía), que es un elemento anulador de la operación de encuentro, pero no tiene un elemento máximo (identidad).
• Un dominio de Scott es un semirretículo de encuentro.
• La pertenencia a cualquier conjunto L puede tomarse como un modelo de un semirretículo con conjunto base L , porque un semirretículo captura la esencia de la extensionalidad de conjuntos . Sea a ∧ b denotado por a ∈ L y b ∈ L. Dos conjuntos que difieren solo en uno o ambos de los siguientes :

1. Orden en que aparecen sus miembros;
2. Multiplicidad de uno o más miembros,

son, de hecho , el mismo conjunto. La conmutatividad y la asociatividad de ∧ aseguran (1), la idempotencia , (2). Este semirretículo es el semirretículo libre sobre L. No está acotado por L , porque un conjunto no es miembro de sí mismo.

• La mereología extensional clásica define un semirretículo de unión, donde unión se interpreta como fusión binaria. Este semirretículo está delimitado superiormente por el individuo del mundo.
• Dado un conjunto S , la colección de particiones${\displaystyle \xi }$de S es un semirretículo de unión. De hecho, el orden parcial viene dado por${\displaystyle \xi \leq \eta }$si${\displaystyle \forall Q\in \eta ,\exists P\in \xi }$de tal manera que${\displaystyle Q\subset P}$y la unión de dos particiones viene dada por${\displaystyle \xi \vee \eta =\{P\cap Q\mid P\in \xi \ \land \ Q\in \eta \}}$Este semirretículo es acotado, siendo el elemento más pequeño la partición unitaria.${\displaystyle \{S\}}$.

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

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

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 debe ser un homomorfismo de monoide , es decir, requerimos adicionalmente que

f (0) = 0.

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 las uniones binarias y los elementos mínimos, si los hay. El dual obvio —sustituyendo ∧ por ∨ y 0 por 1— transforma esta definición de homomorfismo de semirretículo de unión en su equivalente de semirretículo de encuentro.

Cualquier homomorfismo de semirretículo es necesariamente monótono con respecto a la relación de orden asociada.

Existe una equivalencia bien conocida entre la categoría${\displaystyle {\mathcal {S}}}$de semirretículos de unión con cero con${\displaystyle (\vee ,0)}$-homomorfismos y la categoría${\displaystyle {\mathcal {A}}}$de retículos algebraicos con homomorfismos de unión completos que preservan la compacidad , como sigue. Con un semirretículo de unión${\displaystyle S}$Con cero, asociamos su red ideal${\displaystyle \operatorname {Id} \ S}$. Con un${\displaystyle (\vee ,0)}$-homomorfismo${\displaystyle f\colon S\to T}$de${\displaystyle (\vee ,0)}$-semiretículos, asociamos el mapa${\displaystyle \operatorname {Id} \ f\colon \operatorname {Id} \ S\to \operatorname {Id} \ T}$, que con cualquier ideal${\displaystyle I}$de${\displaystyle S}$asocia el ideal de${\displaystyle T}$generado por${\displaystyle f(I)}$Esto define un functor${\displaystyle \operatorname {Id} \colon {\mathcal {S}}\to {\mathcal {A}}}$Por el contrario, con cada retículo algebraico${\displaystyle A}$asociamos el${\displaystyle (\vee ,0)}$-semiretículo${\displaystyle K(A)}$de todos los elementos compactos de${\displaystyle A}$y con cada homomorfismo de unión completo que preserva la compacidad${\displaystyle f\colon A\to B}$Entre retículos algebraicos asociamos la restricción${\displaystyle K(f)\colon K(A)\to K(B)}$Esto define un functor${\displaystyle K\colon {\mathcal {A}}\to {\mathcal {S}}}$La pareja${\displaystyle (\operatorname {Id} ,K)}$define una equivalencia de categoría entre${\displaystyle {\mathcal {S}}}$y${\displaystyle {\mathcal {A}}}$.

Sorprendentemente, existe una noción de "distributividad" aplicable a semirretículos, aunque convencionalmente la distributividad requiere la interacción de dos operaciones binarias. Esta noción requiere solo una operación y generaliza la condición de distributividad para retículos. Un semirretículo de unión es distributivo si para todo a, b y x con x ≤ a ∨ b existen a ' ≤ a y b ' ≤ b tales que x = a ' ∨ b ' . Los semirretículos de intersección distributivos se definen de forma dual. Estas definiciones se justifican por el hecho de que cualquier semirretículo de unión distributivo en el que existan intersecciones binarias es un retículo distributivo. Véase la entrada distributividad (teoría del orden) .

Un semirretículo de unión es distributivo si y solo si el retículo de sus ideales (bajo inclusión) es distributivo.

Actualmente, el término «semiretículo completo» carece de un significado generalmente aceptado, y existen diversas definiciones contradictorias. Si se entiende por completitud la existencia de todas las uniones infinitas, o de todas las intersecciones infinitas, según sea el caso, así como de las finitas, esto conduce inmediatamente a órdenes parciales que, de hecho, son retículos completos . Para comprender por qué la existencia de todas las posibles uniones infinitas implica la existencia de todas las posibles intersecciones infinitas (y viceversa), véase la entrada « completitud (teoría del orden)» .

No obstante, la literatura a veces sigue considerando los semirretículos de unión o de intersección completos como retículos completos. En este caso, la «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 todas las uniones, pero, a diferencia de lo que ocurre con las propiedades de completitud, esto no requiere que los homomorfismos preserven todas las intersecciones. Por otro lado, podemos concluir que cada aplicación 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 intersección 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 todas las intersecciones o uniones, respectivamente.

Otro uso de "semiretículo de encuentro completo" se refiere a un cpo completo acotado . Un semiretículo de encuentro completo en este sentido es posiblemente el semiretículo de encuentro "más completo" que no necesariamente es un retículo completo. De hecho, un semiretículo de encuentro completo tiene todos los encuentros no vacíos (lo que es equivalente a ser completo acotado) y todas las uniones dirigidas . Si dicha estructura también tiene un elemento máximo (el encuentro del conjunto vacío), también es un retículo completo. Por lo tanto, un semiretículo completo resulta ser "un retículo completo que posiblemente carece de un top". Esta definición es de interés particularmente 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 llamado semiretículos algebraicos .

Las nociones de completitud restringidas por cardinalidad para semirretículos rara vez se han considerado en la literatura. ^{[ 1 ]}

Esta sección presupone cierto conocimiento de la teoría de categorías . En diversas situaciones, existen semirretículos libres . Por ejemplo, el functor de olvido 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 incrustarse en F ( S ) mediante una aplicación e que toma cualquier elemento s en S al conjunto unitario { 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' viene dado por${\textstyle f'(A)=\bigvee \{f(s)|s\in A\}.}$Ahora, la unicidad obvia de f' basta para obtener la adjunción requerida; la parte morfológica del functor F puede derivarse de consideraciones generales (véase functores adjuntos ). El caso de semirretículos de intersección libres es dual, utilizando la inclusión de subconjuntos opuestos como ordenamiento. Para semirretículos de unión con base, simplemente añadimos el conjunto vacío a la colección de subconjuntos anterior.

Además, los semirretículos suelen servir como generadores de objetos libres dentro de otras categorías. Cabe destacar que tanto los functores de olvido de la categoría de marcos y homomorfismos de marcos, como los de la categoría de retículos distributivos y homomorfismos de retículos, tienen un adjunto izquierdo.

• Conjunto dirigido – Ordenamiento matemático con cotas superiores – Generalización del semirretículo de unión  
• Lista de temas de pedidos
• Semianillo – Anillo algebraico que no necesariamente tiene elementos negativos aditivos. 

• Davey, BA; Priestley, HA (2002). Introducción a las redes y el orden (segunda  ed.). Cambridge University Press . ISBN 0-521-78451-4.
• Vickers, Steven (1989). Topología mediante la lógica . Cambridge University Press . ISBN 0-521-36062-5.

Con frecuencia, los tratamientos estándar de la teoría de retículos definen un semirretículo, si acaso, y no dan más detalles. Véanse las referencias en las entradas « teoría del orden» y «teoría de retículos» . Además, no existe bibliografía sobre semirretículos de magnitud comparable a la que existe sobre semigrupos .

• Página de Jipsen sobre estructuras algebraicas: Semirretículos.