Semirretículo

Relaciones binarias transitivas en a mi
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Total, Semiconnex Anti- reflexivo Relación de equivalencia Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado (cuasi pedido) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado total ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Pedido total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Preordenamiento de pozos ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien-cuasi-ordenamiento ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Buen orden ✗ Y Y Y ✗ ✗ Y ✗ ✗ Enrejado ✗ Y ✗ ✗ Y Y Y ✗ ✗ Unión de semirrejilla ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Conocer-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden débil estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricta ✗ Y Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones, para todos y${\estilo de visualización a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ y }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ o }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\estilo de visualización aRa}$ ${\displaystyle {\text{no }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{no }}bRa\end{aligned}}}$
Yindica que la propiedad de la columna siempre es verdadera para el término de la fila (a la izquierda), mientras que ✗ indica que la propiedad no está garantizada en general (puede cumplirse o no). Por ejemplo, que toda relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica con en la columna "Simétrica" ​​y ✗ en la columna "Antisimétrica", respectivamente.Y Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : para todo si y entonces La definición de un término puede requerir propiedades adicionales que no están enumeradas en esta tabla.${\estilo de visualización R}$${\estilo de visualización a,b,c,}$$Estilo de visualización aRb$${\estilo de visualización bRc}$${\estilo de visualización aRc.}$

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

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

El máximo límite inferior del conjunto { x , y } se llama 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 :${\displaystyle \langle S,\land \rangle }$

Asociatividad

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

Conmutatividad

x ∧ y = y ∧ x

Idempotencia

x ∧ x = x

Una semirretícula de encuentro está acotada si S incluye un elemento identidad 1 tal que x ∧ 1 = x para todo x en S.${\displaystyle \langle S,\land \rangle }$

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.

• Una red es a la vez una semirretícula de unión y una semirretícula de encuentro. La interacción de estas dos semirretículas a través de la ley de absorción es lo que verdaderamente distingue una red de una semirretícula.
• 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 de encuentro finito no vacío tiene un elemento menor y cualquier semirretículo de unión finito no vacío tiene un elemento mayor. (En ningún caso el semirretículo estará necesariamente acotado).
• Un conjunto totalmente ordenado es una red distributiva , y por lo tanto en particular una semirretícula de encuentro y una semirretícula de unión: dos elementos distintos tienen un elemento mayor y un elemento menor, que son su encuentro y su unión.
  • Un conjunto bien ordenado es además una semirretícula de unión acotada , ya que el conjunto en su conjunto tiene un mínimo de elementos, por lo tanto, está acotado.
    • Los números naturales , con su orden habitual ≤, son un semirretículo de unión acotado, con menor elemento 0, aunque no tienen mayor elemento: son el conjunto infinito bien ordenado más pequeño.${\displaystyle \mathbb {N} }$
• Cualquier árbol de una sola raíz (con la raíz única como el elemento menor) de altura es un semirretículo de encuentro (generalmente ilimitado). Consideremos, por ejemplo, el conjunto de palabras finitas sobre algún alfabeto, ordenadas por el prefijo order . Tiene un elemento menor (la palabra vacía), que es un elemento aniquilador de la operación de encuentro, pero no tiene ningún elemento mayor (identidad).${\displaystyle \leq \omega }$
• Un dominio Scott es un semirretículo de encuentro.
• La pertenencia a cualquier conjunto L puede tomarse como modelo de una semirretícula con un conjunto base L , porque una semirretícula captura la esencia de la extensionalidad de los conjuntos . Sea a ∧ b a ∈ L y b ∈ L . Dos conjuntos que difieren solo en uno o ambos de los siguientes:

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

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

• La mereología extensional clásica define una semirretícula de unión, en la que la unión se lee como fusión binaria. Esta semirretícula está limitada desde arriba por el individuo del mundo.
• Dado un conjunto S , la colección de particiones de S es un semirretículo de unión. De hecho, el orden parcial está dado por si tal que y la unión de dos particiones está dada por . Este semirretículo está acotado, siendo el elemento menor la partición singleton .${\displaystyle \xi }$${\displaystyle \xi \leq \eta }$${\displaystyle \forall Q\in \eta ,\exists P\in \xi }$${\displaystyle Q\subset P}$${\displaystyle \xi \vee \eta =\{P\cap Q\mid P\in \xi \ \&\ Q\in \eta \}}$${\displaystyle \{S\}}$

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

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 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 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.

Nótese 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 .${\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)\colon K(A)\to K(B)}$${\displaystyle K\colon {\mathcal {A}}\to {\mathcal {S}}}$${\displaystyle (\operatorname {Id} ,K)}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {A}}}$

Sorprendentemente, existe una noción de "distributividad" aplicable a los semirretículos, aunque la distributividad requiere convencionalmente 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.${\textstyle f'(A)=\bigvee \{f(s)|s\in A\}.}$

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.

• Conjunto dirigido  – Ordenamiento matemático con límites superiores − generalización de la semired de unión
• Lista de temas de pedidos
• Semiring  – Anillo algebraico que no necesita tener elementos negativos aditivos

• Davey, BA; Priestley, HA (2002). Introducción a los enrejados y el orden (segunda edición). Cambridge University Press . ISBN 0-521-78451-4.
• Vickers, Steven (1989). Topología a través de la lógica . Cambridge University Press . ISBN. 0-521-36062-5.

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 .

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