Sea L un conjunto no vacío cerrado para dos
operaciones
binarias llamadas conjunción y disyunción,
representadas respectivamente por Ù y Ú . Entonces L se llama retículo
silos siguientes axiomas son ciertos, donde a, b, c son elementos
arbitrarios de L:
Ley conmutativa:
Ley asociativa:
Ley de absorción:
Frecuentemente representaremos el retículo por
(L, Ù
, Ú
), cuando queramos mostrar las operaciones del
mismo.
El dual de cualquier expresión en un
retículo (L, A, V) está definido como la
expresión que se obtiene al intercambiar
Ù y
Ú . Por ejemplo,
el dual de
Notemos que el dual de cada axioma de un retículo
es también un axioma. Por consiguiente, el principio de
dualidad es cierto; esto es:
Teorema (Principio de dualidad) El dual de cualquier
teorema en un retículo es también un
teorema.
Esto se sigue del hecho de que el teorema dual puede
probarse usando el dual de cada paso de la demostración
del teorema original.
Una propiedad
importante de reticulos. se sigue directamente de las leyes de
absorción.
Teorema (Ley
idempotente)
La demostración de i) sólo requiere dos
líneas:
La demostración de ii) se obtiene a partir del
anterior principio de dualidad (o se puede demostrar de manera
análoga).
Dado un retículo L, podemos definir un orden
parcial sobre L de la siguiente manera:
Análogamente, podríamos
definir:
Precisamos estos resultados en un teorema.
Teorema . Sea L un retículo. Entonces:
i) a Ù
b = a si y sólo si a Ú b =b.
ii) la relacion a b (definida por a Ù b = a o a Ú b ₧b? Es un orden parcial
sobre L.
Ahora que tenemos un orden parcial sobre cualquier
retículo L, podemos dibujar L por un diagrama como
hemos hecho para los conjuntos
parcialmente ordenados en general.
EJEMPLO . Sea Cuna familia de
conjuntos
cerrada para la intersección y la unión. Entonces
(C, Ç
,È
) es un retículo. En este retículo, la
relación de orden parcial es la misma que la
relación de inclusión de conjuntos. el diagrama del
retículo L de todos los subconjuntos de {a, b,
c}.
Hemos mostrado cómo definir un orden parcial
sobre un retículo L. El siguiente teorema nos dice
cuándo podemos definir un retículo sobre un
conjunto parcialmente ordenado P, de tal manera que el orden
asociado al retículo sea el orden original sobre
P.
Teorema . Sea P un conjunto parcialmente ordenado, tal
que el inf(a, b) y el sup(a, b) existen para cualesquiera a, b de
P. Siendo:
a Ù
b = inf(a, b) y a Ú b = sup(a, b)
tenemos que (P, Ù , Ú ) es un retículo. Además
el orden parcial sobre P, inducido por el
retículo, es el mismo que el orden parcial
original sobre P.
El inverso del anterior teorema es también
cierto. Esto es, sea L un retículo y sea
Á el orden
parcial inducido sobre L. Entonces inf(a, b) y sup(a, b) existen
para cualquier par a, b de L y el retículo obtenido a
partir del conjunto parcialmente ordenado (L, Á ) es el retículo
original. De acuerdo con esto, tenemos lo siguiente:
Definición alternativa: Un retículo es un
conjunto parcialmente ordenado en el que:
a Ù
b = inf(a, b) y a Ú b = sup(a b)
existen para cualquier par de elementos a y
b.
Notemos en primer lugar que cualquier conjunto
linealmente ordenado es un retículo, puesto que inf(a, b)
= a y sup(a, b) = b siempre que a Á b. En el Ejemplo 10.4, el conjunto
de los números enteros positivos N y el conjunto
Dm de los divisores de m son reticulos para la
relación de divisibilidad.
Supongamos que M es un subconjunto no vacío de un
retículo L. Decimos que M es un subretículo de L si
M es un retículo (con respecto a las operaciones de L).
Notemos que M es un subretículo de L si y sólo si M
es cerrado para las operaciones Ù y Ú de L. Por ejemplo, el conjunto
Dm de los divisores de m es un subretículo del
conjunto N de los números enteros positivos con la
operación divisibilidad. Dos retículos L y L’
se llaman isomorfos si existe una aplicación biyectiva f:
L ®
L’, tal que:
para cualesquiera elementos a, b de L.
Un retículo L se dice que tiene una cota inferior
O si para cualquier elemento x de L se tiene que O
Á x.
Análogamente, se dice que L tiene una cosa
superior 1 si para cualquier x de L se tiene que x
Á I.
Decimos que L está acotado si L tiene una cota
inferior 0 y una cota superior 1. En un retículo acotado
se cumplen las identidades:
para cualquier elemento a de L.
Los enteros no negativos con la ordenación
usual:
0 < 1 < 2 < 3 < 4 <…
tienen a 0 como cota inferior, pero no tienen cota
superior. Por el contrario, el retículo P(U) de todos los
subconjuntos de cualquier conjunto universal U, es un
retículo acotado con U como cota superior y el conjunto
vacío Ø como cota inferior.
Supongamos que L = {a1, a2, …,
an} es un retículo finito. Entonces:
son, respectivamente, cotas superior e inferior para L.
Luego tenemos:
Teorema . Todo retículo finito L es
acotado.
Un retículo L se llama distributivo si para
cualesquiera elementos a, b, c de L tenemos lo
siguiente:
[ L4] Ley
distributiva:
En caso contrario, L se llama no distributivo; Notemos
que por el principio de dualidad la condición (4a) es
cierta si y sólo si (4b) es cierta.
La Figura (a) es un retículo no distributivo,
puesto que:
a Ù
(b Ù
c) = a Ú
0 = a
pero:
(a Ù
b) Ù
(a Ú
c) = I Ù
c = c
La Figura (b) es también un retículo no
distributivo. En efecto, tenemos la siguiente
caracterización de tales retículos.
Teorema . Un retículo L es no distributivo si y
sólo si contiene un subretículo isomorfo a la
Figura (a) o (b).
La demostración de este teorema se sale de los
objetivos de
este texto.
Sea L un retículo con una cota inferior 0. Un
elemento a de L se dice disyuntivamente irreducible si a =
x Ú y
implica a = x o a = y. (Los números primos con la
multiplicación tienen esta propiedad, es
decir, si p = ab entonces p = a o p = b cuando p es primo.)
Claramente 0 es disyuntivamente irreducible. Si a tiene al menos
dos predecesores inmediatos, sean b1 y b2
como en la Figura (a), entonces a = b1
Ú b y, por
tanto, a no es disyuntivamente irreducible. Por otro lado, si a
tiene un único predecesor inmediato c, entonces a
¹
sup(b1 , b2) = b1
Ú b2
para cualesquiera otros elementos b1 y b2
ya que c estaría entre las b’s y a como en la Figura
(b). En otras palabras, a ¹ 0 es disyuntivamente irreducible si y
sólo si a tiene un único predecesor inmediato.
Aquellos elementos que suceden inmediatamente a 0, llamados
átomos, son disyuntivamente irreducibles. Sin embargo, los
reticulos pueden tener otros elementos disyuntivamente
irreducibles. Por ejemplo, el elemento c de la Figura (a) no es
un átomo,
pero es disyuntivamente irreducible, puesto que a es su
único predecesor inmediato.
Si un elemento a de un retículo finito L no es
disyuntivamente irreducible, entonces podemos escribir a =
b Ú b
Ahora pode escribir b1 y b2 como la disyunción de otros
elementos si ellos no son disyuntivamente irreducibles; y
así sucesivamente. Puesto que L es finito, tenemos
finalmente:
A = d1 Ú d2 Ú … Ú dn
donde los d’s son disyuntivamente irreducibles. Si
di, precede a dj, entonces di
Ú dj = dj luego
podemos eliminar el di, de la expresión. En otras
palabras, podemos admitir que las d‘s son irredundantes, es
decir, ninguna d precede a cualquier otra d. Una expresión
así no es necesariamente única, por ejemplo, I = =
a Ú b e I
= b Ú e
en los dos retículos de la Figura . Damos ahora el
principal teorema de esta sección.
Teorema . Sea L un retículo distributivo finito.
Entonces todo elemento a de L se puede escribir de forma unica
(excepto por el orden) como la disyunción de elementos
disyuntivamente irreducibles irredundantes.
Actualmente este teorema se puede generalizar a
retículos con longitud finita, es decir, donde todos los
subeonjuntos linealmente ordenados son finitos.
Sea L un retículo acotado con cota inferior O y
cota superior 1. Sea a un elemento de L. Un elemento x de L se
llama complementario de a si:
a v x = I y a v x = 0
Los complementarios no existen necesariamente y no son
necesariamente únicos. Por ejemplo, los elementos a y e
son ambos complementarios de b en la Figura (a). Además,
los elementos y, z y u de la cadena de la Figura 10.1 no tienen
complementario. Tenemos el siguiente resultado.
Teorema . Sea L un retículo distributivo acotado.
Entonces los complementarios, si existen, son
únicos.
Demostración: Supongamos que x e y son
complementarios de un elemento cualquiera a de L.
Entonces:
Usando la distributividad:
Análogamente:
Luego:
y el teorema queda probado.
Un retículo L se llama complementario si L es
acotado y todo elemento de L tiene complementario. La Figura (b)
muestra un
retículo complementario donde los complementarios no son
únicos. Por otro lado, el retículo P(U) de todos
los subconjuntos de un conjunto universal U es complementario, y
cada subconj unto A de U tiene un único complementario
Ac = U A.
Teorema Sea L un retículo complementario con
complementario único. Entonces, los elementos
disyuntivamente irreducibles de L, distintos de O, son sus
átomos.
Combinando este teorema y los Teoremas, tenemos un
importante resultado.
Teorema . Sea L un retículo distributivo,
complementario y finito. Entonces, todo elemento a de L es la
disyunción de un único conjunto de
átomos.
Observación: Algunos textos definen un
retículo L como complementario, si cada elemento a de L
tiene un único complementario. El Teorema se enuncia
entonces de manera diferente.
Creado Por
Sergio E. D’Ambrosio