Higher Engineering Mathematics

Professor P. N. Agrawal
Department of Mathematics
Indian Institute of Technology Roorkee
Lecture - 17
Lattices - IV

Hello friends, welcome to my lecture on Lattices, let us (cons) continue with our discussion
of different types of Lattices. Let us discuss now a distributive lattice, ok.

(Refer Slide Time: 00:43)

A Lattice is set to be distributive if for any elements a, b, c in L we have the following

distributive laws, a meet b join c equal to a meet to b join a meet c and a join b meet c equal
to a join b and a meet a join c, ok. So, if any lattice satisfies these two distributive laws then it
will be called a distributive lattice. Otherwise, we can call L to be a non-distributive lattice.
Now, by the principle of duality it follows that if a holds good then a lattice then b also holds
good, so if a holds good if and only b hold good b holds good.
(Refer Slide Time: 01:27)

Now, let us consider this example the power set P of a set A, we have to see is a lattice under
the operations of union and intersection. Is P a distributive lattice? This we know that P is a
power set P A is a lattice under the operations of union, so join join operation is the union
operation here and meet operation is the intersection operation, if you take two (ele) elements
P belonging to P A say M, N belong to P A then M union N defines is equal to M join N and
M meet N is equal to M intersection N.

So, with these two operations defined as M union N and M intersection N it follows that the
power set P A is a lattice.

Now, let us see whether it is a distributive lattice, so let us say let us take three sets belonging
to P A, so B, C, D let us say B, C, D belong to P A, ok then we know that, then we know
from said theory that B intersection C union D equal to B intersection C union B intersection
D, ok.

So, this we can write as by this notation B meet C join D equal to B meet C join B meet D,
ok. So, this means that the P A, ok in P A if you take any three sets B, C, D then they satisfies
these distributive law for lattices, ok and by duality theory, by duality? Again the other
distributive law also holds good, so we just have to prove one duality law, the other follows
by the duality principle, ok so thus P A is a distributive lattice, P A is a distributive lattice.
(Refer Slide Time: 04:13)

Now, let us go to this theorem, let us now prove that every chain is a distributive lattice? So
let L with this operation is a, be a chain, ok then any two elements belonging to L are
comparable, that means if a and b belong to L either a precedes b or b precedes a, ok. Now,
let us take three elements a, b, c belonging to L, then if L is a chain either a precedes b or b
precedes a.

Let, us consider that a precedes b, ok then a, (ju) a join b, ok a join b equal to b and a meet b
equal to a, ok hence for any a, b belonging to L both a join b and a meet b they exist and
therefore L is a lattice, ok. Chain is a poset, ok where any two elements are comparable it
becomes a lattice if it, if you take it any elements a, b belonging to L, ok then it is greatest
lower bound glb of a, b and lub of a, b they belongs to L. So here we find that lub of a, b that
is a join b and glb of a, b that is a meet b they belong to L, therefore L is a lattice.

Now, let us assume that a meet b, ok then let us consider various possibilities. First we
consider the case where b precedes c, so a precedes b, b precedes c, now a precedes b and b
precedes c means a precedes c because L is a poset, ok. So by transitivity a precedes c. Now,
let us show that this distributive law holds good here, ok. Since, a precedes b we have a
(persi) a meet b equal to a, ok a meet b equal to a, so this is equal to a, a precedes c gives a
meet c equal to a, ok, so a meet c is equal to a therefore right hand side will be equal to a join
a, ok and a join a equal to a, so right side is a, left side is a meet, now b join c, b precedes c,
so b join c is equal to c, so we get a join c.
Now, a precedes c therefore a join c equal to L a meet c equal to a, ok so left side is a and
right side is also a, so they are equal, so when a precedes b and b precedes c then the
distributive law holds good.

(Refer Slide Time: 07:13)

Now, let us consider the case 2, ok. So this is what I have explained just now, ok in the case
where a precedes b and b precedes c the distributive law holds good.

(Refer Slide Time: 07:23)

Let us go to the case 2, ok. So, now let us assume that b succeed c, ok b succeed c, so b
succeed c means, let b succeed c or c is c precedes b, ok they are same things, b succeed c or
c precedes b. Early we have discussed b precedes c, now we are discussing c precedes b, ok.
So, now here there are two possibilities in case 2 again we have two cases, ok 1 case is that a
precedes c the other case will be a succeed c or you can say c precedes a.

So, what we are doing is now, we are assuming that a precedes b, ok then b precedes c, ok
these are given to us. Now, we are considering 2 a case, 2 a case is a precedes c, ok so we are
given this. Now, a precedes b imply that a meet b equal to a and b precedes b succeeds c, ok b
succeeds c there, b succeed c implies that b join c equal to b, ok and so, now let us the we are
to prove the distributive law, so a meet b join c is equal to a meet b join c equal to b, so we
have a meet b and a is a precedes b, so a meet b will be equal to a, ok because of we said that
a precedes b.

Now, a precedes c, so a meet c equal to a, ok so what we have? So a meet b join a meet c how
much is that? a meet b equal to a, so we get a here join a meet c equal to a so we get a join a
and a join a equal to a and this side, ok a join a meet b join c, ok we have already found equal
to a, so they are equal, ok so distributive law holds good. Now, let us consider case 2 b where
we will assume that a succeed c or you can say c precedes a, ok.

(Refer Slide Time: 09:49)

So, let us case 2 let c precedes a, so, now we have the following a precedes b, ok a precedes b
and b succeed c and c precedes a, ok so, now let c precedes a, ok c precedes a when c
precedes a then what we have? a precedes b, ok c precedes b, ok and then we have c precedes
a. Now, let us prove that distributive law holds good? So a meet b join c, ok b join c is how
much? b join c when you join b when you join b and c, b succeeds c, so b join c will give you
b, ok.

So, a meet b, ok and a meet b will be equal to a because a precedes b, so this is equal to a, so
left hand side is a, and right hand side is a meet b join a meet c, a meet b equal to a, ok
because a precedes b, ok and a joins a meet c, a meet c equal to c because c precedes a, so we
have a join c and a join c is equal to a because c precedes a, ok so we have a here, so again
they are equal. Similarly, now if we consider we started with a precedes b, ok similarly we
take b precedes a we can prove that distributive law holds good.
(Refer Slide Time: 11:35)

Now, let us go to (completive) complete Lattice. A lattice is called complete if each of it is

non-empty subsets has a least upper bound and a greatest lower bound. Let us consider this
lattice (1, 2, 3, 6) 1, 2, 3 and we have 6, ok clearly 1, 2, 3, 6 is a lattice under the divisibility
relation.

Now, L we have to show that L with divisibility relation is a complete lattice, you take any
(two) any subset of this, ok any subset of this you, so subset of this or what? Non-empty
subsets are 1, 2, 3, 6, ok they are semi latin sets and then 1, 2 1, 3 1, 6, ok 1, 2 1, 3 1, 6 then
you can say we have 2, 3 2, 6, ok and we can have 3, 6 and we have 1, 2, 3 like this three
elements, ok.

So 1, 2, 3 then 1, 3, 6 then 1, 2, 6 like that, ok so all these subsets, ok and ultimately we will
have 1, 2, 3, 6 the entire set, ok all these subsets of L under the divisibility operation, ok have
the least and the greatest, least upper bound and greatest lower bound, ok. For example, in
case of 1, 2, 3, 6 there are themselves the least upper bound and the greatest lower bounds
because they are semi latin sets, ok and in case of 1, 2; 1 is the least upper bound, ok 1 is the
greatest lower bound, 2 is the least upper bound, ok and in the case of say 1, 2, 3; 1 is the
least greatest lower bound, 3 is the least upper bound, so like that and so they all belong to
the sets and therefore L is a complete lattice.
(Refer Slide Time: 14:05)

Every finite lattice is complete. Now, every finite lattice we have shown, every finite lattice is
bounded, ok every finite lattice is, so, let us say let the lattice be L, then let L be the finite, L
be a finite lattice, then L is bounded and so L has least element of L has the least element and
the greatest element, ok if you take any subset of L, ok any subset of L is or again a finite set,
ok and therefore is bounded and a bounded lattice has least element and greatest element.

So, all non-empty subsets of L will have a least element and greatest element, have the least
element because they are bounded and therefore, every finite lattice is complete.

(Refer Slide Time: 15:51)

Now, complement of an element in a lattice, let L with this operation be a lattice and let 0 and
1 denote its lower and upper bounds, that mean is 0 is the least element of L and 1 is the
greatest element of L, if a is any element belonging to L, ok then an element b is called
complement of a if a join b equal to 1 and a meet b equal to 0.

(Refer Slide Time: 16:24)

Complemented lattice. Let L with again the operation precedes b a lattice with universal
bounds, we called 0 and 1 which are least and greatest element or I mean named as universal
bounds. So, let this be a lattice with universal bound 0 and 1, the lattice L is called
complemented lattice if every element in L has a complement, ok that is you take any
element L, any element a belonging to L then a join 1 equal to 1, a meet 1 equal to a, a join,
sorry a meet 0 equal to 0, a meet 0 equal to, a join 0 equal to a. So, we will then say that L is
a complemented lattice if every element in L has a complement.
(Refer Slide Time: 17:19)
For example, let us P S, ok with inclusion relation, P S is the power set of any set S is
complemented that means we have to (consi) show that every element belonging to P S has a
complement, ok and then it will be called as a complemented lattice, ok and we said that as
we have seen here complement means if a is an element of L, then b will be called a
complement of a if a join b equal to 1 and a meet b equal to 0.

So, let us first see what are the lowest and greatest elements here in the P S that is 0, 0 what is
0? In the P S with the inclusion relation, ok 0 is equal to phi, ok 0 equal to phi and 1 equal to
S. Now, you take any A belonging to S, ok let A belong to P S, then S minus A, S minus A is
the complement of A because A (uni) now, A union S minus A, ok so meet here is union and
sorry join here is join is union and meet is intersection, ok.

So, A union S minus A (equal to A) is equal to S, S is this 1, ok and we have A intersection S

minus A equal to phi, which is 0, ok A union S minus A means A join S minus A, ok A join
S minus A equal to A union S minus A equal to S equal to 1 and A meet S minus A equal to
A intersection S minus A equal to phi, so S minus A is a complement of A, ok and S minus A
belongs to P S because P S consist of all subsets of the set S, ok.

So, for each A belonging to P S there exist an element B, B will be equal to S minus A which
belongs to P S and satisfies A join S minus A equal to 1, A meet S minus A equal to phi. So,
it is a complemented lattice and the each in this lattice each element has a unique
complement, ok it does not happen that one element has two complements, ok take any set A
belonging to P S its complement is unique.

(Refer Slide Time: 20:40)

The lattice with the figure c, let us look at this figures c, this fig this is a complemented lattice
we can see here, you take any two elements let us say a and b, ok take a and b, 1 is the
greatest element, 0 is the least element, ok. So b is the complement of a, ok b is the
complement of a, because a join b equal to 1, and a meet b equal to 0, ok right. Now, so b is
complement of a, right and then b, c if I take b, c, then b join c equal to 1 and b meet c equal
to 0, ok also a join c equal to 1, a and c if you consider their join is also 1, that mean is 1 is
the greatest element or the least upper bound of a and c and a meet c equal to 0 the greatest
lower bound of a and c is 0.

So, what do we notice here? There are two complements of c, there are two complements of
c, they are a and b, ok. So, the complement it need not be unique, ok. In this case, you can see
one element c has two complements, ok both a and b. So, with this I would like to end my
lecture, thank you very much for your attention.