In this section we introduce lattices as special type of partial ordered set and we discuss basic properties of lattices and some

important type of special lattices.

**6.3.1. Lattice Ordered Sets****
**

In this section we define lattice ordered sets and see some examples.

*A poset (L,*

*£*

*) is called*

**lattice ordered set**if for every pair of elements x, y*Î*

*L, the*

*sup (x, y) and inf (x, y) exist in L.*

**Let S be a nonempty set. Then (**

Example 1:

Example 1:

*P*(S), Í ) is a lattice ordered set. For (

*P*(S), Í ) is a poset. Further for any subsets A, B of S,

inf (A, B) = A Ç B Î

*P*(S) and sup (A, B) = A È B Î P(S).

**Example 2:**

Every totally ordered set is a lattice ordered set (Prove !).

**Example 3:**

Consider the set of all positive integer Z

^{+}with divisor as a relation, i.e., a £ b if and only if a½b.

Then (Z

^{+ }, ½) is a poset.

For, if a, b Z

^{+}, then inf (a, b) = GCD(a, b) Z

^{+ }and sup (a, b) = LCM(a, b) Z

^{+}.

Thus, inf (a, b) and sup (a,b) exist in Z

^{+}for any two element a, b Î Z

^{+}.

Hence (Z

^{+ }, ½) is a lattice ordered set. In fact (D

_{n}

_{ }, ½) ( D

_{n}denotes the set of all positive divisors of positive number n ) is also

a lattice ordered set.

**Consider the set B, where B**

Example 4:

Example 4:

^{n }= {(l

_{1}, l

_{2}, … , l

_{n}) / l

_{i}= 0 or 1, for 1 £ r £ n}.

Define the relation £ ' by (i

_{1}, i

_{2}, … , i

_{n}) £ ' (j

_{1}, j

_{2}, … , j

_{n}) if and only if i

_{r}£ j

_{r}, 1 £ r £ n.

Note that here in the expression i

_{r}£ j

_{r}, £ is usual less than or equal to.

We have already seen in Example 7 of Section 6.2.1 that (B

_{n}, £ ') is a poset.

Observe that

inf [ (i

_{1}, i

_{2}, ….. ,i

_{n}), (j

_{1}, j

_{2}, … , j

_{n})] = (min (i

_{1}, j

_{1}), min (i

_{2},j

_{2}), …. , min (i

_{n}, j

_{n}) ) and

sup [ (i

_{1}, i

_{2}, … , i

_{n}), (j

_{1}, j

_{2}, … , j

_{n})] = (max (i

_{1}, j

_{1}), max (i

_{2},j

_{2}), …. , max (i

_{n}, j

_{n}) )

Since min (i

_{r}, j

_{r}) and max (i

_{r}, j

_{r}) is either 0 or 1,

so, inf { (i

_{1}, i

_{2},… , i

_{n}), (j

_{1},j

_{2}, .. ,j

_{n}) } and sup { (i

_{1}, i

_{2}, … , i

_{n}), (j

_{1}, j

_{2}, … , j

_{n}) } exist in B.

Thus, (B

_{n}, £ ) is a lattice ordered set.

**Example 5:**

Poset represented by the Hasse diagram is not a lattice ordered set since inf (a, b) does not exist.

_{}

Example 6:

Example 6:

Poset represented by the Hasse diagram is not a lattice ordered set as sup (f, g) does not exist.

**:**

Exercise

Exercise

- Prove that if (L, £ ) and (M, £ ' ) are lattice ordered sets. Then (L ´ M, R) is a lattice ordered set, where (a, b) R (x, y)

if and only if a £ x in L and b £ ' y in M. - Check whether the poset represented by the following Hasse diagram that is lattice ordered set or not?

**Remark 1:
**Let (L, £ ) be a lattice ordered set and let x, y Î L. Then the following are equivalent.

(i) x £ y

(ii) sup (x, y) = y

(iii) inf (x, y) = x

**:**

Proof

Proof

( i )

_{ }( ii )

Let x £ y …… (1)

We have, y £ y , for all y Î L. …… (2)

From (1) and (2), we have y is an upper bound of (x, y).

Therefore, sup (x, y ) £ y (by definition of superimum).

But, y £ sup (x, y).

Therefore, y = sup (x, y) (since £ is anti - symmetric).

( ii )

_{}( iii )

Given that sup (x, y) = y. Therefore we have x £ y.

Also, we have x £ x.

Therefore, x is a lower bound for x and y.

Thus, x £ inf (x, y).

But, we have inf (x, y) £ x.

Hence, x = inf (x, y) ( since £ is anti-symmetric).

( iii )

_{}( i )

Given that x = inf (x, y).

Therefore, by the definition of infimum, x £ y.

6.3.2 Algebraic Lattice

ordered sets and algebraic lattices are equivalent.

An

An

**algebraic lattice**(L, *,*Å ) is a non empty set L with two binary operations * (meet) and*Å

*(join), which satisfy the*

following conditions for all x, y, z L.

following conditions for all x, y, z L.

L1. x * y = y * x, x Å y = y Å x (Commutative)

L2. x * (y*z) = (x * y) * z, x Å (y Å z) = (x Å y) Å z (Associative)

L3. x * (x Å y) = x, x Å (x * y) = x (Absorption)

L4. x * x = x, x Å x = x (Idempotent)

**Theorem 3.2.1:**

Let (L, £) be a lattice ordered set. If we define x * y = inf (x, y), x Å y = sup (x, y) then (L, *, Å ) is an algebraic lattice.

**Proof:**

Given that (L, £ ) is a lattice ordered set and x * y = inf (x, y) and x Å y = sup (x, y).

Now we shall prove that * and Å satisfy the commutative, associative, absorption and idempotent laws.

**Commutative**

x * y = inf (x, y) = inf (y, x) = y * x.

x Å y = sup (x, y) = sup (y, x) = y Å x.

Associative

Associative

x * (y * z) = inf (x, (y * z))

= inf (x, inf (y,z))

= inf (x,y,z)

= inf ( inf (x, y), z))

= inf ((x*y), z)

= (x*y) *z.

Now, x Å (y Å z) = sup (x, (y Å z))

= sup (x, sup (y,z))

= sup (x, y,z)

= sup (sup (x,y), z)

= sup ((x Å y), z)

= (x Å y) Å z.

Absorption

Absorption

Now, x * (x Å y) = inf (x, x Å y)

= inf (x, sup (x, y))

= x [since x £ sup (x, y)]

and

x Å (x * y) = sup (x, x * y)

= sup (x, inf (x, y))

= x [since inf (x, y) £ x ].

**Idempotent**

We have, x * x = inf (x, x) = x and x Å x = sup (x, x) = x.

Hence (L, * , Å ) is an algebraic lattice.

**Theorem 3.2.2:**

Let (L, *, Å ) be an algebraic lattice. If we define x £ y

_{}x * y = x or x £ y

_{}x Å y = y, then (L, £ ) is a lattice ordered set.

**Proof:**

Given that (L, *, Å ) is an algebraic lattice and x £ y

_{}x * y = x or x Å y = y.

We shall now prove that (L, £ ) is a poset and inf (x, y) and sup (x, y) exist in L, for all x, y in L.

**£ is reflexive**

Since x * x = x, for all x L (by indempotent of *).

We have by definition of £ , x £ x, for all x Î L.

Therefore, £ is reflexive.

**£ is anti-symmetric**

If x £ y and y £ x in L, then by definition of £ , we have x * y = x and y * x = y.

But * satisfies commutative law, so, we have x * y = y * x.

Therefore, x = y.

Hence, £ is anti-symmetric.

**£ is transitive**

If x £ y and y £ z, then by the definition of £ , we have x * y = x and y * z = y.

Therefore, x * z = (x * y) * z

= x * (y * z) [by associativity of *]

= x * y [by definition £ )]

= x [by definition of £ ]

Hence, by definition of £ , we have x £ z.

Thus, £ is transitive.

sup (x, y) and inf (x, y) exist in L

sup (x, y) and inf (x, y) exist in L

We shall now show that inf (x, y) = x * y and sup (x, y) = x Å y.

Now by absorption law, we have

x = x * (x Å y) and y = y * (x Å y)

Then by the definition of £ , we have x £ x Å y and y £ x Å y

Therefore, x Å y is an upper bound for x and y.

Let z be any upper bound for x and y in L.

Then x £ z and y £ z. So, by definition of £ ,

we have x Å z = z and y Å z = z …… ( 1 )

Therefore, (x Å y) Å z = x Å (y Å z) [by associative law]

= x Å z [by ( 1 )]

= z [by ( 1 )].

Thus, by definition of £ , we have x Å y £ z. that is, x Å y is related to every upper bound of x and y. Hence sup (x, y) = x Å y.

Similarly, we can show that inf (x, y) = x * y.

Thus, x * y and x Å y exists for every x, y Î L.

Hence, we have (L, £ ) is lattice ordered set.

**Remark 1:**

From the Theorem 3.2.1 and the Theorem 3.2.2, we see that if we have lattice ordered set (L, £ ) then we can get an algebraic

lattice (L, *, Å ) and conversely. Hence, we conclude that the algebraic lattice and a lattice ordered sets are equivalent system.

Thus, here after we shall say simply lattice to mean both.

In an algebraic system it is better convenience for imposing further conditions on the binary operations. Hence developing

structural concepts will be much easier than the ordered system. In fact, it is one of the motivation to view a lattice ordered set as

an algebraic lattice.

In this section we discuss sublattices of a lattice, direct product of two lattices and homomorphism between two lattices.

**6.3.3.1 Sublattices****
**

Substructure helps to know more about the whole structure. So, here we discuss about sublattice of a lattice.

*Let (L, *,*

*Å ) be a lattice and let S be subset of L. The substructure (S, *,*

*Å) is a*

**sublattice**of (L, *,*Å ) if and only if S is*

closed under both operations * andÅ

closed under both operations * and

*.*

**Remark 1:**

A subset S in a lattice (L, *, Å ) is said to be sublattice, for a, b S, if a * b = c in L and a Å b = d in L, then c, d must

necessary exist in S also.

**Example 1:**

Consider the lattice L represented by the following Hasse diagram.

Here the substructure S

_{1}represented by the Hasse diagram given below is not a sublattice, for inf (a, b) = 0 in L, which does not

belong to S

_{1}.

It is clear that the substructure S

_{2}represented by the Hasse diagram given below is sublattice of L.

It is interesting to note that the substructure

_{3}of L represented by the in the following Hasse diagram is not a sublattice but it is a

lattice on its own. So, it is a lattice without being a sublattice.

Exercise:

Exercise:

_{30}, ½).

- Let L be a lattice and let a < style="font-family: Symbol;">Î L / a £ x £ b }. Prove

that [a,b] is a sublattice.

**
6.3.3.2 Direct Product of Lattices
**

From given two lattices, we can always construct a new lattice by taking Cartesian product of the given two lattices. So, in this

section we discuss about product of two lattices.

Let (L, *, Å ) and (M,,) be two lattices. Consider the Cartesian product of L and M, that is,

L ´ M = {(x, y) / x Î L, y Î M}.

Define operations D and Ñ in L ´ M, by (x, y) D (a, b) = (x * a, y b) and (x, y) Ñ (a, b) = (x Å a, yb), then we shall prove

that ( L ´ M, D ,Ñ ) is a lattice.

**D**

**and**

**Ñ are commutative.**

By definition (x, y) D (a, b) = (x * a, y b)

= (a * x, b y) (since * and are commutative)

= (a, b) D (x, y) (by definition D ).

Similarly, (x, y) Ñ (a, b) = (x Å a, y b)

= (a Å x, b y)

= (a, b) Ñ (x, y).

Hence, commutative law holds good for both operations D and Ñ .

**D**

**and**

**Ñ are associative**

[ ( x, y) D (a, b) ) D (u, v)] = [ (x * a, y b) ] D (u, v) (by definition of D )

= [ (x * a ) * u, (y b) v] (again by definition of D )

= [ x * (a * u), y (b v) ] (since * and are associative)

= [ (x, y) D (a * u, b v) ] (by definition of D )

= [ (x, y) D [ (a, b) D (u, v) ] (by definition of D )

Similarly we can show that

[ (x, y) Ñ (a, b) ] Ñ (u, v) = (x, y) Ñ [ (a, b) Ñ (u, v) ]

Thus, associative law hold good for both operations and Ñ in L ´ M.

Absorption

Absorption

(x, y) D [ (x, y) Ñ (a, b) ] = (x, y) D [ x Å a, y b]

= [ x * (x Å a), y (y b) ] (by definition of D and Ñ )

= (x, y ) (by absorption law in L and M).

Therefore, absorption law hold good in L ´ M.

Idempotent

Idempotent

(x, y) D (x, y) = [ x * x, y y]

= (x, y) (since * and satisfy idempotent law)

Similarly, (x, y) Ñ (x, y) = (x, y).

Hence, (L ´ M, D , Ñ ) is an algebraic lattice.

Thus, (L ´ M, D , Ñ ) is a lattice.

**Remark 1:**

If (L, *, Å ) is a lattice, then L² = L x L is a lattice. In general one can show that

L

^{n}= L ´ L ´ L ´ …. ´ L (n times) is a lattice.

In the finite lattices, B

^{n}is a very important lattices, where B = {0,1}, which has rich structural property and will play very

important role in the applications.

Let (L, £ ) and (M, £ ' ) be two lattices, then we have already seen that (L ´ M, R) where (x

_{1}, y

_{1}) R (x

_{2}, y

_{2}) if and only if

x

_{1 }£ x

_{2}and y

_{1}£ ' y

_{2}, is a poset. It can be proved that

(L ´ M, R) is a lattice ordered set. [ Prove !]

6.3.3.3 Homomorphism

In this section to understand the structural similarity between two lattices we define homomorphism between two lattices and we

discuss about it.

*(L, *, Å )*

Let

Let

*and*(M, ,)

*be two lattices. A function*f : L ® M

*is called a*

*Lattice homomorphism**if*

f (a * b) = f (a) f (b) and

f (a Å b) = f (a) f (b),

*for all*a, b Î L,

and it is called

and it is called

**order preserving**if x*£*f (x)

_{ }y in L implies*' f (y)*

_{}*, where*£

relation in M.

A bijecitve homomorphism is called

_{ }is an order relation in L and_{}' is an orderrelation in M.

A bijecitve homomorphism is called

**isomorphism**.**Example 1:**

Consider the lattices D

_{6}= {1,2,3,6} and D

_{30}= {1,2,3,5,6,10,15,30}. We can show that there exist a homomorphism

*f*

between D

_{6}and D

_{30}.

Define a mapping f from D

_{6}into D

_{30}by

*f*(1) = 1,

*f*(2) = 6,

*f*(3) = 15 and

*f*(6) = 30.

Then

*f*(1 * 2) =

*f*(1) = 1.

*f*(1) * f(2) = 1 * 6 = 1.

[Note that in both D

_{6}and D

_{30 }a * b and a Å b are GCD and LCM of two element a, b]

Similarly,

*f*(1 * 3) =

*f*(1) =

*f*(1) *

*f*(3).

*f*(1 * 6) =

*f*(1) *

*f*(6) =

*f*(1).

*f*(2 * 3) =

*f*(2) *

*f*(3) =

*f*(1).

*f*(2 * 6) =

*f*(2) *

*f*(6) =

*f*(2).

*f*(3 * 6) =

*f*(3) *

*f*(6) =

*f*(3).

Similarly we can prove that

*f*(x Å y) =

*f*(x) Å

*f*(y) for all x, y D

_{6}.

Thus,

*f*is homomorphism.

Note that

*f*is not onto but

*f*is one-one.

Hence f is not an isomorphism.

Exercise 1:

Exercise 1:

It is very interesting to prove that the mapping f defined from B

^{n}into

*P*(A

_{n}), where

A

_{n}= {1,2, …. , n} by

*f*(i

_{1}, i

_{2}, …. , i

_{n}) = { k / i

_{k}¹ 0} is a homomorphism.

6.3.3.4 Special Lattices

**6.3.3.4.1 Isotone, Distributive and Modular Inequalities**

**In this subsection we shall prove that in every lattice the operation * and Å are isotone and distributive and modular inequalities**

holds good.

Lemma 3.4.1.1:

Lemma 3.4.1.1:

In every lattice L the operation * and Å are isotone,

i.e., if y £ z Þ x * y £ x * z and x Å y £ x Å z.

Proof:

Proof:

x * y = (x * x) * (y * z) (since x * x = x and since y £

_{ }z, y * z = y)

= (x * y) * (x * z) (by associative and commutative of *).

_{}x * y £ x * z (since a £

_{ }b

_{}a * b = a).

Also, x Å z = (x Å x) Å (y Å z)

= (x Å y) Å (x Å z)

_{}x Å y £ x Å z.

Hence the lemma.

**Theorem 3.4.1.2:**

The elements of an arbitrary lattice satisfy the following inequalities

- x * (y Å z) ³ (x * y) Å (x * z)

x Å (y * z) £ (x Å y) * (x Å z) (distributive inequalities.) - x ³ z
_{}x * (y Å z) ³ (x * y) Å (x * z) = (x * y) Å z

x £ z_{}x Å (y * z) £ (x Å y) * (x Å z) = (x Å y) * x (modular inequalities.)

**
Proof:
Claim: **

*Distributive inequalities are true in a lattice.*

By definition of Å, y £ y Å z and z £ y Å z.

By isotone property

we have x * y £ x * (y Å z) ............... (1)

and x * z £ x * (y Å z) ............... (2)

From (1) and (2) we observe that x * (y Å z) is an upper bound for x * y and x * z.

Hence, (x * y) Å (x * z) £ x * (y Å z).

By duality principle, we have (x Å y) * (x Å z) ³ x Å (y * z).

ii) It is given that z £ x, then by Theorem 3.2.2 z * x = z.

From the inequality ( i ) we have x* (y Å z) ³ (x*y) Å (x*z).

Therefore, x * (y Å z) ³ (x * y) Å z.

Since x £ z, we have x Å z = z.

Thus, from the inequality x Å (y * z) £ (x Å y) * (x Å z), we have

x Å (y * z) £ (x Å y) * z.

Hence the theorem.

6.3.3.4.2 Modular Lattices

6.3.3.4.2 Modular Lattices

In this section we shall define and discuss about the modular lattices.

*A lattice L is said to be*

if for all x, y, z

**modular**

if for all x, y, z

*Î L, x*

*£ z*

*Þ x * (y*

*Å z) = (x * y)*

*Å z.*

**Example 1**:

(

*P*(A), Ç , È ) is a modular lattice [ Proof left as an exercise].

**:**

Example 2

Example 2

The set of all normal subgroups of a group form a modular lattice. [Recall that a subgroup H of a group G is said to be normal if

gHg

^{-1}= H, for all g Î G]. It can be easily shown that M, the set of normal subgroups of a group G, with `set inclusion' relation is

a poset.

Now for any two normal subgroups H

_{1}and H

_{2}of G, we have

H

_{1}* H

_{2}= inf (H

_{1}, H

_{2}) = H

_{1}Ç H

_{2}and

H

_{1}Å

_{ }H

_{2}= sup (H

_{1}, H

_{2}) = H

_{1}H

_{2}.

Since H

_{1}Ç H

_{2}and H

_{1}H

_{2}are normal subgroups if both H

_{1}and H

_{2}are normal subgroups. Therefore, (M, Í ) is a lattice ordered

set. Hence (M, *, Å ) is an algebraic lattice. Let H

_{1}, H

_{2}, H

_{3}, Î M such that H

_{1}Í H

_{3}. Since in every lattice modular inequality

holds good, we have H

_{1}(H

_{2}* H

_{3}) Í (H

_{1}Å H

_{2}) * H

_{3}………. (1)

Now we shall prove that (H

_{1}Å H

_{2}) * H

_{3}Í H

_{1}Å (H

_{2}* H

_{3}).

Let a Î (H

_{1}Å H

_{2}) * H

_{3 }i.e., a Î (H

_{1}H

_{2}) Ç H

_{3 }a Î H

_{1}H

_{2}and a Î H

_{3 }a = h

_{1}h

_{2}and a = h

_{3}, for some h

_{1}Î H

_{1},h

_{2}Î H

_{2}and h

_{3}Î H

_{3}.

Therefore, h

_{1}h

_{2}= h

_{3 }

_{}h

_{2}= h

_{1}

^{-1}

_{ }h

_{3}Î H

_{3}[ h

_{3}Î H

_{3}and h

_{1}Î H

_{1}Í H

_{3}, therefore, h

_{1}

^{-1}h

_{3}Î H

_{3}]

_{}h

_{2}Î H

_{2}and h

_{2}Î H

_{3}

Thus, h

_{2}Î H

_{2}Ç H

_{3}……… (2)

Since a = h

_{1}h

_{2}, we have a Î H

_{1}(H

_{2}Ç H

_{3}) (by (2))

That is, aÎ H

_{1}Å

_{ }(H

_{2}* H

_{3})

That is, (H

_{1}Å

_{ }H

_{2}) * H

_{3}Í H

_{1}Å

_{ }(H

_{2}* H

_{3}) ………. (3)

From (1) and (3) we have

H

_{1}Å (H

_{2}* H

_{3}) = (H

_{1}Å H

_{2}) * H

_{3}.

Hence (M, *,Å ) is a modular lattice.

**Theorem 3.4.2.1:**

A lattice L is modular if and only if x, y, z Î L , x Å (y * (x Å z)) = (x Å y) * (x Å z).

**Proof :**

Let (L, *, Å ) be a modular lattice

Then, if x £ z implies x Å (y * z) = (x Å y) * z ……… (1)

But, for all x , z Î L, x £ x Å z,

So, by (1) we have

x Å (y * (x Å z)) = (x Å y) * (x Å z), for all x, y, z Î L

Conversely, suppose x Å (y * (x Å z)) = (x Å y) * (x Å z). ……… ( 2 )

Then we shall prove that L is modular.

If x £ z then x Å z = z ………. (3)

Substitute (3) in (2), we have if x £ z Þ x Å (y * z) = (x Å y) * z

Thus, (L, *, Å ) is modular.

If we have a characteristic result in terms of Hasse diagram for the modular lattice then it would effectively help in deciding a given

lattice is modular or not. So, we shall prove the following lemma.

Lemma 3.4.2.1:

Lemma 3.4.2.1:

The "Pentagon Lattice" represented by the Hasse diagram given below is not modular.

**From the structure of the pentagon lattices we see that c £ a.**

Proof:

Proof:

Now c Å (b * a) = c Å 0 = c. On the other hand, (c Å b) * a = 1 * a = a.

Definitely c ¹ a, thus, pentagon lattice is not a modular lattice.

On the other hand, it can be proved that if any lattice whose substructure is isomorphic to a pentagon lattice cannot be a

modular lattice. So, we have the following theorem.

**A lattice L is modular if and only if none of its sublattice is isomorphic to the "pentagon lattice" [ for the detailed proof refer [2]]**

Theorem 3.4.2.2:

Theorem 3.4.2.2:

**Prove that the intervals [x, x Å**

Exercise 1:

Exercise 1:

_{ }y] and [ x * y, y] are isomorphic in a modular lattice. [ By interval [u ,v] we mean the set

{ t Î L / u £ t £ v }]

**Prove that if a ³ b and if there exists c Î L with a Å c = b Å c and a * c = b * c then a = b.**

Exercise 2:

Exercise 2:

**
6.3.4.3 Distributive Lattices**

A lattice (L, *,

A lattice (L, *,

*Å) is called a*

**distributive lattice**if for any a, b, c*Î L,*

a * (b Å c) = (a * b) Å (a * c)

a Å (b * c) = (a Å b)*(a Å c)

**(**

Example 1:

Example 1:

*P*(A), Ç , È ) is a distributive lattice. [ For proof refer Section1.2]

Example 2:

Example 2:

Every totally ordered set is a distributive lattice.

**Proof:**

In a totally ordered set (T, £ ) for any two elements a, b in T, we have either a £ b or b£ a. Therefore, for any three elements a,

b, c in T, the following are the possible situations in the structure of (T, £ ).

All these possible choices can be covered in the following two cases.

**Case 1:**a £

_{ }b or a £

_{ }c [ the first four choices ]

**Case 2:**a ³ b and a ³

_{ }c [ the last two choices ]

For the case 1, we have,

a*(b Å c) = a and (a * b) Å

_{ }(a * c) = a Å

_{ }a = a

For the case 2, we have,

a*(b Å

_{ }c ) = b Å

_{ }c and (a * b) Å

_{ }(a * c) = b Å

_{ }c

Hence any totally ordered set (T, £

_{ }) is a distributive lattice.

**The set of all positive integers Z**

Example 3:

Example 3:

^{+}, ordered by divisibility is a distributive lattice.

**Proof:**

We know that (Z

^{+}, ½ ) is lattice, where x * y = GCD(x, y) and x Å

_{ }y = LCM(x, y), for x, y Î Z

^{+}.

Since every positive integer can be expressed as product of powers of primes,

Let x =

_{}, y =

_{}and z =

_{}.

Note that x

_{i }, y

_{i}, z

_{i }may be zero also.

Now , y * z =

_{ }

x Å (y * z) =

_{}

=

_{}

=

_{}*

_{}

= (x Å

_{ }y) * (x Å

_{ }z)

Remark 1:

Remark 1:

It is clear from the definition of distributive lattice that if a ³ c then a * c = c and a Å

_{ }c = a.

Therefore, a * (b Å

_{ }c) = (a * b) Å

_{ }(a * c)

= (a * b) Å

_{ }c.

If a £ c then a * c = a and a Å

_{ }c = c.

Therefore we have a Å

_{ }(b * c) = (a Å

_{ }b) * (a Å

_{ }c)

= (a Å

_{ }b) * c.

Thus, every distributive lattice is modular.

On the other hand every modular lattice need not be distributive.

For example, the following modular lattice called

*diamond lattice*is not distributive lattice.

Diamond Lattice:

Diamond Lattice:

For,Å

_{ }(b * c) = a Å

_{ }0 = a

(a Å

_{ }b) * (a Å

_{ }c) = 1 * 1 = 1

Therefore, aÅ

_{ }(b * c) ¹ (a Å

_{ }b) * (a Å

_{ }c).

Hence, a diamond lattice is not a distributive lattice.

It is interesting to observe that if a lattice is not modular it cannot be a distributive lattice.

It follows from the Theorem 3.4.2.2. and the above Remark1, we have the following theorem which will effectively decide the

given lattice is distributive or not.

Theorem 3.4.3.1:

Theorem 3.4.3.1:

A lattice is distributive iff none of its sublattice is isomorphic to either the pentagon lattice or diamond lattice.

[ For the proof refer [ 2 ] ]

Exercise:

Exercise:

Prove that the direct product of two distributive lattices is a distributive lattice.

**Let (L, *, Å**

Theorem 3.4.3.2:

Theorem 3.4.3.2:

_{ }) be a distributive lattice. Then for any a, b, c Î L,

a * b = a * c and a Å

_{ }b = a Å

_{ }c Þ b = c [cancellation law].

**Proof:**

(a * b) Å

_{ }c = (a * c) Å

_{ }c = c (since a * b = a * c and by absorption law, (a * c) Å

_{ }c = c)

Now, (a * b) Å

_{ }c = (a Å

_{ }c) * (b Å

_{ }c) (by distributive law)

= (a Å

_{ }b) * (b Å

_{ }c) (since a Å

_{ }c = a Å

_{ }b)

= b Å

_{ }(a * c) (by distributive law)

= b Å

_{ }(a * b) (since a * c = a * b)

= b (by absorption law)

Hence, b = c .

3.4.4 Complemented Lattices

In this section we shall define complemented lattices and discuss briefly.

In a lattice (L, *, Å ), the greatest element of the lattice is denoted by

**1**and the least element is denoted by

**0**.

If a lattice (L, *,Å ) has

**0**and

**1**, then we have,

x *

**0**=

**0**, x Å

_{ }

**0**= x, x *

**1**= x, x Å

_{ }

**1**=

**1**, for all x Î L.

*A lattice L with*

**0**and**1**is**complemented**if for each x in L there exists atleast one y*Î L such that x * y =*

xÅ

**0**andx

_{ }y =**1**and such element y is called complement of x.**Note:**

It is customary to denote complement of x by x'.

**Remark 1:**

It is clear that complement of

**1**is

**0**and vice versa.

Example 1:

Example 1:

Consider the lattice (

*P*(A), Í )

Here

**0**= f and 1 = A.

Then, for every S Î

*P*(A), that is, S Í A, complement of S is A\ S, i.e. S'.

**Example 2:**

Consider the lattice L described in the Hasse diagram given below.

Here, c does not have a complement.

For, c *

**0**=

**0**, but, c Å

**0**= c.

Therefore,

**0**can not be a complement of c.

Since a Å c = c, therefore, a can not be a complement of c.

Further, since c * b = c, b is not a complement of c.

Also, c *

**1**= c,

**1**is not a complement of c.

Hence, c does not have any complement in L.

Therefore, L is not a complemented lattice.

**Example 3:**

In a totally ordered set, except

**0**and

**1**, all the other elements do not have complements.

**Example 4:**

Consider the lattice L described by the Hasse diagram given below.

Here, for c, we have, c * a =

**0**and c Å a =

**1**and also, c * b = 0

and c Å b =

**1**.

Thus, c has a and b as its complements.

From this example, it is clear that complement of an element in a complemented lattice need not be unique.

Theorem 3.4.5.1:

Theorem 3.4.5.1:

In a distributive lattice L with

**0**and

**1**, if a complement of an element exists then it is unique.

**Proof:**

Let L be a distributive lattice with

**0**and

**1**. Let aÎL. Suppose a' and a" be two complement of a. Then by the definition of

complement of an element, we have

a * a' =

**0**and a Å a' =

**1**

a Å a" =

**0**and a Å a" =

**1**

Therefore, a * a' = a * a" and a Å a' = a Å a".

Therefore by cancellation law in a distributive lattice, we have a' = a".

Thus, complement of an element in a distributive lattice is unique.

**Exit Quiz Questions:**

- Is the poset A = {2, 3, 6, 12, 24, 36, 72} under the relation of divisibility a lattice.
- If L
_{1}and L_{2}are the lattices shown in the following figure, draw the Hasse diagram.of L_{1}´ L_{2}with product partial order.

- Show that a subset of a totally ordered set is a sublattice.
- Find all the sublattices of D
_{24}that contains at least five elements. - Shows that sublattice of a distributive lattice is distributive.
- Show that the lattice given below is not a distributive lattice but modular.

- Find the complement of each element of D
_{42}. - Determine whether the lattice given below is distributive, complemented or both.

## No comments:

Post a Comment