Descargar

RETICULOS

Enviado por dambrosio


    1. Teorema (Ley idempotente)
    2. Retículos acotados
    3. Retículos distributivos
    4. Retículos complementarios

    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.

    RETICULOS ACOTADOS

    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.

    RETICULOS DISTRIBUTIVOS

    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.

    RETICULOS COMPLEMENTARIOS

    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