Module 4

Lattices
Lattices

➢ Partially Ordered Relations

➢ Lattices as Posets

➢ Hasse Digram

➢ Properties of Lattices.
Relation: If A and B are two sets, then relation 𝑅 from 𝐴 to 𝐵is the subset of the
cartesian product 𝐴 × 𝐵.

If 𝑎 is related to 𝑏 under the relation R, then we write 𝑎 𝑅 𝑏.

Thus

The set of first entries of the ordered pairs in a relation is called the domain of the
relation. The set of second entries of the ordered pairs in a relation is called the range of
the relation.
Domain of 𝑅={2,3,4,6},
Range of 𝑅={2,4,6,8}

Note:
PROPERTIES OF RELATIONS
Reflexive Relation
Let 𝑅 be a relation defined in a set 𝐴; then 𝑅 is reflexive if 𝑎 𝑅 𝑎 holds for all 𝑎 ∈ 𝐴, i.e.,
if 𝑎, 𝑎 ∈ 𝑅 for all 𝑎 ∈ 𝐴.
Example 1: Let 𝐴 = {𝑎, 𝑏, 𝑐} and 𝑅 = { 𝑎, 𝑎 , 𝑏, 𝑏 , 𝑐, 𝑐 } then 𝑅 is a reflexive relation
in 𝐴.
Example 2: 'Equality' is a reflexive relation, since an element equals itself.

Symmetric Relation
A relation 𝑅 defined in set 𝐴 is said to be 'symmetric' if 𝑏 𝑅 𝑎 holds whenever 𝑎 𝑅 𝑏
holds for 𝑏 ∈ 𝐴, i.e., 𝑅 is symmetric in 𝐴 if
𝑎, 𝑏 ∈ 𝑅 ⇒ 𝑏, 𝑎 ∈ 𝑅
Example: Let 𝑅 be relation 'is perpendicular to' in the set of all straight lines, then 𝑅 is a
symmetric relation.
Transitive Relation
A relation 𝑅 in set 𝐴 is said to be transitive if

𝑎, 𝑏 ∈ 𝑅, 𝑏, 𝑐 ∈ 𝑅 ⇒ 𝑎, 𝑐 ∈ 𝑅
i.e., if 𝑎 𝑅 𝑏 and 𝑏 𝑅 𝑐 ⇒ 𝑎 𝑅 𝑐, where 𝑎, 𝑏, 𝑐 ∈ 𝐴.

E x a m p l e 1 : L e t 𝐴 denote the set of straight lines in a plane and 𝑅 be a relation in 𝐴

defined by 'is parallel to' then 𝑅 is a transitive relation in 𝐴.
E x a m p l e 2 : Let 𝐴 = {1,2,3} and 𝑅 = {(1,1), (2,2), (2,3), (3,2), (3,3)} then 𝑅 is
transitive.
Anti-symmetric Relation
Let 𝑅 be a relation in a set 𝐴, then 𝑅 is called anti-symmetric.

𝑎, 𝑏 ∈ 𝑅, 𝑏, 𝑎 ∈ 𝑅 ⇒ 𝑎 = 𝑏 ∀𝑎, 𝑏 ∈ 𝑅
𝑖. 𝑒. 𝑎 𝑅 𝑏 and 𝑏 𝑅 𝑎 ⇒ 𝑎 = 𝑏

E x a m p l e : Let 𝑁 denote the set of Natural Numbers 𝑅 be a relation in 𝑁, defined by

'𝑎 is a divisor' of 𝑏, i.e., 𝑎 𝑅 𝑏 if 𝑎 divides 𝑏 then 𝑅 is anti-symmetric since 𝑎 divides 𝑏
and 𝑏 divides 𝑎 ⇒ 𝑎 = 𝑏.

Equivalence Relation
A relation 𝑅 in a set 𝐴 is said to be an equivalence relation in 𝐴, if 𝑅 is reflexive,
symmetric and transitive.
Example:
(i) Let 𝐴 be the set of all triangle in a plane and let 𝑅 be a relation in 𝐴 defined by 'is
congruent to', then 𝑅 is reflexive, symmetric and transitive.
∴ 𝑅 is an Equivalence relation in 𝐴.
(ii) Let 𝐴 = {𝑎, 𝑏, 𝑐}, and 𝑅 =
{ 𝑎, 𝑎 , 𝑎, 𝑏 , 𝑎, 𝑐 , (𝑏, 𝑎), (𝑏, 𝑏), (𝑏, 𝑐), (𝑐, 𝑎), (𝑐, 𝑏), (𝑐, 𝑐)} then 𝑅 is an equivalence
relation in 𝐴.
Example: Consider the following relations on {1,2,3,4} :
𝑅1 = { 1,1 , 1,2 , 2,1 , 2,2 , 3,4 , 4,1 , 4,4 },
𝑅2 = { 1,1 , 1,2 , 2,1 },
𝑅3 = { 1,1 , 1,2 , 1,4 , 2,1 , 2,2 , 3,3 , 4,1 , 4,4 },
𝑅4 = { 2,1 , 3,1 , 3,2 , 4,1 , 4,2 , 4,3 },
𝑅5 = { 1,1 , 1,2 , 1,3 , 1,4 , 2,2 , 2,3 , 2,4 , 3,3 , 3,4 , 4,4 },
𝑅6 = { 3,4 } .
Which of these relations are reflexive?

Solution: The relations 𝑅3 and 𝑅5 are reflexive because they both contain all pairs of
the form 𝑎, 𝑎 , namely, 1,1 , 2,2 , 3,3 , and 4,4 . The other relations are not
reflexive because they do not contain all of these ordered pairs. In particular,
𝑅1 , 𝑅2 , 𝑅4 , and 𝑅6 are not reflexive because 3,3 is not in any of these relations.
Let 𝐴 = {0,1,2} and 𝐵 = {𝑎, 𝑏}. Then { 0, 𝑎 , 0, 𝑏 , 1, 𝑎 , 2, 𝑏 } is a relation from 𝐴
to 𝐵. This means, for instance, that 0 𝑅 𝑎, but that1𝑅𝑏. Relations can be represented
graphically,
Example:
Let A={0,1,2,3} and R={ (0,0),(0,1),(0,2),(1,1), (1,2), (2,2),(0,3),(3,3)}
R is a partial order relation
Definition: A partial order is a total or linear order iff for all x and y in the set either xRy
or yRx is true. In a totally ordered set all elements are comparable.
Hasse Diagrams
The simplified form of the digraph of a partial ordering on a finite set that contains
sufficient information about the partial ordering is called a Hasse diagram, named after
the twentieth-century mathematician Helmut Haasse.
The simplification of the digraph as a Hasse diagram is achieved in three ways:
➢ Since the partial ordering is a reflexive relation, its digraph has loops at all vertices. We
need not show these loops since they must be present.
➢ Since the partial ordering is transitive, we need not show those edges that must be
present due to transitivity. For example, if (1,2) and (2,3) are edges in the digraph of
a partial ordering, (1,3) will also be an edge due to transitivity. This edge (1,3) need
not be shown in the corresponding Hasse diagram.
➢ If we assume that all edges are directed upward, we need not show the directions of
the edges.
Thus the Hasse diagram representing a partial ordering can be obtained from its digraph,
by removing all the loops, by removing all edges that are present due to transitivity and
by drawing each edge without arrow so that its initial vertex is below its terminal vertex.
Example: let us construct the Hasse diagram for the partial ordering {(𝑎, 𝑏)| 𝑎 ≤ 𝑏}
on the set {1, 2, 3, 4} starting from its digraph.
Solution:
The element x is called the least upper bound (LUB) or supremum of the subset A of
a poset {𝑃, ≤}, if x is an upper bound that is less than every other upper bound of A.

Similarly the element y is called the greatest lower bound (GLB) or infimum of the
subset A of a poset {𝑃, ≤}, if y is a lower bound that is greater than every other
lower bound of A.

Example: let us consider the poset with the Hasse diagram given in Fig

Solution: The upper bounds of the subset {a, b, c} are e and f.

[Note: d is not an upper bound, since c is not related to d]
and LUB of {a, b, c} is e.
The lower bounds of the subset {d, e} are a and b and GLB of {d, e} is b.
c is not a lower bound, since c is not related to d.
LATTICES
Definition:
A lattice is a partially ordered set {𝐿,≤} in which every pair of elements 𝑎,𝑏∈𝐿 has a
greatest lower bound and least upper bound.
The greatest lower bound of a subset {𝑎,𝑏}∈𝐿will be denoted by 𝑎∗𝑏 and the least
upper bound by 𝑎 ⊕ 𝑏.

Join or sum: The LUB of a subset {𝑎,𝑏} ⊆ 𝐿 is denoted by 𝑎 ⊕ 𝑏(or𝑎∨𝑏or 𝑎+𝑏) and is
called the join or sum of a and b.

Meet or product: The GLB of a subset {𝑎,𝑏} ⊆ 𝐿 is denoted by 𝑎∗𝑏( or 𝑎∙𝑏 or 𝑎 ∧ 𝑏) is

called the meet or product of 𝑎 and 𝑏.

A totally ordered set is trivially a lattice, but not all partially ordered sets are lattices
Example: ({1,2,4,8},|),where | means ‘divisor of ’. The hasse diagram

LUB = 8, GLB = 1

So, it is a lattice.

Example: ({1,2,3,4,5},|) It is not a lattice, since LUB of the pair (2, 3) and
(3, 5) do not exist.
Example: In the case of power set 𝑃(𝑆) of any set 𝑆, (𝑃(𝑆),⊆) is a lattice

Here 𝐿𝑈𝐵=𝐴∪𝐵 and 𝐺𝐿𝐵=𝐴∩𝐵, where 𝐴 and 𝐵 are any subsets of 𝑃(𝑆).
Example: Is the poset (𝑍 + , |) a lattice?

Solution: Let 𝑎,𝑏∈ 𝑍 + , now, LUB of these two integers is the LCM (Least Common
multiple) and GLB is the GCD (Greatest Common Divisor).

Example:

It is not a lattice since the pair (b, c) have no least upper bound.
Example:

It is a lattice since every pair of elements has LUB and GLB.

Properties of Lattice:
We shall first list some of the properties of the two binary operations of meet and
join denoted by ∗ and ⊕ on a lattice (𝐿,≤).
For any 𝑎,𝑏,𝑐∈𝐿,we have
Lattices and Algebraic systems:

Definition:
A lattice is an algebraic system < 𝐿,∗,⊕> with two binary operation * and ⊕ on 𝐿
which are both (1) commutative and (2) associative and (3) satisfy the absorption
laws. In other words the operation * and ⊕ satisfy the identities (L-2) to (L-4) and (L-
2)’ to (L-4)’.

Sub lattices

Definition:
Let < 𝐿,∗ ,⊕> be lattices and let S is a subset of L. The algebra < 𝑆,∗ ,⊕> is a
sub-lattices of < 𝐿,∗ ,⊕> iff S is closed under both operations * and ⊕.
Example 1:

Let <L, ≤ > be a lattices in which 𝐿 = {𝑎1 , 𝑎2 , … , 𝑎8 } and 𝑆1 , 𝑆2 and 𝑆3 be the subsets of
𝐿 given by 𝑆1 ={𝑎1 , 𝑎2 , 𝑎4 , 𝑎6 }, 𝑆2 ={𝑎3 , 𝑎5 , 𝑎7 , 𝑎8 } and 𝑆3 ={𝑎1 , 𝑎2 , 𝑎4 , 𝑎8 }.

Observe that < 𝑆1 , ≤ > and < 𝑆2 , ≤ > are sub lattices of
< 𝐿, ≤ >
But < 𝑆3 , ≤ > is not a sub lattices , because 𝑎2 , 𝑎4 ∈ 𝑆3
but 𝑎2 ∗ 𝑎4 = 𝑎6 ∉ 𝑆3 note that < 𝑆3 , ≤ > is a lattices.

Example 2: The lattices of divisor of any positive integer

𝑛 denoted by < 𝑆𝑛 , | > is a sub lattices of < 𝑍 + , | >.
Some special lattices:
Definition:
A lattices is called complete if each of its non-empty subsets has a least upper
bound and a greatest lower bound.

Definition:
A lattice (L, ∗, ⊕) is said to be bounded if it has a greatest element and a least
element. The greatest and least elements are denoted by 1 and 0 respectively.

Definition:
In a bounded lattice < 𝐿,∗,⊕, 0, 1 > an element 𝑏 ∈ 𝐿 is called a complement
of an element a ∈ 𝐿 if a*b=0 & a ⊕ b=1.
Definition:
A lattice < 𝐿,∗,⊕, 0, 1 > is said to be complemented lattices if every element of L has
at least one complement.
In fig some lattices are shown and the complement of some of the elements are noted
below the diagram. 1
1 1

𝑥2
𝑥1 𝑥2 𝑥1 𝑥2 𝑥3 𝑥1
𝑥3

0 0
0
Complement of Complements of 𝑥1 are
𝑥1 is 𝑥2 𝑥2 , 𝑥3 Complements of 𝑥1 are 𝑥2 , 𝑥3
Complements of 𝑥2 are
𝑥1 , 𝑥3
let 𝐿 = {0,1} and the lattices < 𝐿, ≤ > be as shown in fig.

The lattices < 𝐿2 , ≤2 >, < 𝐿3 , ≤3 >, are shown in fig .

In general of < 𝐿𝑛 , ≤𝑛 >, is an n cube.
Example:
Let < 𝐿𝑛 , ≤𝑛 > be the lattice of n- tuples of 0 and 1 . This is a complemented lattice
in which every element has a unique complement.
The complement of an element of 𝐿𝑛 can obtained by interchanging 1 by 0 and 0 by
1 in the n- tuples representing the element. As a special case let n=3 . The bounds of
< 𝐿𝑛 , ≤𝑛 >, < 0,0,0> and < 1,1,1> the complement of <1,0,1> is < 0,1,0>
Definition:
A lattices < 𝐿,∗,⊕> is called a distributive lattice if for any a, b, c ∈ L

Example :
show that the lattices given by the diagram are not distributive.
Solution:

hence the lattices is not distributive . In the other case,

which shows that the lattices is not distributive.