Semirretículo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas, un semirretículo superior es un conjunto parcialmente ordenado en el que existe un supremo para todo subconjunto no vacío finito. Dualmente, un semirretículo inferior es un conjunto parcialmente ordenado en el que existe un ínfimo para todo subconjunto no vacío finito. Todo semirretículo superior es un semirretículo inferior en el orden inverso y vice versa.

Los semirretículos también pueden definirse algebraicamente: el supremo y el ínfimo son operaciones binarias asociativas, conmutativas, idempotentes y cualquiera operación de estas características induce un orden parcial (así como el correspondiente orden inverso) de modo que el resultado de la operación para dos elementos cualesquiera es el supremo (o ínfimo, en su caso) de los elementos con respecto a ese orden parcial.

Un retículo es un conjunto parcialmente ordenado que es tanto semirretículo superior como semirretículo inferior con respecto a un mismo orden parcial. Algebraicamente, un retículo es un conjunto con dos operaciones binarias asociativas, conmutativas e idempotentes, enlazadas por las correspondientes leyes de absorción.

Definición en términos de la teoría del orden[editar]

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

Para todos los elementos x e y en S, existe el ínfimo del conjunto {x, y}.

El ínfimo del conjunto {x, y} se denomina ínfimo de x e y, denotándose xy.

Al reemplazar "ínfimo" por "supremo" se obtiene el concepto dual de semirretículo superior. El supremo de {x, y} se denomina supremo de x e y, denotándose xy. Ínfimo y supremo son operaciones binarias en S. Un simple argumento de inducción muestra que la existencia de todos los supremos (ínfimos) por pares, por definición, implica la existencia de todos los supremos (ínfimos) de conjuntos no vacíos finitos.

Un semirretículo superior es acotado si tiene un elemento menor, el supremo del conjunto vacío. Dualmente, un semirretículo inferior se dice acotado si tiene un elemento mayor, el ínfimo del conjunto vacío.

Es posible suponer otras propiedades; véase el artículo sobre completitud en la teoría del orden para más detalles. En ese artículo también se analiza como podemos reformular la definición dada aquí en términos de la existencia de conexiones de Galois apropiadas entre conjuntos parcialmente ordenados — un enfoque de interés especial para investigaciones del concepto en términos de la teoría de categorías.

Definición algebraica[editar]

Un "semirretículo inferior" es una estructura algebraica S, ∧〉 consistente en un conjunto S con una operación binaria ∧, llamada ínfimo, tal que para todos los miembros x, y y z de S se cumplen las siguientes identidades:

Asociatividad
x ∧ (yz) = (xy) ∧ z
Conmutatividad
xy = yx
Idempotencia
xx = x

Un semirretículo inferior S, ∧〉 se dice acotado si en S existe un elemento neutro 1 tal que x ∧ 1 = x para todo x en S.

Si el símbolo ∧ se reemplaza por el símbolo ∨ en la definición anterior para designar una operación binaria llamada supremo, la estructura se denomina semirretículo superior. Es posible ser ambivalente en cuanto al símbolo a usar, hablando simplemente de semirretículos.

Un semirretículo es un semigrupo idempotente y conmutativo. Alternativamente, un semirretículo es una banda conmutativa. Un semirretículo acotado es un monoide idempotente y conmutativo.

Un semirretículo inferior induce un orden parcial declarando xy cada vez que xy=x. En el caso de un semirretículo superior, el orden se induce declarando xy cada vez que xy=y. En un semirretículo inferior acotado, el elemento neutro 1 es un elemento mayor de S. Similarmente, un elemento neutro de un retículo superior es un elemento menor.

Relación entre ambas definiciones[editar]

Un semirretículo inferior en términos de la teoría del orden S, ≤〉 da origen a una operación binaria ∧ tal que S, ∧〉 es un semirretículo inferior en términos algebraicos. A la inversa, el semirretículo inferior S, ∧〉 da origen a una operación binaria ≤ que ordena parcialmente al conjunto S de la siguiente manera: para todo elemento x e y en S, xy si y solo si x = xy.

La relación ≤ introducida de esta manera define un orden parcial, del cual es posible recuperar la operación binaria ∧. A la inversa, el orden inducido por el semiretículo definido algebraicamente S, ∧〉 coincide con aquél inducido por ≤.

Por tanto, ambas definiciones pueden usarse de manera intercambiable, dependiendo de cuál sea más conveniente para un propósito particular. Para semirretículos superiores y el orden dual ≥ se verifica una conclusión similar.

Ejemplos[editar]

Los semirretículos suelen utilizarse para construir otras estructuras de orden o en asociación con tras propiedades de completitud.

  • Un retículo es tanto semirretículo superior como semirretículo inferior. La interacción entre estos dos semirretículos a través de la ley de absorción es lo que realmente distingue a un retículo de un semirretículo.
  • Los elementos compactos de un retículo algebraico, bajo el orden parcial inducido, forman un retículo superior acotado.
  • Todo árbol (con la raíz como su elemento menor) es un semirretículo inferior. Considérese por ejemplo el conjunto de las palabras finitas sobre algún alfabeto, ordenado por la relación de prefijos. Este conjunto tiene un elemento menor, pero no tiene elemento mayor: la raíz es el ínfimo de todos los demás elementos.
  • Un dominio de Scott es un retículo inferior.
  • La calidad de miembro de un conjunto cualquiera L puede interpretarse como model de un semirretículo sobre el conjunto base L, puesto que un semirretículo captura la esencia de la extensionalidad de los conjuntos. convengamos que ab denota aL & bL. Dos conjuntos que solamente difieran en ambos aspectos que sigues, o en uno de ellos:
  1. Orden en que se enumeran sus miembros;
  2. Multiplicidad de uno o más miembros,
son de hecho el mismo conjunto. La Conmutatividad y asociatividad de ∧ garantizan (1), su idempotencia, (2). Este semirretículo es el semirretículo libre sobre L. No está acotado por L, dado que un conjunto no es miembro de simismo.
  • La mereología clásica extensional define un semirretículo superior, cuyo supremo se entiende como fusión binaria. Este semirretículo es acotado desde arriba por el individuo mundo.

Morfismos entre semirretículos[editar]

La anterior definición algebraica de semirretículo sugiere la noción de morfismo entre dos semirretículos. Dados dos semirretículos superiores S, ∨〉 y T, ∨〉, un homomorfismo entre semirretículos (superiores) es una función f: ST tal que

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

Por tanto, f es simplemente un homomorfismo entre los semigrupos asociados a cada uno de los semirretículos. Si tanto S como T contienen un elemento menor 0, f puede ser también un homomorfismo monoide, si es que adicionalmente se requiere que

f(0) = 0.

Para la formulación en términos de la teoría del orden, estas condiciones simplemente sostienen que un homomorfismo de semirretículos superiores es una función que conserva supremos y elementos menores, de existir. La formulación dual obvia — reemplazando ∧ por ∨ y 0 por 1 — transforma esta definición de homomorfismo de semirretículo superior en su equivalente en términos de semirretículo inferior.

Nótese que todo homomorfismo de semirretículos es necesariamente monótono con respecto a la relación de orden relacionada.

Equivalencia con retículos algebraicos[editar]

Existe una conocida equivalencia entre la categoría \mathcal{S} de semirretículos superiores con cero y con homomorfismos (\vee,0) por un lado, y la categoría \mathcal{A} de los retículos algebraicos con homomorfismos superiores completos que conserven la compacidad como sigue. A un semirretículo superior con cero S, le asociamos su retículo ideal \operatorname{Id}\ S. A un (\vee,0)-homomorfismo f \colon S \to T de (\vee,0)-semirretículos, le asociamos la aplicación \operatorname{Id}\ f \colon \operatorname{Id}\ S \to \operatorname{Id}\ T, que a cada ideal I de S le asocia el ideal de T generado por f(I). Así se define un functor \operatorname{Id} \colon \mathcal{S} \to \mathcal{A}. A la inversa, a cada retículo algebraico A le asociamos el (\vee,0)-semirretículo K(A) de todos los elementos compactos de A y a cada homomorfismo superior completo preservante de la compacidad f \colon A \to B entre retículos algebraicos le asociamos la restricción K(f) \colon K(A) \to K(B). Así se define un functor K \colon \mathcal{A} \to \mathcal{S}. El par (\operatorname{Id},K) define una equivalencia de categorías entre \mathcal{S} y \mathcal{A}.

Semirretículos distributivos[editar]

Aunque sea sorprendente, sí existe una noción de "distributividad" aplicable a semirretículos, aunque la distributividad convencionalmente trata de la interacción de dos operaciones binarias. Este concepto no requiere más que una única operación y generaliza la condición de distributividad para retículos. Véase el artículo distributividad (teoría del orden).

Semirretículos completos[editar]

Hoy en día, el término "semirretículo completo" no tiene una significación generalmente aceptada y existen varias definiciones inconsistentes entre si. Si la completitud se entiende como exigencia de que existan todos los supremos o ínfimos, en su caso, como también todos los finitos, esto inmediatamente lleva a órdenes parciales que constituyen, de hecho, retículos completos. Porque la existencia de todos los supremos infinitos posibles conlleva la existencia de todos los ínfimos infinitos posibles (y vice versa), véase el artículo completitud en la teoría del orden.

Sin embargo, en la literatura ocasionalmente aún se entiende que los semirretículos superiores o inferiores son retículos completos. En este caso, "completitud" denota una restricción del alcance de los homomorfismos. Específicamente, para un semirretículo superior completo se requiere que los homomorfismos preserven todos los supremos, pero contrariamente a la con la que nos encontramos en el caso de las propiedades de completitud, esto no requiere que los homomorfismos preserven todos los ínfimos. 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 (único) correspondiente será entonces un homomorfismo de semirretículos inferiores completos. Esto da origen a una serie de dualidades en materia de la teoría de categorías entre las categorías de todos los semirretículos completos con morfisms preservadores de todos los ínfimos o supremos, respectivamente.

Otra acepción del término "semirretículo inferior completo" se refiere a un orden parcial completo en un conjunto parcialmente ordenado acotado y completo. Un semirretículo inferior completo en este sentido probablemente constituya el semirretículo inferior "más completo" que no necesariamente es un retículo completo. Efectivamente, un semirretículo inferior completo contiene a todos los ínfimos no vacíos (lo que es equivalente a que sea acotado y completo ) y a todos los supremos dirigidos. Si una estructura tal además tiene un elemento mayor (el ínfimo del conjunto vacío) , resulta ser a su vez un retículo completo. Por tanto, un retículo completo resulta ser "un retículo completo al que posiblemente le falte la cúspide". Esta definición es de especial interés en la teoría de dominios, en la que se estudian los conjuntos parcialmente ordenados algebraicos como dominios de Scott. Por lo anterior, a los dominios de Scott se los ha denominado semirretículos algebraicos.

Semirretículos libres[editar]

Esta sección presupone cierto grado de conocimiento de la teoría de categorías. En una variedad de situaciones, existen semirretículos libres. Por ejemplo, el funtor olvido desde la categoría de los semirretículos superiores (y sus homomorfismos) a la categoría de los conjuntos (y funciones) admite un adjunto izquierdo. Por tanto, el semirretículo superior libre F(S) sobre un conjunto S se construye tomando la colección de de todos los subconjuntos no vacíos finitos de S, ordenados por la inclusión de subconjuntos. Claramente, S puede encajarse en F(S) por medio de una aplicación e que transforma cualquier elemento s de S en el conjunto unitario {s}. Entonces cualquier función f desde S a un semirretículo superior T (más formalmente, al conjunto subyacente de T) induce un homomorfismo único f' entre los semirretículos superiores F(S) y T, tal que f = f' o e. Explícitamente, f' está dado por f' (A) = \vee{f(s) | s in S}. Ahora, la unicidad obvia de f' basta para obtener el carácter adjunto requerido — el aspecto de morfismo del funtor F puede derivarse en base a consideraciones generales (ver funtores adjuntos). El caso de los semirretículos inferiores libres es dual, usando la relación de inclusión opuesta como relación de orden. Para un tratamiento de semirretículos superiores con fondo, simplemente agregamos el conjunto vacío a la colección de subconjuntos arriba mencionada.

Adicionalmente, los semirretículos muchas veces sirven de generadores de objetos libres en otras categorías. Es notable, por ejemplo, que los funtores olvido, tanto de la categoría de framas y homomorfismos de framas, como de la categoría de los retículos distributivos y homomorfismos de retículo, tienen un adjunto izquierdo.

Véase también[editar]

Referencias[editar]

Lamentablemente, con frecuencia se da el caso que en los tratados estándar de la teoría de retículos se defina un semirretículo, cuando más, y después no se vuelva a mencionar. Véanse las referencias en los artículos sobre teoría del orden y teoría de retículos. Más aún, no existe bibliografía sobre semirretículos de magnitud comparable a la que existe sobre semigrupos.

Enlaces externos[editar]

  • Página Web de Jipsen sobre estructuras algebraicas: Semirretículos. (en inglés)