2. LATICES

2. LÁTICES

Una látice o red es un conjunto parcialmente ordenado por una relación de orden, en el cual cada subconjunto {a, b} de este, que consta de dos elementos, tiene una mínima cota superior y una máxima cota inferior.

Se escribirá la mínima cota superior del conjunto {a,b} como m.c.s({a, b}) y se denotará por "a + b". Similarmente se escribirá la máxima cota inferior del conjunto {a, b} como M.C.I({a, b}) y se denotará por "a. b".

Ejemplo 1. Sea S un conjunto no vacío y sea L = P(S). Se sabe que la operación "Í " define una relación de orden parcial en P(S). Acá se cumple que A + B (m.c.m({A, B})) es la unión de A y B y A B (M.C.I({A, B})) es la intersección de A y B.

Ejemplo 2. Sea n un entero positivo y sea Dn el conjunto de todos los divisores positivos de n. Entonces el conjunto Dn ordenado por la relación de divisibilidad es una látice.

Así, si n = 20 entonces D₂₀ = {1, 2, 4, 5, 10, 20} y se cumple que para cualesquiera a, b Î D₂₀:

a + b = m.c.s({a, b}) es el mínimo común múltiplo de a y b.

a.b = M.C.I({a, b}) es el máximo común divisor de a y b.

El diagrama de Hasse de D₂₀ ilustra claramente esta situación.

Ejemplo 3 El conjunto parcialmente ordenado representado por el siguiente diagrama de Hasse no es una látice.

No es una látice porque el conjunto {f, g} no posee mínima cota superior, es decir f + g no existe.

Ejemplo 4. El conjunto parcialmente ordenado representado por el siguiente diagrama de Hasse no es una látice.

No es una látice porque no existen c + b y d.e. Esto a pesar de que los conjuntos {b, c} y {d, e} poseen respectivamente cotas superiores y cotas inferiores, pero no son comparables.

Sublátice. Sea (L, £ ) una látice. A un subconjunto no vacío S, de L se le llama una sublátice de L si se cumplen las siguientes dos condiciones:

• (a + b) Î S. " a, b Î S.
• a.b Î S. " a, b Î S.

Ejemplo 5. Dado D₂₀ = {1, 2, 4, 5, 10, 20} ordenado por la relación de divisibilidad, entonces los siguientes conjuntos son sublátices de D₂₀.

D₁₀ = {1, 2, 5, 10} D₄ = {1, 2, 4}

Propiedades de las látices.

1. a £ a + b; b £ a + b (por ser a + b una cota superior del conjunto {a, b}).

2. a £ c y b £ c si y sólo si a + b £ c (por ser a + b la mínima cota superior del conjunto {a, b}).

3. a.b £ a; a.b £ b (por ser a.b cota inferior de {a, b}).

4. c £ a y c £ b sí y sólo si c £ a. b (por ser a.b la máxima cota interior de a y b).

Teorema. Sea L una látice entonces para cualquiera a,b Î L se cumple:

1. a + b = b sí y sólo sí a £ b.

2. a.b = a sí y sólo sí a £ b.

3. a.b = a sí y sólo sí a + b = b.

Demostración de b = b sí y sólo sí a £ b. Suponga que a + b = b; como a £ a + b se concluye que a £ b. Recíprocamente si a £ b, entonces como b £ b se tiene que b es una cota superior de {a, b}. Por la definición de mínima cota superior se tiene que a + b £ b. Como a + b es cota superior, se cumple que b £ a + b. De acá se concluye que b = a + b.

Teorema. Sea L una látice, entonces:

1. Ley de Idempotencia. a + a = a a.a = a.

2. Ley conmutativa. a + b = b + a a.b = b.a.

3. Ley asociativa. a + (b + c) = (a + b) + c a(b.c) = (a.b)c.

4. Ley de absorción. a + a.b = a a(a + b) = a.

Demostración de a + a.b = a. Se tiene que a · b £ a por ser a.b cota inferior; y como a £ a se tiene entonces que a es una cota superior de a.b y a. Como la mínima cota superior de los elementos a.b y a es a + a.b, se concluye entonces que a + a.b £ a. De la definición de mínima cota superior, se tiene que a £ a + a.b Por lo tanto, a = a + ab.

Teorema. Sea L una látice. Entonces para cada a, b y c en L no cumple:

1. Sí a £ b entonces a + c £ b + c a.c £ b.c.

2. Sí a £ b y c £ d entonces a + c £ b + d a.c £ b.d.

Tipos especiales de látices.

Definición. Una látice L se llama acotada si tiene un elemento máximo y un elemento mínimo. El elemento máximo se denotará 1 y el elemento mínimo 0.

Definición. Una látice L se llama distributiva si para todo a, b y c Î L se cumple:

- a + (b.c) = (a + b)(a + c).

- a(b + c) = (ab) + (a.c).

Ejemplo 6. El conjunto potencia de S, P(S) ordenado por la relación "Í " es una látice distributiva ya que las operaciones de unión o intersección distribuyen la una respecto a la otra.

Ejemplos 7. Muestre que la látice cuyo diagrama de Hasse se muestra, no es una látice distributiva.

Del diagrama de Hasse se puede afirmar:

b + c = 1

a(b + c) = a 1 = a

\ a (b + c) = a (1)

Mientras que:

a b = b

a c = 0

entonces, ab + ac = b + o = b (2)

De (1) y (2) se concluye que:

a(b + c) ¹ ab + a c

Definición. Sea L una látice acotada con un elemento máximo 1 y un elemento mínimo 0, y sea a Î L. A un elemento a’ Î L se le llama complemento de a si cumple las siguientes dos condiciones:

• a + a’ = 1.
• a a’ = 0.

Definición. Una látice L se llama complementada sí es acotada y si cada elemento en L tiene un complemento.

Teorema. Sea L una látice distributiva complementada. Entonces para cada a Î L se cumple que a’ es único.

Demostración: Suponga que a’ y a" son los complementos de a, entonces:

a + a’ =1 a + a" =1

a a" = 0 a a’’ = 0

Usando las leyes distributivas se tiene:

a’ = a’ + 0 = a’ + (a a’’) = (a + a’)( a’ + a’')

= (a’ + a)( a’ + a’')

= 1 ( a’ + a’')

= a’ + a’'

a’’ = a’’ + 0 = a’’ + (a a’) = (a’’ + a)( a’’ + a’)

= (a + a")( a’ + a’')

= 1 ( a’ + a’')

= a’ + a’'

Se concluye entonces que a’ = a" y el complemento de a es único.

- DIAGRAMA DE HASSE

En matemáticas, un diagrama de Hasse es una representación gráfica simplificada de un conjunto parcialmente ordenado finito. Esto se consigue eliminando información redundante. Para ello se dibuja una arista ascendente entre dos elementos solo si uno sigue a otro sin haber otros elementos intermedios.

En un diagrama de Hasse se elimina la necesidad de representar:

• ciclos de un elemento, puesto que se entiende que una relación de orden parcial es reflexiva.
• aristas que se deducen de la transitividad (matemática) de la relación.

Definición

• De dos miembros x e y de un conjunto parcialmente ordenado S que «y sigue a x» si x ≤ y y no hay elemento de S entre x e y.

El orden parcial es entonces precisamente la clausura transitiva de la relación de seguir.

• El diagrama de Hasse de S se define como el conjunto de todos los pares ordenados (x, y) tales que y sigue a x, es decir, el diagrama de Hasse se puede identificar con la relación de seguir.

Ejemplo8

Concretamente, uno representa a cada miembro de S como un punto negro en la página y dibuja una línea que vaya hacia arriba de x a y si y sigue a x.

Por ejemplo, sea el conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los divisores de 60). Este conjunto está ordenado parcialmente por la relación de divisibilidad. Su diagrama de Hasse puede ser representado como sigue:

Por ejemplo, en el diagrama de Hasse del poset de todos los divisores de un número n, ordenados parcialmente por divisibilidad, n mismo está en el tope del diagrama, el número 1 estaría en el fondo, y los divisores más pequeños (primos) seguirían al elemento inferior.

Relación con los Grafos

Un diagrama de Hasse puede verse también como un grafo al que se le quitan todos sus bucles y sus aristas que pueden deducirse con la propiedad transitiva y propiedad reflexiva.

La dificultad de encontrar un buen diagrama de Hasse

Las relaciones "seguir a" queda definida de modo único a partir de la relación de orden inicial. Esto hace que las aristas del diagrama de Hasse y los puntos que conectan queden determinados también de forma única. Pero existe un problema adicional: encontrar una ubicación adecuada para los vértices que pueda reflejar alguna de las simetrías subyacentes. En este sentido, encontrar un buen diagrama es difícil.

Se han propuesto varios algoritmos para dibujo de "buenos" diagramas, pero hoy en día su construcción sigue basándose en una fuerte intervención humana. De hecho, incluso un humano necesita bastante práctica para elaborarlos.

Los siguientes ejemplos corresponden a diagramas de Hasse de una misma relación de orden: