DISCRETE MATHEMATICS (3140708)

CHAPTER 2 – Unit 3
PARTIAL ORDERING

CONTENT

❖ Definition
❖ Examples
❖ Simple or Linear ordering
❖ Totally ordered set (Chain)
❖ Frequently used Partially ordered relations
❖ Representation of Partially ordered sets
❖ Hasse Diagrams
❖ Least (minimum) and greatest (maximum) members
❖ Minimal and maximal members
❖ Least upper bound (Supremum)
❖ Greatest lower bound (Infimum)
❖ Well-ordered Partially ordered sets (POSETS)
❖ Lattice as Posets
❖ Complete, Distributive modular and complemented lattices
❖ Boolean and pseudo-Boolean lattices (Definitions and simple examples only)

Definition of Partial Order Relation

The relation 𝑅 defined on set 𝐴 is called partial order relation if
1) 𝑅 is reflexive
2) 𝑅 is anti-symmetric
3) 𝑅 is transitive
Notation
The partial order relation 𝑅 is often denoted by the symbol ⪯. This symbol is different from
the usual less than or equal to symbol ≤. In other words, the symbols ⪯ and ≤ do not have the
same meaning.
Partially ordered set / POSET
Let ⪯ be the partial order relation defined on set 𝐴. Then, ⟨ 𝐴 , ⪯ ⟩ is called POSET. In other
words, if the relation is partial order relation on any set, then a set together with a partial order
relation is called a POSET.
For example,
1) Let 𝑅 be the relation defined on set 𝐴 = {1, 2, 3} where
𝑅 = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}.
Note that (1,1) ∈ 𝑅 where 1 ∈ 𝐴.
Also, (2,2) ∈ 𝑅 where 2 ∈ 𝐴.
Also, (3,3) ∈ 𝑅 where 3 ∈ 𝐴.
Since (1,1) ∈ 𝑅 , (2,2) ∈ 𝑅 and (3,3) ∈ 𝑅, the relation 𝑅 is reflexive.

Let (1,2) ∈ 𝑅. But, (2,1) ∉ 𝑅.

Let (1,3) ∈ 𝑅. But, (3,1) ∉ 𝑅.
Let (2,3) ∈ 𝑅. But, (3,2) ∉ 𝑅.
Since (𝑦, 𝑥) ∉ 𝑅 for every (𝑥, 𝑦) ∈ 𝑅, the relation 𝑅 is anti-symmetric.

Let (𝒙, 𝑦) = (𝟏, 2) ∈ 𝑅 and (𝑦, 𝒛) = (2, 𝟑) ∈ 𝑅. Then, (𝑥, 𝑧) = (𝟏, 𝟑) is also in 𝑅.
Since new ordered pair belongs to 𝑅, the relation 𝑅 is transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order
relation on the given set 𝐴. So, ⟨ 𝐴 , 𝑅 ⟩ is partially ordered set or POSET.

Question (DEC 2022 – 03 Marks)

Define Partial Order Relation. Illustrate with an example.
Answer (On page 1 and 2)
Question (SEP 2021 – 01 Mark)
Define Partially ordered set (Poset).
Answer (On page 1 and 2)
Question
Let ≥ be the relation defined on the set 𝑆 = {−1, 0, 1, 2}. Show that ≥ is a partial order relation
and ⟨ 𝑆 , ≥ ⟩ is POSET.
Answer
Method 1
Here ≥ is “greater than or equal to” relation defined on finite set 𝑆 = {−1, 0, 1, 2}. That is,
𝑥 is related to 𝑦 if 𝑥 is greater than or equal to 𝑦.
Since −1 = −1, we have (−1, −1) ∈ 𝑅.
Since 0 = 0, we have (0, 0) ∈ 𝑅.
Since 0 > −1, we have (0, −1) ∈ 𝑅.
Since 1 = 1, we have (1, 1) ∈ 𝑅.
Since 1 > −1, we have (1, −1) ∈ 𝑅.
Since 1 > 0, we have (1, 0) ∈ 𝑅.
Since 2 = 2, we have (2, 2) ∈ 𝑅.
Since 2 > −1 , 2 > 0 and 2 > 1, we have (2, −1) ∈ 𝑅, (2, 0) ∈ 𝑅 and (2, 1) ∈ 𝑅.
Hence, 𝑅 = {(−1, −1), (0,0), (0, −1), (1,1), (1, −1), (1,0), (2,2), (2, −1), (2,0), (2,1)}.
1) Note that (−1, −1) ∈ 𝑅 where −1 ∈ 𝑆.
Also, (0,0) ∈ 𝑅 where 0 ∈ 𝑆.
Also, (1,1) ∈ 𝑅 where 1 ∈ 𝑆.
Also, (2,2) ∈ 𝑅 where 2 ∈ 𝑆.
Hence, the relation 𝑅 or ≥ is reflexive.
2) Let (0, −1) ∈ 𝑅. But, (−1,0) ∉ 𝑅.
Let (1, −1) ∈ 𝑅. But, (−1,1) ∉ 𝑅.
Let (1,0) ∈ 𝑅. But, (0,1) ∉ 𝑅.
Let (2, −1) ∈ 𝑅. But, (−1,2) ∉ 𝑅.
Let (2,0) ∈ 𝑅. But, (0,2) ∉ 𝑅.
Let (2,1) ∈ 𝑅. But, (1,2) ∉ 𝑅.
Since (𝑦, 𝑥) ∉ 𝑅 for every (𝑥, 𝑦) ∈ 𝑅, the relation 𝑅 or ≥ is anti-symmetric.
3) Let (𝒙, 𝑦) = (𝟏, 0) ∈ 𝑅 and (𝑦, 𝒛) = (0, −𝟏) ∈ 𝑅. Then, (𝑥, 𝑧) = (𝟏, −𝟏) is also in 𝑅.
Let (𝒙, 𝑦) = (𝟐, 1) ∈ 𝑅 and (1, −𝟏) = (2, −𝟏) ∈ 𝑅. Then, (𝑥, 𝑧) = (𝟐, −𝟏) is also in
𝑅. Similarly, all new ordered pairs belong to 𝑅. So, the relation 𝑅 or ≥ is transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order
relation on the given set 𝑆. So, ⟨ 𝑆 , ≥ ⟩ is partially ordered set or POSET.

Method 2
Here ≥ is “greater than or equal to” relation defined on finite set 𝑆 = {−1, 0, 1, 2}. That is, 𝑥
is related to 𝑦 if 𝑥 is greater than or equal to 𝑦.

1) Since the relation is “greater than or equal to”, every element of set 𝑆 is related to itself.
Hence, the relation ≥ is reflexive.
 2) If 𝑥 ≥ 𝑦 then 𝑦 ≱ 𝑥. That is, if 𝑥 greater than or equal to 𝑦 is true then 𝑦 greater than
or equal to 𝑥 is NOT true. Hence, the relation ≥ is anti-symmetric.
In other words, if 𝑥 ≥ 𝑦 and 𝑦 ≥ 𝑥 then 𝑥 = 𝑦. Hence, the relation ≥ is
anti-symmetric.
3) If 𝒙 ≥ 𝑦 and 𝑦 ≥ 𝒛 then we have 𝒙 ≥ 𝒛. That is, if 𝑥 is greater than or equal to 𝑦 and
𝑦 is greater than or equal to 𝑧 then 𝑥 is greater than or equal to 𝑧. Hence, the relation
≥ is transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order
relation on the given set 𝑆. So, ⟨ 𝑆 , ≥ ⟩ is partially ordered set or POSET.

Question
Let ≥ be the relation defined on the set of integers 𝑍. Show that ≥ is a partial order relation on
𝑍 and ⟨ 𝑍 , ≥ ⟩ is partially ordered set.
Answer

Here ≥ is “greater than or equal to” relation defined on infinite set 𝑍 = {… , −2, −1, 0, 1, 2, … }.
That is, 𝑥 is related to 𝑦 if 𝑥 is greater than or equal to 𝑦.

1) Since the relation is “greater than or equal to”, every element of set 𝑍 is related to itself.
Hence, the relation ≥ is reflexive.
2) If 𝑥 ≥ 𝑦 then 𝑦 ≱ 𝑥. That is, if 𝑥 greater than or equal to 𝑦 is true then 𝑦 greater than
or equal to 𝑥 is NOT true. Hence, the relation ≥ is anti-symmetric.
In other words, if 𝑥 ≥ 𝑦 and 𝑦 ≥ 𝑥 then 𝑥 = 𝑦. Hence, the relation ≥ is
anti-symmetric.
3) If 𝒙 ≥ 𝑦 and 𝑦 ≥ 𝒛 then we have 𝒙 ≥ 𝒛. That is, if 𝑥 is greater than or equal to 𝑦 and
𝑦 is greater than or equal to 𝑧 then 𝑥 is greater than or equal to 𝑧. Hence, the relation
≥ is transitive.
Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order
relation on the given set 𝑍. So, ⟨ 𝑍 , ≥ ⟩ is partially ordered set or POSET.
Question
Let | be the divisibility relation defined on the set 𝑆 = {1, 2, 3, 4, 5}. Determine whether | is a
partial order relation on 𝑆. OR

Let | be the divisibility relation defined on the set 𝑆 = {1, 2, 3, 4, 5}. Determine whether
⟨ 𝑆 , | ⟩ is POSET.

Answer

Here | is “divides” relation defined on finite set 𝑆 = {1, 2, 3, 4, 5}. That is, 𝑥 is related to 𝑦 if
𝑥 divides 𝑦. In other words, 𝑥 is related to 𝑦 if 𝑦 is divisible by 𝑥. In other words, 𝑥 is related
𝑦
to 𝑦 if 𝑥 is an integer where 𝑥 is first element and 𝑦 is second element of ordered pair (𝑥, 𝑦).
Note that every number divides itself. That is, 1|1 , 2|2 , 3|3 , 4|4 , 5|5. Therefore, (1,1),
(2,2), (3,3), (4,4), (5,5) are elements of the given relation.

Note that 1 divides every number. That is, 1|2 , 1|3 , 1|4 , 1|5. Therefore, (1,2), (1,3),
(1,4), (1,5) are elements of the given relation.

Note that only 2 divides 4. That is, 2|4. Therefore, (2,4) is element of the given relation.

Hence, | = {(1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,4), (3,3), (4,4), (5,5)}. Note that here
we used the symbol | for the relation (earlier we used the symbol 𝑅 for the relation).

1) Since the ordered pairs (1,1), (2,2), (3,3), (4,4), (5,5) are present, the relation | is
reflexive.
2) (1,2) is present but (2,1) is not present.
(1,3) is present but (3,1) is not present.
(1,4) is present but (4,1) is not present.
(1,5) is present but (5,1) is not present.
(2,4) is present but (4,2) is not present.
Hence, the relation | is anti-symmetric.
3) Let (𝒙, 𝑦) = (𝟏, 2) and (𝑦, 𝒛) = (2, 𝟒). Then, (𝑥, 𝑧) = (𝟏, 𝟒) is also present in the
relation. That is, all new ordered pairs are present in the relation. So, the relation | is
transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order
relation on the given set 𝑆. So, ⟨ 𝑆 , | ⟩ is partially ordered set or POSET.

Question
Let | be the divisibility relation defined on the set 𝑍 + . Determine whether | is a partial order
relation on 𝑍 + . OR

Let | be the divisibility relation defined on the set 𝑍 + . Determine whether ⟨ 𝑍 + , | ⟩ is POSET.
Answer

Here | is “divides” relation defined on infinite set 𝑍 + = {1, 2, 3, 4, 5, … }. Note that 𝑍 + is the
set of positive integers.

1) Note that every number divides itself. That is, 𝑥|𝑥. That is, (𝑥, 𝑥) is present in the
relation for every 𝑥 ∈ 𝑍 + . Hence, the relation | is reflexive.
2) If 𝑥|𝑦 is true for positive integers 𝑥 and 𝑦 then 𝑦|𝑥 is not true. Hence, the relation | is
anti-symmetric.
In other words, if 𝑥|𝑦 and 𝑦|𝑥 then 𝑥 = 𝑦. Hence, the relation | is anti-symmetric.
 3) If 𝑥|𝑦 and 𝑦|𝑧 then 𝑥|𝑧. That is, if 𝑥 divides 𝑦 and 𝑦 divides 𝑧, then 𝑥 divides 𝑧 also.
Hence, the relation | is transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order

relation on the given set 𝑍 + . So, ⟨ 𝑍 + , | ⟩ is partially ordered set or POSET.

Question

Let ⊆ be the inclusion (subset) relation defined on the power set of 𝑆 where 𝑆 = {𝑎, 𝑏, 𝑐}.
Determine whether ⊆ is a partial order relation on 𝑃(𝑆). OR

Let ⊆ be the inclusion (subset) relation defined on the power set of 𝑆 where 𝑆 = {𝑎, 𝑏, 𝑐}.
Determine whether ⟨ 𝑃(𝑆) , ⊆ ⟩ is POSET.
Answer

The power set of 𝑆 is denoted by 𝑃(𝑆) and it is given by

𝑃(𝑆) = {∅, {𝑎}, {𝑏}, {𝑐}, {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, {𝑎, 𝑏, 𝑐}}.

Here ⊆ be the inclusion (subset) relation defined on 𝑃(𝑆). That is, a set 𝐴 ∈ 𝑃(𝑆) is related
to a set 𝐵 ∈ 𝑃(𝑆) if 𝐴 is a subset of 𝐵.

1) Since every set is a subset of itself, the relation ⊆ is reflexive.

2) If 𝐴 ⊆ 𝐵 is true then 𝐵 ⊆ 𝐴 is not true. Hence, the relation ⊆ is anti-symmetric.
In other words, if 𝐴 is a subset of 𝐵 and 𝐵 is a subset of 𝐴 then 𝐴 = 𝐵. Hence, the
relation ⊆ is anti-symmetric.
3) If 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐶 then 𝐴 ⊆ 𝐶 also. For example, if {𝑎} is a subset of {𝑎, 𝑏} and
{𝑎, 𝑏} is a subset of {𝑎, 𝑏, 𝑐}. Then, {𝑎} is a subset of {𝑎, 𝑏, 𝑐} also. Hence, the relation
⊆ is transitive.

Since the given relation is reflexive, anti-symmetric and transitive, it is a partial order

relation on the power set 𝑃(𝑆). So, ⟨ 𝑃(𝑆) , ⊆ ⟩ is partially ordered set or POSET.

Note

In above example, let 𝑆 be any given set. Then, ⊆ is a partial order relation on the power set
𝑃(𝑆).

Comparability

The elements 𝑎 and 𝑏 of a POSET ⟨ 𝐴 , ⪯ ⟩ are called comparable (related) if either 𝑎 ⪯ 𝑏

or 𝑏 ⪯ 𝑎. That is, two elements 𝑎 and 𝑏 are comparable if either 𝑎 is related to 𝑏 or 𝑏 is
related to 𝑎.
Chain

Let ⟨ 𝐴 , ⪯ ⟩ be a POSET. If every two elements of 𝐴 are comparable (related) then 𝐴 is called
a totally ordered set or linearly ordered set or chain.

Antichain

If no two distinct elements of a POSET are comparable (related) then it is called an antichain.
Hasse Diagrams

A partial order relation ⪯ defined on a set 𝑆 can be represented by a diagram and that is known
as Hasse diagram of POSET ⟨ 𝑆 , ⪯ ⟩.
Use the following procedure/points to construct a Hasse diagram:

1) Every element of 𝑆 can be represented by a point (or node or vertex).

There is no loop (self-loop) at any vertex.
In other words, start with a directed graph (digraph) and remove the loops at all the
vertices.
2) If 𝑥 is related to 𝑦 then it can be represented by an edge (without arrow/direction)
between 𝑥 and 𝑦 where element (vertex) 𝑦 appear above the element (vertex) 𝑥.
In other words, remove all the arrows from a directed graph (digraph).
3) If 𝒙 is related to 𝑦 and 𝑦 is related to 𝒛 then there is no direct edge between 𝒙 and 𝒛.
In other words, remove the direct edge between 𝑥 and 𝑧 from a directed graph if 𝑥 is
related to 𝑧 by transitivity. That is, remove all those edges whose existence is implied
by the transitive property.
Important note

1) If 𝑥 is not related to 𝑦, then keep element (vertex) 𝑦 parallel (in a horizontal direction)
to element (vertex) 𝑥.
2) If 𝑥 is related to 𝑦, then keep element (vertex) 𝑦 above (in a vertical or upward
direction) to the element (vertex) 𝑥.

Question
Draw the Hasse diagram representing the partial ordering {(𝑎, 𝑏) | 𝑎 divides 𝑏} on the set
{1, 2, 5, 10}.
Answer
Explanation

1) 1 divides every other element. That is, 1 is related to every element. So, keep vertex 1
at the extreme bottom.
2) 1 divides 2. That is, 1|2. That is, 1 is related to 2. So, keep vertex 2 in the upward
direction of vertex 1.
3) Join 1 and 2 by an edge.
 4) 2 does not divide 5. That is, 2 ∤ 5. That is, 2 is not related to 5. So, keep vertex 5 in the
horizontal direction of vertex 2.
5) 2 divides 10. That is, 2|10. That is, 2 is related to 10. So, keep vertex 10 in the upward
direction of vertex 2.
6) Join 2 and 10 by an edge.
7) 5 divides 10. That is, 5|10. That is, 5 is related to 10. So, join 5 and 10 by an edge.

Hasse diagram

Question (FEB 2021 – 04 Marks)

Draw the Hasse diagram representing the partial ordering {(𝑎, 𝑏) | 𝑎 divides 𝑏} on
{1, 2, 3, 4, 6, 8, 12}.

Answer
Explanation

1) 1 divides every element of the given set. That is, 1 is related to every element. So, keep
vertex 1 at the extreme bottom.
2) 1 divides 2. That is, 1|2. That is, 1 is related to 2. So, keep vertex 2 in the upward
direction of vertex 1.
3) Join 1 and 2 by an edge.
4) 2 does not divide 3. That is, 2 ∤ 3. That is, 2 is not related to 3. So, keep vertex 3 in the
horizontal direction of vertex 2.
5) 1 divides 3. That is, 1|3. That is, 1 is related to 3. So, join 1 and 3 by an edge.
6) 2 divides 4. That is, 2|4. That is, 2 is related to 4. So, keep vertex 4 in the upward
direction of vertex 2.
7) Join 2 and 4 by an edge.
8) 4 does not divide 6. That is, 4 ∤ 6. That is, 4 is not related to 6. So, keep vertex 6 in the
horizontal direction of vertex 4.
9) 2 divides 6. That is, 2|6. That is, 2 is related to 6. So, join 2 and 6 by an edge.
10) 3 divides 6. That is, 3|6. That is, 3 is related to 6. So, join 3 and 6 by an edge.
11) 4 divides 8. That is, 4|8. That is, 4 is related to 8. So, keep vertex 8 in the upward
direction of vertex 4.
 12) Join 4 and 8 by an edge.
13) 8 does not divide 12. That is, 8 ∤ 12. That is, 8 is not related to 12. So, keep vertex 12
in the horizontal direction of vertex 8.
14) 4 divides 12. That is, 4|12. That is, 4 is related to 12. So, join 4 and 12 by an edge.
15) 6 divides 12. That is, 6|12. That is, 6 is related to 12. So, join 6 and 12 by an edge.

Hasse diagram

Question (DEC 2022 – 04 Marks)

Draw Hasse Diagram for the poset (𝑆30 , 𝐷) where 𝑆30 is the set of divisors of 30 and 𝐷 is
the relation divides.
Answer
The divisors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. Therefore, 𝑆30 = {1, 2, 3, 5, 6, 10, 15, 30}.
Explanation

1) 1 divides every other element. That is, 1 is related to every element. So, keep vertex 1
at the extreme bottom.
2) 1|2 , 1|3 and 1|5. Join 1 and 2 by an edge. Join 1 and 3 by an edge. Join 1 and 5 by an
edge.
3) 2|6 and 2|10. Join 2 and 6 by an edge. Join 2 and 10 by an edge.
4) 3|6 and 3|15. Join 3 and 6 by an edge. Join 3 and 15 by an edge.
5) 5|10 and 5|15. Join 5 and 10 by an edge. Join 5 and 15 by an edge.
6) 6|30 , 10|30 and 15|30. So, join 6 and 30, 10 and 30, 15 and 30, by an edge.

Hasse diagram
Question (DEC 2021 – 07 Marks)
Let 𝐴 be the set of factors of particular positive integer 𝑚 and ≤ be the relation divides, that is
≤= {⟨𝑥, 𝑦⟩ | 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐴 ∧ (𝑥 divides 𝑦)}
Draw the Hasse diagrams for 𝑎) 𝑚 = 45 𝑏) 𝑚 = 210.

Answer

a) The factors of 45 are 1, 3, 5, 9, 15, 45. Therefore, 𝐴 = {1, 3, 5, 9, 15, 45}.

Explanation

1) 1 divides every other element. That is, 1 is related to every element. So, keep vertex 1
at the extreme bottom.
2) 1|3 and 1|5. Join 1 and 3 by an edge. Join 1 and 5 by an edge.
3) 3|9 and 3|15. Join 3 and 9 by an edge. Join 3 and 15 by an edge.
4) 5|15. Join 5 and 15 by an edge.
5) 9|45 and 15|45. Join 9 and 45 by an edge. Join 15 and 45 by an edge.
Hasse diagram

b) The factors of 210 are 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210.
Therefore, 𝐴 = {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}.

Hasse diagram
Question (SEP 2021 – 03 Marks)
Draw the Hasse diagram of the set {1, 3, 9, 18} under partial order relation ‘divides’ and
indicate those which are chains.
Answer
Let 𝐴 = {1, 3, 9, 18}.

Explanation

1) 1|3. Join 1 and 3 by an edge.

2) 3|9. Join 3 and 9 by an edge.
3) 9|18. Join 9 and 18 by an edge.

Hasse diagram

Since every two elements of given set are comparable (related), {1, 3, 9, 18} is a chain.

Question (DEC 2021 – 03 Marks)

Let 𝐴 be a given finite set and 𝜌(𝐴) its power set. Let ⊆ be the inclusion relation on the elements
of 𝜌(𝐴). Draw the Hasse diagram of ⟨𝜌(𝐴), ⊆⟩ for 𝐴 = {𝑎, 𝑏, 𝑐}.
OR
Question (OCT 2020 – 04 Marks)
Draw the Hasse diagram for the partial ordering {(𝐴, 𝐵) | 𝐴 ⊆ 𝐵} on the power set 𝑃(𝑆)
where 𝑆 = {𝑎, 𝑏, 𝑐}.
Answer
The power set of 𝐴 is denoted by 𝜌(𝐴) and it is given by

𝜌(𝐴) = {∅, {𝑎}, {𝑏}, {𝑐}, {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, {𝑎, 𝑏, 𝑐}}.

Here ⊆ be the inclusion (subset) relation defined on 𝜌(𝐴). That is, a set 𝑋 ∈ 𝜌(𝐴) is related
to a set 𝑌 ∈ 𝜌(𝐴) if 𝑋 is a subset of 𝑌.
Explanation

1) ∅ is a subset of every set. That is, ∅ is related to every element. So, keep vertex ∅ at the
extreme bottom.
 2) ∅ is a subset of {𝑎}, {𝑏} and {𝑐}. That is, ∅ ⊂ {𝑎}, ∅ ⊂ {𝑏} and ∅ ⊂ {𝑐}. So, join them
by an edge.
3) {𝑎} ⊂ {𝑎, 𝑏} and {𝑎} ⊂ {𝑎, 𝑐}. So, join them by an edge.
4) {𝑏} ⊂ {𝑎, 𝑏} and {𝑏} ⊂ {𝑏, 𝑐}. So, join them by an edge.
5) {𝑐} ⊂ {𝑎, 𝑐} and {𝑐} ⊂ {𝑏, 𝑐}. So, join them by an edge.
6) {𝑎, 𝑏}, {𝑏, 𝑐} and {𝑎, 𝑐} all are subsets of {𝑎, 𝑏, 𝑐}. That is, {𝑎, 𝑏} ⊂ {𝑎, 𝑏, 𝑐}, {𝑎, 𝑐} ⊂
{𝑎, 𝑏, 𝑐} and {𝑏, 𝑐} ⊂ {𝑎, 𝑏, 𝑐}. So, join them by an edge.

Hasse diagram

Question (DEC 2021 – 04 Marks) (FEB 2024 – 04 Marks)

Let 𝐴 be a given finite set and 𝜌(𝐴) its power set. Let ⊆ be the inclusion relation on the elements
of 𝜌(𝐴). Draw the Hasse diagram of ⟨𝜌(𝐴), ⊆⟩ for 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}.
Answer
The power set of 𝐴 is denoted by 𝜌(𝐴) and it is given by

𝜌(𝐴) = {∅, {𝑎}, {𝑏}, {𝑐}, {𝑑}, {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑎, 𝑑}, {𝑏, 𝑐}, {𝑏, 𝑑}, {𝑐, 𝑑}, {𝑎, 𝑏, 𝑐}, {𝑎, 𝑏, 𝑑},
{𝑎, 𝑐, 𝑑}, {𝑏, 𝑐, 𝑑}, {𝑎, 𝑏, 𝑐, 𝑑}}

Here ⊆ be the inclusion (subset) relation defined on 𝜌(𝐴). That is, a set 𝑋 ∈ 𝜌(𝐴) is related
to a set 𝑌 ∈ 𝜌(𝐴) if 𝑋 is a subset of 𝑌.
Explanation

1) ∅ is a subset of every set. That is, ∅ is related to every element. So, keep vertex ∅ at the
extreme bottom.
2) ∅ is a subset of {𝑎}, {𝑏}, {𝑐} and {𝑑}. That is, ∅ ⊂ {𝑎}, ∅ ⊂ {𝑏}, ∅ ⊂ {𝑐} and ∅ ⊂ {𝑑}.
So, join them by an edge.
3) {𝑎} ⊂ {𝑎, 𝑏}, {𝑎} ⊂ {𝑎, 𝑐} and {𝑎} ⊂ {𝑎, 𝑑}. So, join them by an edge.
 4) {𝑏} ⊂ {𝑎, 𝑏}, {𝑏} ⊂ {𝑏, 𝑐} and {𝑏} ⊂ {𝑏, 𝑑}. So, join them by an edge.
5) {𝑐} ⊂ {𝑎, 𝑐}, {𝑐} ⊂ {𝑏, 𝑐} and {𝑐} ⊂ {𝑐, 𝑑}. So, join them by an edge.
6) {𝑑} ⊂ {𝑎, 𝑑}, {𝑑} ⊂ {𝑏, 𝑑} and {𝑑} ⊂ {𝑐, 𝑑}. So, join them by an edge.
7) {𝑎, 𝑏} ⊂ {𝑎, 𝑏, 𝑐} and {𝑎, 𝑏} ⊂ {𝑎, 𝑏, 𝑑}. So, join them by an edge.
8) {𝑎, 𝑐} ⊂ {𝑎, 𝑏, 𝑐} and {𝑎, 𝑐} ⊂ {𝑎, 𝑐, 𝑑}. So, join them by an edge.
9) {𝑎, 𝑑} ⊂ {𝑎, 𝑏, 𝑑} and {𝑎, 𝑑} ⊂ {𝑎, 𝑐, 𝑑}. So, join them by an edge.
10) {𝑏, 𝑐} ⊂ {𝑎, 𝑏, 𝑐} and {𝑏, 𝑐} ⊂ {𝑏, 𝑐, 𝑑}. So, join them by an edge.
11) {𝑏, 𝑑} ⊂ {𝑎, 𝑏, 𝑑} and {𝑏, 𝑑} ⊂ {𝑏, 𝑐, 𝑑}. So, join them by an edge.
12) {𝑐, 𝑑} ⊂ {𝑎, 𝑐, 𝑑} and {𝑐, 𝑑} ⊂ {𝑏, 𝑐, 𝑑}. So, join them by an edge.
13) {𝑎, 𝑏, 𝑐}, {𝑎, 𝑏, 𝑑}, {𝑎, 𝑐, 𝑑} and {𝑏, 𝑐, 𝑑} all are subsets of {𝑎, 𝑏, 𝑐, 𝑑}. That is, {𝑎, 𝑏, 𝑐} ⊂
{𝑎, 𝑏, 𝑐, 𝑑}, {𝑎, 𝑏, 𝑑} ⊂ {𝑎, 𝑏, 𝑐, 𝑑}, {𝑎, 𝑐, 𝑑} ⊂ {𝑎, 𝑏, 𝑐, 𝑑} and {𝑏, 𝑐, 𝑑} ⊂ {𝑎, 𝑏, 𝑐, 𝑑}. So,
join them by an edge.
Hasse diagram

Special elements in POSET

Maximal element
Let ⟨ 𝐴 , ⪯ ⟩ be a poset. An element 𝑥 in the poset is called a maximal element of 𝐴 if 𝑥 is not
related to any other element of 𝐴.
Minimal element
Let ⟨ 𝐴 , ⪯ ⟩ be a poset. An element 𝑥 in the poset is called a minimal element of 𝐴 if no other
element of 𝐴 related to 𝑥.
Maximum element (Greatest element)
Let ⟨ 𝐴 , ⪯ ⟩ be a poset. An element 𝑥 in the poset is called a maximum element of 𝐴 if
 1) Every other element of 𝐴 is related to 𝑥.
2) 𝑥 is not related to any other element of 𝐴.
Minimum element (Least element)
Let ⟨ 𝐴 , ⪯ ⟩ be a poset. An element 𝑥 in the poset is called a minimum element of 𝐴 if
1) 𝑥 is related to every other element of 𝐴.
2) No other element of 𝐴 is related to 𝑥.
For example,
1) The Hasse diagram is shown below:

Since 𝑓 is not related to any other element, 𝒇 is the maximal element.

Since every other element is related to 𝑓 and the element 𝑓 is not related to any
element in the vertical direction, 𝒇 is the maximum (greatest) element.

Since no other element is related to 𝑎, an element 𝒂 is the minimal element.

Since 𝑎 is related to every other element and no other element is related to 𝑎, an

element 𝒂 is the minimum (least) element.

Important note
In the given Hasse diagram, there is an edge between 𝑎 and 𝑏. That is, 𝑎 is related to
𝑏. Note that 𝑏 is not related to 𝑎.
Also, 𝑎 is related to 𝑏 and 𝑏 is related to 𝑒. So, we can say that 𝑎 is related to 𝑒. Note
that 𝑒 is not related to 𝑎.

2) The Hasse diagram is shown below:

Since 4 , 6 and 5 are not related to any other element, 𝟒 , 𝟔 and 𝟓 are maximal
elements.
 Since every other element is not related to 4, the element 4 is not maximum (not
greatest) element.
Since every other element is not related to 6, the element 6 is not maximum (not
greatest) element.
Since every other element is not related to 5, the element 5 is not maximum (not
greatest) element.
Hence, there is no maximum (no greatest) element.
Since no other element is related to 1, an element 𝟏 is the minimal element.
Since 1 is related to every other element and no other element is related to 1, an
element 𝟏 is the minimum (least) element.
3) The Hasse diagram is shown below:

Since 12 and 18 are not related to any other element, 𝟏𝟐 and 𝟏𝟖 are maximal
elements.

Since every other element is not related to 12, the element 12 is not maximum (not
greatest) element.
Since every other element is not related to 18, the element 18 is not maximum (not
greatest) element.
Hence, there is no maximum (no greatest) element.

Since no other element is related to 2 and 3, the elements 𝟐 and 𝟑 are minimal
elements.

Since 2 is not related to every other element, the element 2 is not minimum (not
least) element.
Since 3 is not related to every other element, the element 3 is not minimum (not
least) element.
Hence, there is no minimum (no least) element.
Question (JULY 2022 – 03 Marks)
Draw the Hasse diagram for the poset ({2, 4, 5, 10, 12, 20, 25} , | ). Hence, find the maximal
and minimal elements.
Answer
Hasse diagram

Since 12, 20 and 25 are not related to any other element, 𝟏𝟐 , 𝟐𝟎 and 𝟐𝟓 are maximal
elements.
Since no other element is related to 2 and 5, the elements 𝟐 and 𝟓 are minimal elements.

Upper bound
Let ⟨ 𝐴 , ⪯ ⟩ be a poset and 𝐵 be the subset of a poset. An element 𝑥 of set 𝐴 is called an
upper bound of subset 𝐵 if all elements of 𝐵 are related to 𝑥.
Least upper bound (LUB) or Join
Let ⟨ 𝐴 , ⪯ ⟩ be a poset and 𝐵 be the subset of a poset. An element 𝑥 of set 𝐴 is called a least
upper bound of subset 𝐵 if
1) 𝑥 is an upper bound of 𝐵. That is, all elements of 𝐵 are related to 𝑥.
2) 𝑥 is related to any upper bound of 𝐵.
Lower bound
Let ⟨ 𝐴 , ⪯ ⟩ be a poset and 𝐵 be the subset of a poset. An element 𝑥 of set 𝐴 is called a lower
bound of subset 𝐵 if 𝑥 is related to all elements of 𝐵.
Greatest lower bound (GLB) or Meet
Let ⟨ 𝐴 , ⪯ ⟩ be a poset and 𝐵 be the subset of a poset. An element 𝑥 of set 𝐴 is called a
greatest lower bound of subset 𝐵 if
1) 𝑥 is a lower bound of 𝐵. That is, 𝑥 is related to all elements of 𝐵.
2) Any lower bound of 𝐵 is related to 𝑥.

Question
Draw the Hasse diagram representing the partial ordering {(𝑎, 𝑏) | 𝑎 divides 𝑏} on the set
{1, 2, 5, 10}. Find upper bounds, least upper bound, lower bounds and greatest lower bound of
subset {2, 5}.
Answer
Hasse diagram

Let 𝐵 = {2, 5} be the given subset. Note that 2 and 5 are not related.
Since 2 and 5 both are related to 10, the element 𝟏𝟎 is upper bound of the subset 𝐵 =
{2, 5}.
Since there is only one upper bound, it is also least upper bound. So, 𝟏𝟎 is least upper
bound of subset 𝐵.
Since 1 is related to both 2 and 5, the element 𝟏 is lower bound of the subset 𝐵 = {2, 5}.
Since there is only one lower bound, it is also greatest lower bound. So, 𝟏 is greatest lower
bound of subset 𝐵.
Question
Draw the Hasse diagram representing the partial ordering {(𝑎, 𝑏) | 𝑎 divides 𝑏} on
{1, 2, 3, 4, 6, 8, 12}. Find upper bounds, least upper bound, lower bounds and greatest lower
bound of the following subsets:
1) {2, 3}
2) {4, 6}
3) {3, 4}
4) {2, 3, 4}
5) {2, 4}
6) {2, 12}
7) {6, 8}
Answer
Hasse diagram

1) Let 𝐵 = {2, 3} be the given subset. Note that 2 and 3 are not related.
Since 2 and 3 both are related to 6 and 12, the elements 𝟔 and 𝟏𝟐 are upper bounds
of the subset 𝐵 = {2, 3}.
 Since 6 is an upper bound and 6 is related to other upper bound 12, the element 𝟔 is
least upper bound.
Since 1 is related to both 2 and 3, the element 𝟏 is lower bound of the subset
𝐵 = {2, 3}.
Since there is only one lower bound, it is also greatest lower bound. So, 𝟏 is greatest
lower bound of subset 𝐵.

2) Let 𝐵 = {4, 6} be the given subset. Note that 4 and 6 are not related.
Since 4 and 6 both are related to 12, the element 𝟏𝟐 is upper bound of the subset
𝐵 = {4, 6}.
Since there is only one upper bound, it is also least upper bound. So, 𝟏𝟐 is least
upper bound of subset 𝐵.
Since 1 and 2 both are related to 4 and 6, the elements 𝟏 and 𝟐 are lower bounds of
the subset 𝐵 = {4, 6}.
Since 2 is a lower bound and other lower bound 1 is related to 2, the element 𝟐 is
greatest lower bound.

3) Let 𝐵 = {3, 4} be the given subset. Note that 3 and 4 are not related.
Since 3 and 4 both are related to only 12, the upper bound is 𝟏𝟐 and the least upper
bound is also 𝟏𝟐.
Since only 1 is related to both 3 and 4, the lower bound is 𝟏 and the greatest lower
bound is also 𝟏.

4) Let 𝐵 = {2, 3, 4} be the given subset.

Since 2, 3 and 4 all are related to only 12, the upper bound is 𝟏𝟐 and the least upper
bound is also 𝟏𝟐.
Since only 1 is related to all 2, 3 and 4, the lower bound is 𝟏 and the greatest lower
bound is also 𝟏.

5) Let 𝐵 = {2,4} be the given subset. Note that 2 and 4 are related.
Since 2 and 4 are related, the upper bound and least upper bound is 𝟒.
Since 2 and 4 are related, the lower bound and greatest lower bound is 𝟐.

6) Let 𝐵 = {2,12} be the given subset. Since 2 is related to 4 and 4 is related to 12, the
element 2 is related to 12.
Since 2 is related to 12, the upper bound and least upper bound is 𝟏𝟐.
Since 2 is related to 12, the lower bound and greatest lower bound is 𝟐.

7) Let 𝐵 = {6,8} be the given subset. Note that 6 and 8 are not related.
Since 6 and 8 both are not related to any other element, there is no upper bound.
Hence, there is no least upper bound.
Since 1 and 2 both are related to 6 and 8, the lower bounds are 𝟏 and 𝟐.
Since 2 is a lower bound and other lower bound 1 is related to 2, the element 𝟐 is
greatest lower bound.
Question (JULY 2022 – 03 Marks)
Draw the Hasse diagram for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72} , | ). Hence, find
𝑔𝑙𝑏({60, 72}) and all maximal elements.
Answer
Hasse diagram

Since 12 , 6 , 4 , 2 are related to both 60 and 72, the lower bounds are 12 , 6 , 4 , 2.
Since all other lower bounds 2 , 4 and 6 are related to 12, the greatest lower bound is 12.
That is, 𝑔𝑙𝑏({60, 72}) = 𝟏𝟐.
Since 27 , 48 , 60 and 72 are not related to any other element, maximal elements are 𝟐𝟕 ,
𝟒𝟖 , 𝟔𝟎 and 𝟕𝟐.

Question
In the poset 𝑃 shown in the given figure, find upper bound and least upper bound for
𝐴 = {2, 3} and 𝐵 = {4, 6}.
Answer

The elements 2 and 3 of set 𝐴 are related to the elements 4 , 5 , 7 and 8. So, the upper
bounds of the given set 𝐴 = {2, 3} are 𝟒 , 𝟓 , 𝟕 and 𝟖.

Here 4 is an upper bound but 4 is not related to other upper bound 5. So, the least upper
bound of the given set 𝐴 = {2, 3} does not exist.

The elements 4 and 6 of set 𝐵 are related to the element 8 only. So, the upper bound and
least upper bound of the given set 𝐵 = {4, 6} is 𝟖.

Lattice
A lattice is a poset ⟨ 𝐿 , ⪯ ⟩ in which every pair of elements 𝑎 ∈ 𝐿 , 𝑏 ∈ 𝐿 has a greatest lower
bound and a least upper bound.
Important note
1) The greatest lower bound of a subset {𝑎 , 𝑏} is called meet and denoted by
𝐆𝐋𝐁{𝒂, 𝒃} or 𝐠𝐥𝐛{𝒂, 𝒃} or 𝒂 ∗ 𝒃 or 𝒂 ∧ 𝒃 or 𝒂 ∙ 𝒃.

2) The least upper bound of a subset {𝑎 , 𝑏} is called join and denoted by 𝐋𝐔𝐁{𝒂, 𝒃} or
𝐥𝐮𝐛{𝒂, 𝒃} or 𝒂 ⊕ 𝒃 or 𝒂 ∨ 𝒃 or 𝒂 + 𝒃.

3) The least upper bound of a subset {𝑎, 𝑎} is 𝑎. That is, 𝑎 ∨ 𝑎 = 𝑎.

4) The greatest lower bound of a subset {𝑎, 𝑎} is 𝑎. That is, 𝑎 ∧ 𝑎 = 𝑎.

5) If 𝑎 is related to 𝑏 then least upper bound of a subset {𝑎, 𝑏} is 𝑏. That is, 𝑎 ∨ 𝑏 = 𝑏.

6) If 𝑎 is related to 𝑏 then greatest lower bound of subset {𝑎, 𝑏} is 𝑎. That is, 𝑎 ∧ 𝑏 = 𝑎.

Question
Determine whether the poset represented by the given Hasse diagram is lattice.

Answer
Let 𝐿 = {1, 2, 3, 4, 6, 8, 12}.
Let 𝑎 = 8 ∈ 𝐿 and 𝑏 = 12 ∈ 𝐿.
Clearly, the least upper bound does not exist for the set {8, 12}. Hence, this is NOT a lattice.
Question
Draw the Hasse diagram for the poset ({1, 2, 3, 6} , | ). Determine whether the poset
represented by the Hasse diagram is lattice.
Answer
Hasse diagram

The least upper bound (lub) of {1, 1} is 1. The least upper bound (lub) of {1, 2} is 2.

The least upper bound (lub) of {1, 3} is 3. The least upper bound (lub) of {1, 6} is 6.

The least upper bound (lub) of {2, 1} is 2. The least upper bound (lub) of {2, 2} is 2.

The least upper bound (lub) of {2, 3} is 6. The least upper bound (lub) of {2, 6} is 6.

The least upper bound (lub) of {3, 1} is 3. The least upper bound (lub) of {3, 2} is 6.

The least upper bound (lub) of {3, 3} is 3. The least upper bound (lub) of {3, 6} is 6.

The least upper bound (lub) of {6, 1} is 6. The least upper bound (lub) of {6, 2} is 6.

The least upper bound (lub) of {6, 3} is 6. The least upper bound (lub) of {6, 6} is 6.

Write least upper bounds of all possible subsets in the table format. That is, construct the
closure table for least upper bound (lub or ∨).
∨ (lub) 1 2 3 6
1 1 2 3 6
2 2 2 6 6
3 3 6 3 6
6 6 6 6 6

The greatest lower bound (glb) of {1, 1} is 1. The greatest lower bound (glb) of {1, 2} is 1.

The greatest lower bound (glb) of {1, 3} is 1. The greatest lower bound (glb) of {1, 6} is 1.

The greatest lower bound (glb) of {2, 1} is 1. The greatest lower bound (glb) of {2, 2} is 2.

The greatest lower bound (glb) of {2, 3} is 1. The greatest lower bound (glb) of {2, 6} is 2.
The greatest lower bound (glb) of {3, 1} is 1. The greatest lower bound (glb) of {3, 2} is 1.

The greatest lower bound (glb) of {3, 3} is 3. The greatest lower bound (glb) of {3, 6} is 3.

The greatest lower bound (glb) of {6, 1} is 1. The greatest lower bound (glb) of {6, 2} is 2.

The greatest lower bound (glb) of {6, 3} is 3. The greatest lower bound (glb) of {6, 6} is 6.

Write greatest lower bounds of all possible subsets in the table format. That is, construct the
closure table for greatest lower bound (glb or ∧).
∧ (glb) 1 2 3 6
1 1 1 1 1
2 1 2 1 2
3 1 1 3 3
6 1 2 3 6
Since every pair of elements has a greatest lower bound and a least upper bound, the given
poset is Lattice.
Question
Determine whether the poset represented by the given Hasse diagram is lattice.

Answer
Construct the closure table for least upper bound (lub or ∨).
∨ (lub) 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑎 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑏 𝑏 𝑏 𝑑 𝑑 𝑒 𝑓 𝑔
𝑐 𝑐 𝑑 𝑐 𝑑 𝑒 𝑓 𝑔
𝑑 𝑑 𝑑 𝑑 𝑑 𝑒 𝑓 𝑔
𝑒 𝑒 𝑒 𝑒 𝑒 𝑒 𝑔 𝑔
𝑓 𝑓 𝑓 𝑓 𝑓 𝑔 𝑓 𝑔
𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔
Construct the closure table for greatest lower bound (glb or ∧).
∧ (glb) 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑎 𝑎 𝑎 𝑎 𝑎 𝑎 𝑎 𝑎
𝑏 𝑎 𝑏 𝑎 𝑏 𝑏 𝑏 𝑏
𝑐 𝑎 𝑎 𝑐 𝑐 𝑐 𝑐 𝑐
𝑑 𝑎 𝑏 𝑐 𝑑 𝑑 𝑑 𝑑
𝑒 𝑎 𝑏 𝑐 𝑑 𝑒 𝑑 𝑒
𝑓 𝑎 𝑏 𝑐 𝑑 𝑑 𝑓 𝑓
𝑔 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔

Since every pair of elements has a greatest lower bound and a least upper bound, the given
poset is Lattice.
Question (SEP 2021 – 07 Marks)
Let 𝐴 be the set of factors of positive integer 𝑚 and relation is divisibility on 𝐴. For 𝑚 = 45,
show that POSET (𝐴, ≤) is a Lattice.
Answer
The factors of 45 are 1, 3, 5, 9, 15, 45. Therefore, 𝐴 = {1, 3, 5, 9, 15, 45}.
Hasse diagram

Construct the closure table for least upper bound (lub or ∨).
∨ (lub) 1 3 5 9 15 45
1 1 3 5 9 15 45
3 3 3 15 9 15 45
5 5 15 5 45 15 45
9 9 9 45 9 45 45
15 15 15 15 45 15 45
45 45 45 45 45 45 45
Construct the closure table for greatest lower bound (glb or ∧).
∧ (glb) 1 3 5 9 15 45
1 1 1 1 1 1 1
3 1 3 1 3 3 3
5 1 1 5 1 5 5
9 1 3 1 9 3 9
15 1 3 5 3 15 15
45 1 3 5 9 15 45

Since every pair of elements has a greatest lower bound and a least upper bound, the given
poset is Lattice.

Question
Determine whether the poset represented by the given Hasse diagram is lattice.

Answer
Construct the closure table for least upper bound (lub or ∨).
∨ (lub) 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑎 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑏 𝑏 𝑏 𝑑 𝑑 𝑒 𝑓 𝑔
𝑐 𝑐 𝑑 𝑐 𝑑 𝑒 𝑓 𝑔
𝑑 𝑑 𝑑 𝑑 𝑑 𝑒 𝑓 𝑔
𝑒 𝑒 𝑒 𝑒 𝑒 𝑒 𝑓 𝑔
𝑓 𝑓 𝑓 𝑓 𝑓 𝑓 𝑓 Does not exist (DNE)
𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 DNE 𝑔
Since every pair of elements has NOT a least upper bound, the given poset is NOT a Lattice.
Construct the closure table for greatest lower bound (glb or ∧).
∧ (glb) 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔
𝑎 𝑎 𝑎 𝑎 𝑎 𝑎 𝑎 𝑎
𝑏 𝑎 𝑏 𝑎 𝑏 𝑏 𝑏 𝑏
𝑐 𝑎 𝑎 𝑐 𝑐 𝑐 𝑐 𝑐
𝑑 𝑎 𝑏 𝑐 𝑑 𝑑 𝑑 𝑑
𝑒 𝑎 𝑏 𝑐 𝑑 𝑒 𝑒 𝑒
𝑓 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑒
𝑔 𝑎 𝑏 𝑐 𝑑 𝑒 𝑒 𝑔

Note that every pair of elements has a greatest lower bound.

Question (FEB 2021 – 04 Marks) (OCT 2020 – 04 Marks)

Define lattice. Determine whether POSET {{1, 2, 3, 4, 5} ; |} is a lattice.

Answer

Definition

A lattice is a poset ⟨ 𝐿 , ⪯ ⟩ in which every pair of elements 𝑎 ∈ 𝐿 , 𝑏 ∈ 𝐿 has a greatest lower

bound and a least upper bound.

Hasse diagram

Construct the closure table for least upper bound (lub or ∨).
∨ (lub) 1 2 3 4 5
1 1 2 3 4 5
2 2 2 − 4 −
3 3 − 3 − −
4 4 4 − 4 −
5 5 − − − 5

For the pair of elements (2, 3) and for other few pairs, there is no upper bound. Hence, the
least upper bound does not exist. This implies that {{1, 2, 3, 4, 5} ; |} is NOT a lattice.

Question (JULY 2023 – 07 Marks)

Define Lattice and draw the Hasse diagram representing the partial ordering {(𝐴, 𝐵) ∶ 𝐴 ⊆
𝐵} on the power set 𝑃(𝑆) where 𝑆 = {1, 2, 3}. Find the maximal, minimal, greatest and least
elements of the poset.

Answer

Definition

A lattice is a poset ⟨ 𝐿 , ⪯ ⟩ in which every pair of elements 𝑎 ∈ 𝐿 , 𝑏 ∈ 𝐿 has a greatest lower

bound and a least upper bound.

The power set of 𝑆 is denoted by 𝑃(𝑆) and it is given by

𝑃(𝑆) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Here ⊆ be the inclusion (subset) relation defined on 𝑃(𝑆). That is, a set 𝑋 ∈ 𝑃(𝑆) is related to
a set 𝑌 ∈ 𝑃(𝑆) if 𝑋 is a subset of 𝑌.
Hasse diagram

Since {1, 2, 3} is not related to any other element, {𝟏, 𝟐, 𝟑} is the maximal element.
Since there is only one maximal, {𝟏, 𝟐, 𝟑} is also maximum (greatest) element.
Since no other element is related to ∅, the element ∅ is the minimal element.
Since there is only one minimal, ∅ is also minimum (least) element.

Some Special Lattices

Complete Lattice
A lattice is called complete lattice if each of its non-empty subsets has a least upper bound
and a greatest lower bound.
Important points
1) Every finite lattice is complete lattice.
2) Every complete lattice must have a least (minimum) element and a greatest
(maximum) element.
3) The least (minimum) and greatest (maximum) elements of a lattice are called bounds
(units, universal bounds) of the lattice.
Bounded Lattice
The least (minimum) element of a lattice is denoted by 𝟎 and the greatest (maximum)
element of a lattice is denoted by 𝟏. A lattice which has both elements 0 and 1 is called a
bounded lattice and is often denoted by (𝐿 , ∨ , ∧ , 0 , 1).
For example, the poset represented by the given Hasse diagram is bounded lattice because it
has both elements 0 and 1. That is, it has least element ∅ which is denoted by 0 and greatest
element {1, 2, 3} which is denoted by 1.

Complement of an element
In a bounded lattice (𝐿 , ∨ , ∧ , 0 , 1), an element 𝑏 ∈ 𝐿, is called a complement of an
element 𝑎 ∈ 𝐿 if
𝑎∧𝑏=0 and 𝑎∨𝑏=1
That is, 𝑏 is a complement of 𝑎 if the least upper bound of 𝑎 and 𝑏 is greatest (maximum)
element and the greatest lower bound of 𝑎 and 𝑏 is least (minimum) element.

Important points
1) If 𝑎 is a complement of 𝑏 then we can say that 𝑏 is a complement of 𝑎.
2) An element may or may not have a complement.
3) An element may have more than one complement. That is, complements are not
unique.
4) In any bounded lattice, the bounds 0 and 1 are unique complements of each other
because 0 ∨ 1 = 1 and 0 ∧ 1 = 0. That is, the least (minimum) and greatest
(maximum) elements are unique complements of each other.
Complemented Lattice
A lattice 𝐿 is called complemented lattice if it is bounded lattice and if every element in 𝐿
has a complement.
For example, consider the poset ({1, 2, 3, 6} , | ) represented by the given Hasse diagram.

The least element is 1 and the greatest element is 6. So, it is bounded lattice.

The complement of an element 1 is 6 because 1 ∨ 6 = 6 (greatest element) and 1 ∧ 6 = 1

(least element). Also, the complement of an element 6 is 1.

The complement of an element 2 is 3 because 2 ∨ 3 = 6 (greatest element) and 2 ∧ 3 = 1

(least element). Also, the complement of an element 3 is 2.

Since the lattice is bounded and every element has a complement, it is a complemented
lattice.

Distributive Lattice
A lattice (𝐿 , ∨ , ∧) is called a distributive lattice if for any 𝑎, 𝑏, 𝑐 ∈ 𝐿,
𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐)
𝑎 ∨ (𝑏 ∧ 𝑐) = (𝑎 ∨ 𝑏) ∧ (𝑎 ∨ 𝑐)
Important point
Both the equalities are equivalent to one another, it is sufficient to verify any one equality to
check whether the lattice is distributed or not.
For example, consider the poset ({1, 2, 3, 6} , | ) represented by the given Hasse diagram.

Let 𝑎 = 1, 𝑏 = 2 and 𝑐 = 6. Then,

𝑎 ∧ (𝑏 ∨ 𝑐) = 1 ∧ (2 ∨ 6) = 1 ∧ 6 = 𝟏 and
(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐) = (1 ∧ 2) ∨ (1 ∧ 6) = 1 ∨ 1 = 𝟏
Hence, 𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).
Let 𝑎 = 2, 𝑏 = 3 and 𝑐 = 6. Then,
𝑎 ∧ (𝑏 ∨ 𝑐) = 2 ∧ (3 ∨ 6) = 2 ∧ 6 = 𝟐 and
(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐) = (2 ∧ 3) ∨ (2 ∧ 6) = 1 ∨ 2 = 𝟐
Hence, 𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).
Similarly, we can verify any one equality for any 𝑎, 𝑏, 𝑐 ∈ 𝐿. Since the equality is verified for
any 𝑎, 𝑏, 𝑐 ∈ 𝐿, it is a distributive lattice.
Question
Show that the lattice given in the following diagram is not distributive lattice.

Answer
Let 𝑎 = 𝑢 , 𝑏 = 𝑣 and 𝑐 = 𝑤. Then,
𝑎 ∧ (𝑏 ∨ 𝑐) = 𝑢 ∧ (𝑣 ∨ 𝑤) = 𝑢 ∧ 1 = 𝒖 and
(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐) = (𝑢 ∧ 𝑣) ∨ (𝑢 ∧ 𝑤) = 0 ∨ 0 = 𝟎
Hence, 𝑎 ∧ (𝑏 ∨ 𝑐) ≠ (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).
Therefore, it is NOT distributive lattice.

Modular Lattice
A lattice (𝐿 , ∨ , ∧) is called a modular lattice if 𝑎 ∨ (𝑏 ∧ 𝑐) = (𝑎 ∨ 𝑏) ∧ 𝑐 whenever 𝑎 ⪯ 𝑐
for all 𝑎, 𝑏, 𝑐 ∈ 𝐿.
Boolean Lattice
A complemented distributive lattice is called a Boolean lattice.
Boolean Algebra
An algebraic system defined on Boolean lattices is known as Boolean algebra.
Finite Boolean Algebra
A bounded, complemented and distributive lattice is known as finite Boolean algebra.
Question (SEP 2021 – 03 Marks)
Define: Bounded, Distributive and Complemented Lattices.
Answer
The least (minimum) element of a lattice is denoted by 0 and the greatest (maximum) element
of a lattice is denoted by 1. A lattice which has both elements 0 and 1 is called a bounded
lattice and is often denoted by (𝐿 , ∨ , ∧ , 0 , 1).

A lattice (𝐿 , ∨ , ∧) is called a distributive lattice if for any 𝑎, 𝑏, 𝑐 ∈ 𝐿,

𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐)
𝑎 ∨ (𝑏 ∧ 𝑐) = (𝑎 ∨ 𝑏) ∧ (𝑎 ∨ 𝑐)

A lattice 𝐿 is called complemented lattice if it is bounded lattice and if every element in 𝐿 has
a complement.
Question (SEP 2021 – 01 Mark)
Define Boolean algebra.
Answer
A complemented distributive lattice is called a Boolean lattice. An algebraic system defined
on Boolean lattices is known as Boolean algebra.
Question (FEB 2024 – 07 Marks)
Prove that ⟨𝑆30 , 𝐷⟩ is a Boolean algebra.
Answer
Let 𝑆30 be the set of divisors of 30 and 𝐷 be the relation “divides”.
The divisors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. Therefore, 𝑆30 = {1, 2, 3, 5, 6, 10, 15, 30}.
Hasse diagram

𝟑𝟎 is maximum (greatest) element and 𝟏 is minimum (least) element.

It is bounded lattice because it has both least element and greatest element.
The complement of 1 is 30.
The complement of 2 is 15.
The complement of 3 is 10.
The complement of 5 is 6.
Since every element has a complement, it is complemented lattice.

Let 𝑎 = 6 , 𝑏 = 10 and 𝑐 = 3. Then,

𝑎 ∧ (𝑏 ∨ 𝑐) = 6 ∧ (10 ∨ 3) = 6 ∧ 30 = 𝟔 and
(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐) = (6 ∧ 10) ∨ (6 ∧ 3) = 2 ∨ 3 = 𝟔
Hence, 𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).
Similarly, we can verify any one equality for any 𝑎, 𝑏, 𝑐 ∈ 𝐿. Since the equality is verified for
any 𝑎, 𝑏, 𝑐 ∈ 𝐿, it is a distributive lattice.

Since it is bounded, complemented and distributive lattice, it is a finite Boolean algebra.

Question
Prove that ⟨𝑃(𝑆) , ⊆⟩ is a finite Boolean algebra where 𝑆 is any finite set with 𝑛 elements and
⊆ is the inclusion (subset) relation defined on the power set 𝑃(𝑆) of 𝑆.
Answer
Let 𝑆 = {1, 2, 3}. Then, the power set of 𝑆 is denoted by 𝑃(𝑆) and it is given by
𝑃(𝑆) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Hasse diagram
{𝟏, 𝟐, 𝟑} is maximum (greatest) element and ∅ is minimum (least) element.
It is bounded lattice because it has both least element and greatest element.

The complement of ∅ is {1, 2, 3}.

The complement of {1} is {2, 3}.
The complement of {2} is {1, 3}.
The complement of {3} is {1, 2}.
Since every element has a complement, it is complemented lattice.

Let 𝑎 = {1} , 𝑏 = {2, 3} and 𝑐 = {3}. Then,

𝑎 ∧ (𝑏 ∨ 𝑐) = {1} ∧ ({2,3} ∨ {3}) = {1} ∧ {2,3} = ∅ and
(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐) = ({1} ∧ {2,3}) ∨ ({1} ∧ {3}) = ∅ ∨ ∅ = ∅
Hence, 𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).
Similarly, we can verify any one equality for any 𝑎, 𝑏, 𝑐 ∈ 𝐿. Since the equality is verified for
any 𝑎, 𝑏, 𝑐 ∈ 𝐿, it is a distributive lattice.

Since it is bounded, complemented and distributive lattice, it is a finite Boolean algebra.

Question (JULY 2023 – 04 Marks)

Show that in a lattice if 𝑎 ≤ 𝑏 ≤ 𝑐, then (I) 𝑎⨁𝑏 = 𝑏 ∗ 𝑐 and
(II) (𝑎 ∗ 𝑏)⨁(𝑏 ∗ 𝑐) = 𝑏 = (𝑎⨁𝑏) ∗ (𝑎⨁𝑐).
Answer
Given that 𝑎 ≤ 𝑏 ≤ 𝑐. That is, 𝑎 is related to 𝑏 and 𝑏 is related to 𝑐. That is, 𝑎 is related to 𝑐.
(I)
Since 𝑎 is related to 𝑏, the least upper bound of 𝑎 and 𝑏 is 𝑏. That is, 𝑎⨁𝑏 = 𝒃. Note that
here the symbol ⨁ is used for least upper bound.
Since 𝑏 is related to 𝑐, the greatest lower bound of 𝑏 and 𝑐 is 𝑏. That is, 𝑏 ∗ 𝑐 = 𝒃. Note that
here the symbol ∗ is used for greatest lower bound.
Hence, 𝑎⨁𝑏 = 𝑏 ∗ 𝑐.
(II)
(𝑎 ∗ 𝑏)⨁(𝑏 ∗ 𝑐)
= (𝑎 ∧ 𝑏) ∨ (𝑏 ∧ 𝑐)
=𝑎∨𝑏
=𝒃
(𝑎⨁𝑏) ∗ (𝑎⨁𝑐)
= (𝑎 ∨ 𝑏) ∧ (𝑎 ∨ 𝑐)
=𝑏∧𝑐
=𝒃
Hence, (𝑎 ∗ 𝑏)⨁(𝑏 ∗ 𝑐) = 𝑏 = (𝑎⨁𝑏) ∗ (𝑎⨁𝑐).

TRY YOURSELF