CHAROTAR UNIVERSITY OF SCIENCE AND TECHNOLOGY

FACULTY OF APPLIED SCIENCES

DEPARTMENT OF MATHEMATICAL SCIENCES
SEMESTER 3 B.Tech. (CE/ IT/ CSE)

DISCRETE MATHEMATICS AND ALGEBRA

MA253
Unit-2 Relations and Lattice
CARTESIAN PRODUCT: Let A and B be sets. Cartesian product of A and B ,
denoted by A×B, is defined as

A  B = ( a, b ) : a  A and b  B

RELATION ON SETS: Let A and B be two sets. A relation from A to B is a subset

of the Cartesian product AXB. Suppose R is a relation from A to B. Then R is a set
of ordered pairs (a, b) or aRb where a is in A and b is in B. Every such ordered pair
is written as (a, b) or aRb and read as “ a is related to b by R”.
DOMAIN AND RANGE OF RELATION R:
Domain: The set a  A : ( a, b )  R for someb  B is called the domain of R and
denoted by Dom(R).
Range: The set b  B : ( a, b )  R for some a  A is called the range of R and denoted
by Ran(R).
Thus, the domain of relation R is the set of all first elements of the ordered pairs
which belong to R and the range is the set of second element.
Example: Let A={ 2, 3, 5} , B={ 2, 4, 6, 10} . A relation from A to B is given as
follows: {2R2, 2R4,2R6, 2R10,3R6,5R10}.Write R as a set of ordered pair.
Solution: R={ (2,2),(2,4), (2,6),(2,10), (3,6),(5,10)}.

Total number of distinct relation from a set A to a set B .

Let the number of element of A and B be m and n respectively. Then the number
of elements in AXB is mn. Therefore, the number of elements of the power set of
AXB is 2mn. Thus AXB has 2mn subsets. Now every subset of AXB is a relation from
A to B. Hence ,the number of different relation from A to B is 2mn.

TYPES OF RELATION
Inverse Relation: Let R be the relation from set A to set B. The inverse of R is
denoted by R-1 is the relation from B to A which consist of those ordered pairs
which , when reversed, belong to R that is
R-1={(b, a): (a, b)∈ R}.

Example: Let A={1,2,3} and B={a, b} and R={ (1,a), (1,b),(3,a), (2,b)} be a relation
defined from A to B. Then find R-1.
Solution: R-1={ (a,1), (b,1), (a,3), (b,2)}.
Identity Relation: A relation R on a set A to A is said to be identity relation IA.
i.e., IA={(x, x): x∈ A}.

For example, Let A={2,4,6}. IA={(2,2),(4,4),(6,6)} is an identity relation on A.

Complement of Relation: Let R be a relation defined on set A× 𝐵 .Then complement of the
relation is denoted by Rc or 𝑅ത . Then 𝑅ത is defined as ={ (a, b) :(a, b)  A  B and (a, b)  R}

i.e., =(A×B)-R.

Combining Relation: Given two relations R1 and R2, we can combine them using basic set
operations to form new relations such as R1 ∪ R2, R1 ∩ R2 and R2 − R1.
For example: Let A = {1,2,3} and B = {1,2,3,4}. The relations
R1 = {(1,1),(2,2),(3,3)} and R2 ={(1,1),(1,2),(1,3),(1,4)}
can be combined using basic set operations to form new relations:
R1 ∩ R2 ={(1,1)}
R1 ∪ R2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)}
R2 − R1 ={(1,2),(1,3),(1,4)}
 PROPERTIES (TYPES) OF RELATION

Let A={ 1,2,3,4}

Remark: Total number of element in A =n. Therefore no. of element in Cartesian
product AXA =nXn.

IRREFLEXIVE RELATION: A relation R on a set A to A is said to be irreflexive if a∈

A, (a,a) does not belong to R. It is also called as antireflexive.
Let A={ 1,2,3,4}

Remark: If the relation is not reflexive then it is not compulsory that it is irreflexive.
For example relation R1 is neither reflexive nor irreflexive.
Antisymmetric Relation:
A relation R on set X is said to be antisymmetric if aRb and bRa, then a = b.

Remark: Antisymmetric is not the same as symmetric. A relation may be

symmetric as well as antisymmetric at the same time.
For example, R5={(a,a),(b,b),(c,c)} is both symmetric and antisymmetric on
A ={a,b,c}.
Transitive:

A relation R over a set X is said to be transitive if for all

elements a, b, c in X, whenever R relates aRb and bRc, then aRc.

Following are the example of

R={(a, b),(b, a),(a, a),(b, b)} and R=AXA transitive relation.

EQUIVALENCE RELATION: A relation R on set S to S is called an EQUIVALENCE RELATION
if it is reflexive, symmetric and transitive (RST). That is, R is an equivalence relation on A if it
satisfy the following properties:

R is not a reflexive and transitive. R is a symmetric. Therefore R is not an Equivalence Relation.

EQUIVALENCE CLASSES: If R is an equivalence relation on a set S and (x, y) or xRy,
then x and y are called respect to R. The set of all elements of S that are equivalent to a
given element x constitute the equivalence class of x and equivalence class is denoted
by [x].
Thus [x] = {y∈ S:yRx}.
PARTITIONS OF SET: A partition of a set A is a set of non –empty subsets of A
denoted by { A1,A2,.....An} such that the union of Ai ‘s is equal to A and intersection of
Ai and Aj is empty for any distinct Ai and Aj.
Example : Let A={ 1,2,3,4,5} and R={(1,2), (1,1),(2,1),(2,2),(3,3),(4,4),(4,5),(5,4),(5,5)}
Show that R is an equivalence relation on A. Determine the partition
corresponding to R.
Solution: show that R is an equivalence relation on (Homework)
Then Equivalence class of
[1]={1,2}; [2]={1,2}; [3]={3}; [4]={4,5} ; [5]={4,5}
Thus partition set corresponding to R
P={ {1,2},{3}, {4,5}}
Note: Using Cross product between element to it self in a partition set, One can find
equivalence relation from partition.
Example: Let R is an equivalence relation on set A = {a, b, c, d}
defined by partitions of P{{a, d},{b, c}}. Determine the element of
equivalence relation and also find the equivalence classes of R.
Solution:
The elements of equivalence relation defined by partition P is
R={(a, a), (d, d), (a, d),(d, a), (b, b),(c, c), (b, c),(c, b)}.
The equivalence classes of R are [a]=[d]={a, d} and [b]=[c]={b, c}.

Example: Show that the relation (x, y)R(a, b), x2+y2= a2+b2 is an
equivalence relation on plane.
Solution:
Reflexive :
(x, y)R(x, y) ⇔x2+y2= x2+y2
Therefore R is reflexive .
Symmetric : Let (x, y)R(a, b)⟹ x2+y2= a2+b2
⟹ a2+b2 =x2+y2
⟹ (a, b)R (x, y)
R is symmetric.

Transitive:
Let (x,y)R(a,b) and (a,b)R( c,d), x2+y2= a2+b2 and a2+b2=c2+d2
⟹ x2+y2= c2+d2
⟹(x,y)R (c,d)
Therefore R is transitive.
Since R is reflexive , symmetric and transitive therefore R is an
equivalence relation.
PARTIAL ORDERED RELATION: A relation R on set S is called a partial order if
it is reflexive, antisymmetric and transitive (RAT). That is

..
POSET: A set S together with a partial order relation R or ≼ is called partial
order set or POSET and is denoted by (S, R) or (S, ≼).
 Practice Example
Example: Show that the set (Z+,/) is a POSET where the relation a/b means a
is divisible by b.

Example: Check that the set (R, ≥) is a POSET or not, where the relation a ≥
b means a is greater or equal to b.
 REPRESENTATION OF RELATION

There are many ways of representing relations on finite sets. Graphical methods
are particularly useful for visualising the information about relations. It is more
convenient to represent Relations as matrices to do mathematical calculations.
MATRIX REPRESENTATION:

Let A={a1, a2, a3,...,an} and B={ b1,b2,b3,...,bm} are finite sets containing n and m
elements respectively and let R be a relation from A to B. The relation R can be
represented by n×m matrix, MR=[mij], where

1, if (ai , b j )  R
𝑀𝑅 = mij=  .
 0 if ( ai , b j )  R

Then matrix MR is called the matrix of R.

Example: Let R be the relation from set A={1,3,4} on itself and defined by
R={(1,1), (1,3), (3,3), (4,4)}. Then find the matrix of R.

Solution: Let MR denotes the matrix of R.

The number of rows in MR=number of elements in A=3. Since the relation from
the set A on itself, the number of column in MR is also 3. So MR is 3x3 matrix.
Example : Let A={ a1, a2, a3} and B={ b1,b2,b3, b4} which ordered pairs are in
the relation R represented by the matrix
b1 b2 b3 b4
a1 0 1 0 0 
M R = a2 1 0 1 1  .
a3 1 0 1 0 

Find the relation R from given Matrix.

Solution:
Since R contains of those ordered pairs (ai, bj) with mij = 1.
It follows that R={ (a1,b2),(a2,b1),( a2,b3),(a2,b4),(a3,b1), (a3,b3) }
Remarks:
The matrix representing a relation can be used to determine whether the relation
has various properties i.e. reflexive, irreflexive, symmetric, asymmetric,
antisymmetric and transitive.
1) Reflexive: If all the elements in the main diagonal of the matrix representation of
relation are 1 i.e., mii=1, then the relation is reflexive. For example,

1 0 0 
M R = 0 1 0  .
0 0 1 

2) Irreflexive: If all the elements in the main diagonal of the matrix representation of
relation are 0, then the relation is irreflexive. For example,
0 0 1 
M R = 0 0 0  .
1 1 0 

3) Symmetric: If the representative matrix of a relation is symmetric with respect to

the main diagonal, i.e., mij=mji for all value of i and j then the relation is symmetric.
( i.e., MR=MRT).
4) Antisymmetric: A relation is antisymmetric if and only if mij=1 at a same time
mji=0.The following matrices illustrate the notions of symmetry and antisymmetric.

5) Asymmetric: A relation is asymmetric iff mii=0, mij=1 and mji=0.

0 1 1
For example, 𝑀 = 0 0 0
0 1 0
6) Transitive: A relation R is transitive if and only if MR2+MR=MR.
Note:
When we take product or sum of MR (Matrix of relation R) at that time entries of new matrix of
product or sum must be 1 or 0. If it is more than one, then take that entry as 1.
Example: Let A={1,2,3,4} and let R be a relation on A whose matrix is
1 1 1 1
0 0 0 0 
MR = 
1 1 1 1  . Show that R is transitive.
 
0 0 0 0

Therefore, relation R is transitive.

 GRAPHICAL REPRESENTATION

Let A and B are two finite sets and R is a relation from A to B.

For graphical representation of a relation on a set, each element of the set is

represented by a point. These points are called nodes or vertices.

An arc is drawn from each point to its related point. The arcs start at the first
element of the pair, and they go to the second element of the pair. The direction is
indicated by an arrow. All arcs with an arrow are called directed arcs. The resulting
image is called a directed graph or diagraph of R. An edge of the form (a, a) is
represented using an arc from the vertex a back to itself. Such an edge is called
loop.
For example, Let A={ 2,4,6} and B={ 4,6,8} and R be the relation
from the set A to the set B given by xRy means x is a factor of y, then
R={(2,4),(2,6), (2,8),(4,4),(6,6),(4,8)}.

This relation R from A to B is represented by the arrow diagram as

shown in figure:
Remarks:
The directed graph representing a relation can be used to determine various
properties a relation:
(1) A relation is reflexive if and only if there is a loop at every vertex of the directed
graph, so that ordered pair of the form (a,a) occurs in the relation. If no vertex has a
loop then the relation is irreflexive.
(2) A relation is symmetric if and only if for every edge between distinct vertices in its
digraph there is an edge in the opposite direction, that is if (b, a) is in the relation
whenever (a, b) is in relation. A relation is antisymmetric if no two distinct points in
the diagraph have an edge going between them in both directions.
(3) A relation is transitive if and only if whenever there is a directed edge from to
vertex a to a vertex b and from a vertex b to vertex c , then there is also a directed edge
from a to c.
Every diagraph determines a relation, so that we may recover R from the graph.
Domain and Range can be found easily if the relation is represented by a graph. Every
node with an outgoing arc belongs to the domain and every node with an incoming
arc belongs to the range.
EXAMPLE: Draw the directed graph that represents the
relation R={ (1,1),(2,2),(1,2),(2,3),(3,2),(3,1),(3,3)} on X.
Solution:
EXAMPLE: Determine whether the relation for the directed
graph shown in figures are reflexive, symmetric ,
antisymmetric and transitive.

R1 R2
REPRESENTATION AND HASSE DIAGRAM

HASSE DIAGRAM: A partial order relation on X can be represented

by means of a diagram known as Hasse diagram of X.

This gives a method of representing finite poset. We represent the

element of x by points and if y is an immediate successor of x we
take y at a higher level than x and join x and y by a straight line. A
diagram formed as above is known as Hasse diagram.

Thus, there will not be any horizontal lines in the diagram of a

poset.
Example: Let A={ 1,3,9,27,81} , draw the Hasse diagram of the Poset
(A,/).
Example: Let X={1,2,3,4,5,6}, then / is partial order relation on X.
Draw the Hasse diagram of (X,/)
Solution
Example: Draw the Hasse diagram for the partial ordering { (A,B):
A ⊆ B} on the power set P(S) where S= { a,b,c}
Solution: Here P(S)={ ∅,{a}, {b},{c}, {a,b},{a,c},{b,c}, {a,b,c}}. The
Hasse diagram of the poset (P(S), ⊆) is shown below
SPECIAL ELEMENT IN POSETS
MAXIMAL ELEMENT: An element ‘a’ in the poset is called maximal element of P
if 𝑥 ≺ a for every x in P, i.e. No element of P strictly succeeds ‘a’.

MINIMAL ELEMENT: An element ‘b’ in P is called minimal element of P if 𝑏 ≺x

for every x in P.

Remark: Maximal and minimal element are easy to spot in the Hasse diagram,
They are the top and bottom elements in the diagram. That is a maximal element
has no connections leading up and minimal element has no connection leading
down. Also, it is not necessary that Maximal and minimal element are
unique.

Maximal elements : a, b
Minimal elements : d, e
Maximal elements : a, e
Minimal elements : d, f

Maximal element : f
Minimal element : a
MAXIMUM ELEMENT (GREATEST ELEMENT): Let (P, ≤) be a poset. An
element a in P is the greatest element of P if 𝑥 ≤ 𝑎 for all x ∈ P i.e., every element
in P precede a. OR An element of poset is said to be maximum if it is maximal
and every element is related to it. Also, maximum element is a unique point.

MINIMUM ELEMENT ( LEAST ELEMENT) : Let (P, ≤) be a poset. An element a

in P is the least element of P if 𝑎 ≤ 𝑥 for all x ∈ P i.e., every element in P
succeeds a. OR An element of poset is said to be minimum if it is minimal and
every element is related to it. Also, minimum element is a unique point.

Maximal and maximum element : f

Minimal and minimum element : a
 Maximum and minimum
element does not exist

Maximum element does not exist

Minimum element is d.

Maximum element is a
Minimum element is d.
Remarks: The following points are to be noted
1) A poset may not have maximal element. For instance, the set of
natural numbers N under the operation ≤ have no maximal
element. Minimal element exists and it is 1.
2)A poset may have a maximal element but no minimal elements, or
minimal element but no maximal elements.
-
For example, the poset (Z , ≤) has a maximal element as -1 but no
minimal element, whereas the poset (Z+, ≤) has minimal element
as 1 but no maximal element.
3) A poset may not have a maximal element and minimal elements.
For example, the poset (R, ≤) has no maximal element and minimal
element.
UPPER BOUND: Let B be a subset of a poset (A, ≤). An element ‘u’ in A is called an
upper bound of B if ‘u’ succeeds every element of B i.e., x ≤ u for all x in B.

LOWER BOUND: Let B be a subset of a poset (A, ≤). An element ‘l’ in A is called a
lower bound of B if ‘l’ precedes every element of B i.e., l ≤ x for all x in B.

LEAST UPPER BOUND : Let B be a subset of a poset (A, ≤). An element ‘a’ in A is
called least upper bound (lub) of B. If ‘a’ is an upper bound of B and a ≤ a’ whenever
a’ is the upper bound of B. That means it is one of the upper bound element
which is less than all the other upper bounds.(It is a unique.)

GREATEST LOWER BOUND: Let B be a subset of a poset (A,≤). An element ‘a’ in A

is called the greatest lower bound (glb) of B if ‘a’ is lower bound of B and a’ ≤ a,
whenever a’ is a lower bound of B. i.e. it is one of the lower bound element which is
greater than all the other lower bounds. (It is a unique.)

There are the elements which are greater than or equal to all the element of subset B of a
poset.
Find the Maximal element, Minimal element, Maximum element, Minimum
element, Upper bound, Lower bound, Least upper bound and Greatest lower
bound for the sub set A={8, 9} of poset (S, ≤), where S={1, 2, 4, 8, 9, 10, 15, 16}.
Solution : Here we have a poset (S,≤), where S={1, 2, 4, 8, 9, 10, 15, 16}
. A ={8, 9} is a subset of S={1, 2, 4, 8, 9, 10, 15, 16}
Maximal elements are 9,10, 15 and 16.
Minimal elements are 1,2, 4 and 8.
Maximum element is 16.
Minimum element is 1.
Upper bounds are 9, 10, 15 and 16.
Lower bounds are 1, 2, 4 and 8.
Least upper bound is 9.
Greatest lower bound is 8.
Find the Upper bound, Lower bound, Least upper bound and Greatest lower
bound for the following Hasse diagram for given set if exists.
B={c, d} B={a, b }

UB is a, c and e. UB is a.

LB is d. LB is b and d.

LUB is c. LUB is a.

GLB is d. GLB is b.

B={d, e} B={b, c}

UB is f. UB is d e and f.

LB is a b and c. LB is a.

LUB is f. LUB does not exist as it

is unique.
GLB does not exist
as it is unique. GLB is a.
Find the Upper bound, Lower bound, Least upper bound and Greatest lower
bound for the following Hasse diagram for given set if exists.

B={b, d, g}

UB is g and h.

LB is a and b.

LUB is g.

GLB is b.
Find the Upper bound, Lower bound, Least upper bound and Greatest lower
bound for the following Hasse diagram for given sets if exists.

1) B={a, c, f} 1)B={5, 10}

2) B={c, d} 2) B={5, 10, 25}
JOIN SEMI LATTICE : In a poset if LUB/JOIN/ SUPREMUM/ ∨ (LUB) exist for
every pair of elements then poset is called join semi lattice.

MEET SEMI LATTICE: In a poset of GLB/MEET/INFIMUM/ ∧ (GLB) exist for

every pair of elements then poset is called meet semi lattice or MEET SEMI
LATTICE.

LUB: In set of upper bound elements, Lub is the smallest element as per relation
R or lies below all upper bound element as per Hasse diagram. It is unique
element out of upper bound elements.

GLB: In set of lower bound elements, GLB is the largest element as per relation R
or lies above all upper bound element as per Hasse diagram. It is unique
element out of lower bound elements.

LATTICE: A poset is called lattice if it is both MEET and JOIN SEMI LATTICE.
Lattice is denoted by (L, ∨, ∧).
Find the Upper bound, Lower bound, Least upper bound and Greatest lower
bound for the sub set A={8, 9} of poset (S, ≤), where S={1, 2, 4, 8, 9, 10, 15, 16}.
Solution : Here we have a poset (S,≤), where S={1, 2, 4, 8, 9, 10, 15, 16}
. A ={8, 9} is a subset of S={1, 2, 4, 8, 9, 10, 15, 16}
Upper bounds are 9, 10, 15 and 16.
Lower bounds are 1, 2, 4 and 8.
Least upper bound is 9.
Greatest lower bound is 8.
Example : The poset of the divisors of 30 ordered by divisibility forms
lattice.
Solution : The Hasse diagram of the divisors of 30 is given below.

The poset consisting of all the divisors of 30 is a lattice as every pair of

elements has both a meet and a join.
Example : Show that the poset of the subsets of {0, 1, 2},ordered by the
relation ⊆ is a lattice.

Solution: The poset of the subsets of {0, 1, 2}, ordered by the subset
relation as every pair of elements has both a meet and a join.
SUBLATTICE : A nonempty subset L’ of a lattice L is called a sub lattice of
L if a ∨ b ∈ L’ and a ∧ b ∈ L’ for all a, b ∈ L’ or the algebra (L’, ∨, ∧) is a
sublattice of (L, ∨, ∧) iff L’ is closed under both operations ∨ and ∧.
Remark:
1) From the definition it follows that a sub lattice itself is a lattice .
2) Every singleton of a lattice L is a sublattice. However, any subset of L,
which is a lattice need not be a sub lattice.
Practice Example : The poset of the divisors of 60 ordered by divisibility
forms lattice.
Note: ‘∨’ stands for LUB, ‘∧ ’ stands for GLB and ‘≤’ stands for relation.

Idempotent
Example: Let T={ ∅, {a}, {c}, {a,c}, {a,b,c}} be a subset of P(S) for
S={a, b, c} and L=(P(s), ∩, ∪) be a lattice. Show that T is a sub lattice
of L.
Solution: Here P(S)={∅, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a,b,c}}.
T ⊆ 𝑃(𝑆)is a closed under ∩ 𝑎𝑛𝑑 ∪, i. e. for any set A and B in T, the
A ∩ 𝐵 and A ∪ 𝐵 is in T. Therefor, T is a sub lattice.

Example: Let T={ ∅, {a}, {b}, {a, c}, {a, b, c}} be a subset of P(S) for
S={a, b, c} and L=(P(s), ∩, ∪) be a lattice. Show that T is not a sub
lattice of L.
Solution: Here P(S)={∅, {a}, {b},{c}, {a,c}, {b,c}, {a,b,c}}.
T ⊆ 𝑃(𝑆) is not closed under ∪, beause A={a} and B={b} in T, For
A={a} and B={b}, the A ∪ 𝐵 is not in a T. Therefor, T is not a sub
lattice.
Example : The Hasse diagram of a poset (S, R) is given below. Check
that it is a lattice or not.

Solution: we take pair {e, c},

Upper bound of e is e itself and Upper bound of c is c it self.
Common upper bound of {e, c} does not exist. Therefore, LUB
of {e,c} does not exist.
Thus, The poset (S, R) is not a Joint semi lattice.
Therefore The poset (S, R) is not a lattice.
Note : Similarly you can take pair {c, a}.
Example : The Hasse diagram of a poset (S, R) is given below. Check
that it is a lattice or not.

Solution: we take pair {d, e},

Lower bounds of d are a, b, c and d and Lower bounds of e are a, b, c
and e. Common lower bounds of {d, e} are a, b and c. GLB of {d, e}
does not exist.
Thus, The poset (S, R) is not a Meet semi lattice.
Therefore The poset (S, R) is not a lattice.
OR
Similarly take {b, c}, this pair does not have LUB.
Thus, The poset (S, R) is not Joint semi lattice and it is not a lattice.
Practice Example : The Hasse diagram of a poset (S, R) is given below.
Check that it is a lattice or not.
 SOME SPECIAL LATTICES
COMPLETE LATTICE: A lattice is called complete lattice if each of
its non empty subsets has a least upper bound and greatest lower
bound.
DISTRIBITIVE LATTICE:
A lattice (L,∨, ∧)is called a distributive lattice if for any a,b, c ∈ L
a∨ 𝑏 ∧ 𝑐 = (a ∨ 𝑏) ∧ a ∨ 𝑐
a∧ 𝑏 ∨ 𝑐 = (a ∧ 𝑏) ∨ a ∧ 𝑐
Remark: Note that both the equalities are equivalent to one
another, hence to check whether the lattice is distributive or not , it
is sufficient to verify one of them.
If L is not distributive, we say that L is non distributive.
Note: The distributive property holds when
1. any two of the elements a, b and c are equal.
2. when any one of the elements is 0 or 1.
BOUNDED LATTICE: A lattice L is said to be bounded if it has a
greatest (maximum) element and a least (minimum) element which
are denoted by 1 (maximum) or I and 0 or O (minimum)
respectively.

COMPLEMENT OF ELEMENT: Let L be bounded lattice with

greatest element 1 and least element 0, and let a in L. An element b
in L is called a complement of a if a ∨ b = 1(maximum) and a ∧ b
=0(minimum).
Note: 0’/0c = 1 and 1’ /1c= 0

COMPLEMENTED LATTICE: A lattice L is said to be

complemented if it is bounded and every element in it has a
complement.
B
Sr no Set Lower bound Greatest Lower bound Upper bound Least upper bound
1 {1} 1 1 1236 1
2 {2} 21 2 26 2
3 {3} 13 3 36 3
4 {6} 6123 1 6 6
5 {1 2} L b of 1→1 Lb of 2-> 1 2 1 Ub of 1-> 1 2 3 6 Ub of 2->2 2
So Lb of {1 2 } is 1 6
Ub of {1 2} is 2 6
6 {1 3} Lb of 1→1 Lb of 3→1 3 1 Ub of 1→1 2 3 6 Ub of 3→ 3 3
So lb of {1 3} is 1 6
So ub of {1 3} is 3 6
7 {1 6} Lb of 1 →1 Lb of → 1 2 3 6 1 Ub of 1 →1 2 3 6 Ub of 6→ 6 6
So lb of {1 6 } is 1 So Ub of {1 6 } is 6
8 {2 3} Lb of 2 →2 1 Lb of 3 →3 1 1 Ub of 2 →2 6 Ub of 3 →3 6 6
So lb of {2 3 } is 1 So Ub of {2 3 } is 6
9 {2 6} Lb of 2→1 2 Lb of 6→1 2 3 6 2 Ub of 2→2 6 Ub of 6→6 6
So lb of {2 6} are 1 2 So Ub of {2 6} is 6
10 {3 6} Lb of 3 →1 3 Lb of 6→1 2 3 6 3 Ub of 3 →3 6 Ub of 6→6 6
So lb of {3 6 } are 1 3 So Ub of {3 6 } is 6
11 {1 2 3} Lb of 1→1 Lb of 2→ 2 1 1 Ub of 1→1 2 3 6 Ub of 2→ 2 6
Lb of 3→ 1 3 So lb of {1 2 3 } is 1 6
Ub of 3→ 3 6So Ub of {1 2 3
} is 6
12 {1 2 6} Lb of 1→1 Lb of 2→2 1 Lb of 6→ 1 2 3 1 Ub of 1→1 2 3 6 Ub of 2→2 6
6 6
So lb of {1 2 6 } is 1 Ub of 6→ 6
So Ub of {1 2 6 } is 6
13 {1 3 6} Lb of 1→1 Lb of 3→ 1 3 Lb of 6→ 1 2 3 1 Ub of 1→1236 Ub of 3→ 3 6 6
6 Ub of 6→6
So lb of {1 3 6 } is 1 So Ub of {1 3 6 } is 6
14 {2 3 6} Lb of 2→1 2 Lb of 3→ 1 3 Lb of 6→1 2 1 Ub of 2→2 6 Ub of 3→ 3 6 6
36 Ub of 6→6
So lb of {2 3 6 } is 1 So Ub of {2 3 6 } is 6
15 {1 2 3 6} Lb of 1→1 Lb of 2→ 1 2 Lb of 3→1 3 1 Ub of 1→1 2 3 6 6
Lb of 6→1 2 3 6 So lb of {1 2 3 6 } is 1 Ub of 2→ 2 6 Ub of 3→3 6
Ub of 6→6
So Ub of {1 2 3 6 } is 6
Example: Prove that P(S) is a bounded and distributive lattice under ∩
𝒂𝒏𝒅 ∪, where S= {a, b, c}.
Solution: We know that (P(S), ∩, ∪) is a lattice. Here P(S)={ ∅,{a}, {b},{c},
{a, b},{a, c},{b, c}, {a, b, c}}. Maximum element is {a, ,b, c} and minimum
element is ∅. Therefore P(S) is a bounded under ∩ 𝑎𝑛𝑑 ∪.
Also we know that P(S ) satisfier the distributive relation

a ∪ 𝑏 ∩ 𝑐 = (a ∪ 𝑏) ∩ a ∪ 𝑐 , therefore it is a distributive lattice

Example: Prove that D30 with relation ‘/’ is a complemented
lattice, where a/b means a is divisible by b.
Solution: D30 ( divisors of 30) ={ 1,2,3,5,6,10,15,30}

It is a complemented lattice.
Note : Complement of an element is not unique.
Example: The Hasse diagram of a lattice (S, R) is given below.
Check that it is a complemented lattice or not.
Maximum element is e and minimum element is a. Therefore
it is a bounded lattice. It is a complemented lattice because
each element has /have its complement as shown in table.
Element Complement
a e
b c and d(not
unique)
c b and d(not
unique)
d b and c(not
unique)
Complement of an element need
It is a complemented lattice. not to be unique.