Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
MASTER OF COMPUTER APPLICATIONS
SEMESTER 1
DISCRETE MATHEMATICS AND
GRAPH THEORY
Unit 1: Introduction to POSET 1
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
Unit 1
Introduction to POSET
Table of Contents
SL Topic Fig No / Table / SAQ / Page No
No Graph Activity
1 Pre-Requisites - -
1.1 Objectives - -
1.2 Cartesian Product - -
3- 6
1.3 Relations - -
1.4 Different types of relations - -
1.5 Directed graph of a relation - -
2 Introduction - - 7
3 Definitions and Examples - -
3.1 Partial order - -
3.2 HASSE Diagram (or) POSET Diagram 8 - 12
- -
(or) Digraph of a partial order:
3.3 External element - -
4 Comparable and Non-Comparable Elements - -
4.1 Comparable Elements - -
13 - 14
4.2 Non-Comparable Elements - -
4.3 Linearly Ordered Set - -
5 Self-assessment questions - 15 – 17
6 Summary - - 17
7 References - - 17
Unit 1: Introduction to POSET 2
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
1. (PRE-REQUISITES)
1.1 Objectives:
The objective of this topic is to make the students to:
❖ Understand concept of partial order.
❖ Understand and implement properties of POSET.
1.2. Cartesian Product
Let 𝐴 and 𝐵 be any two non-empty sets. The Cartesian product (or) cross product of 𝐴 and 𝐵
denoted by 𝐴 × 𝐵 is set of all ordered pairs (𝑎, 𝑏) where 𝑎 belongs to 𝐴 and 𝑏 belongs to 𝐵.
𝐴 × 𝐵 = {(𝑥, 𝑦): 𝑥 ∈ 𝐴, 𝑦 ∈ 𝐵}.
Note:
If A and B are finite then the Cardinality of |𝐴 × 𝐵| = |𝐴| × |𝐵|.
Example: Let 𝐴 = {1,2,3} and B= {𝑝, 𝑞, 𝑟}, then
𝐴 × 𝐵 = {(1, 𝑝), (1, 𝑞), (1, 𝑟), (2, 𝑝), (2, 𝑞), (2, 𝑟), (3, 𝑝), (3, 𝑞), (3, 𝑟)}
and |𝐴 × 𝐵| = |𝐴| × |𝐵| = 3 × 3 = 9
1.3. Relations:
Let 𝐴 and 𝐵 be any two non-empty sets. The Cartesian product (or) cross product of 𝐴 and 𝐵
denoted by 𝐴 × 𝐵 is set of all ordered pairs (𝑎, 𝑏) where 𝑎 belongs to 𝐴 and 𝑏 belongs to 𝐵.
∴ 𝐴 × 𝐵 = {(𝑎, 𝑏)/𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵}
Thus a relation 𝑅 from a non-empty set 𝐴 to a non-empty set 𝐵 is a subset of a Cartesian
product 𝐴 × 𝐵.
i.e., If (𝑎, 𝑏) ∈ 𝑅, we say that 𝑎 is related 𝑏 and we write 𝑎𝑅𝑏
Note:
Unit 1: Introduction to POSET 3
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
|𝐴| = 𝑚, |𝐵| = 𝑛 then total number of relations from 𝐴 to 𝐵 formed is given by 2𝑚𝑛
When a relation is defined on 𝐴 i.e., (𝐴 𝑡𝑜 𝐴) then the relation is called binary relation.
1.4. Different types of relations:
Reflexive relation:
A relation 𝑅 defined on set 𝐴 is called reflexive relation if 𝑎𝑅𝑎, ∀ 𝑎 ∈ 𝐴
Example
Let 𝐴 = {1,2,3,4} then
𝑅1 = {(1,1), (2,2), (3,3), (4,4)} →Reflexive
𝑅2 = {(1,1), (2,2), (3,2), (4,4)} → Non-reflexive
𝑅3 = {(1,2), (2,3), (3,4), (4,1)} → Irreflexive
Note:
• A relation in which no element is related to itself is called Irreflexive relation.
• In the relation if at least one element is not related itself then it is called Non-reflexive.
Symmetric relation:
Let 𝑅 be relation defined on set 𝐴, 𝑅 is called symmetric relation 𝐼𝑓 𝑎𝑅𝑏 ⇒ 𝑏𝑅𝑎
Example
Let 𝐴 = {1,2,3,4} then
𝑅1 = {(1,2), (2,1), (3,2), (2,3), (4,4)} → Symmetric.
𝑅2 = {(1,2), (3,2), (2,3), (4,4)} → Not symmetric (Asymmetric).
Note:
Unit 1: Introduction to POSET 4
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
A relation which is not symmetric is called asymmetric relation.
Antisymmetric relation:
Let 𝑅 be set defined on a set 𝐴. Then 𝑅 is an antisymmetric relation
𝐼𝑓 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑎 ⇒ 𝑎 = 𝑏
Example
i. 𝑎 ≤ 𝑏 𝑎𝑛𝑑 𝑏 ≤ 𝑎 ⇒ 𝑎 = 𝑏.
ii. 𝑎 ≥ 𝑏 𝑎𝑛𝑑 𝑏 ≥ 𝑎 ⇒ 𝑎 = 𝑏.
iii. 𝐴 ⊆ 𝐵 𝑎𝑛𝑑 𝐵 ⊆ 𝐴 ⇒ 𝐴 = 𝐵.
Transitive relation:
Let 𝑅 is a relation defined on a set 𝐴. Then 𝑅 is called transitive relation 𝐼𝑓 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒
𝑎𝑅𝑐
Example
Let 𝐴 = {1,2,3,4,5} then
𝑅1 = {(1,2), (2,3), (1,3), (3,4), (4,5), (3,5)} → Transitive.
𝑅2 = {(1,2), (2,3)} → Not Transitive.
Equivalence relation:
A relation 𝑅 is defined on a set 𝐴. then 𝑅 is called an equivalence relation. If it is reflexive,
symmetric, and transitive.
1.5. Directed graph of a relation:
Let 𝐴 relation 𝑅 on set 𝐴 [𝑅 ⊆ 𝐴 × 𝐴] can be represented pictorially as follows
Step 1: Draw small circles representing the element of 𝐴. This circle is called vertex or node.
Unit 1: Introduction to POSET 5
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
Step 2: Draw an arrow from vertex 𝑎1 to vertex 𝑎2 iff 𝑎1 is related to 𝑎2 . This arrow is called
edge.
Note: If 𝑎1 is related to itself then, we write the arrow which starts from vertex 𝑎1 and ends
at vertex 𝑎1 and it is called loop
The resulting pictorial representation is known as directed graph of a relation.
Example
Let 𝐴 = {1,2,3,4} and 𝑅 = {(1,1)(2,3), (3,4), (4,1)} the digraph of the Relation is given by
1 2
3 4
Unit 1: Introduction to POSET 6
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
2. INTRODUCTION
We often utilize relations to arrange some or all of the components in a set. For example, in
the dictionary, we rank words using the relation comprising pairs of words (x, y), where x
comes before y. We plan projects using the pairwise relation (x, y), where x and y are project
activities that must be completed before y may begin. We use the relation containing the
pairings (x, y) where x is smaller than y to arrange the set of numbers. When we add all of
the pairings of the type (x, x) to these relations, we get a reflexive, antisymmetric, and
transitive relation. These are the characteristics of the relations used to organize the
components of sets.
Unit 1: Introduction to POSET 7
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
3. DEFINITIONS AND EXAMPLES
3.1. Partial order:
A relation 𝑅 is defined on a set 𝐴 is called a partial order. If it is reflexive, antisymmetric, and
transitive. (𝑅, 𝐴) is called partially ordered or POSET.
EXAMPLE: Show that the “greater than or equal” relation (≥) is a partial ordering on the set
of integers.
Solution:
WKT a ≥ a for every integer a,
Therefore ≥ is reflexive.
If a ≥ b and b ≥ a, then a = b.
Hence, ≥ is antisymmetric.
Finally, ≥ is transitive because a ≥ b and b ≥ c imply that a ≥ c.
It follows that ≥ is a partial ordering on the set of integers and (Z, ≥) is a poset.
3.2. HASSE Diagram (or) POSET Diagram (or) Digraph of a partial order:
While drawing the directed graph of a partial order we use the following conventional
conditions
1) As 𝑅 is reflexive every element is related to itself, therefore self-loop need not be
shown.
2) As 𝑅 is transitive 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐 we need not draw an edge from 𝑎 𝑡𝑜 𝑐.
3) We represent element of a set 𝐴 by dots.
4) The digraph drawn in such a way that there edges always upwards. We need not show
direction.
Unit 1: Introduction to POSET 8
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
The directed graph obtained using the above is known as POSET diagram or Hasse diagram.
EXAMPLE: Let R be a relation defined on set 𝑨={𝟏,𝟐,𝟑,𝟒} “𝒙𝑹𝒚 𝒊𝒇𝒇 𝒙 𝒅𝒊𝒗𝒊𝒅𝒆𝒔 𝒚" show that
R is a partial order and draw the Hasse diagram/Poset Diagram.
Solution
Reflexive:
We know every number divides itself
⇒ 𝑥 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑥
⇒ 𝑥𝑅𝑥
⇒ 𝑅 𝑖𝑠 𝑟𝑒𝑓𝑙𝑒𝑥𝑖𝑣𝑒
Antisymmetric:
wkt if 𝑥 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑦 & 𝑦 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑥 𝑡ℎ𝑒𝑛 𝑥 = 𝑦
4
⇒ 𝑥𝑅𝑦 & 𝑦𝑅𝑥 ⇒ 𝑥 = 𝑦
⇒ 𝑅 𝑖𝑠 𝑎𝑛𝑡𝑖𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐 3 2
Transitive:
1
wkt if 𝑥|𝑦 & 𝑦|𝑧 then 𝑥|𝑧
i.e., if 𝑥𝑅𝑦 & 𝑦𝑅𝑧 then 𝑥𝑅𝑧
⇒ 𝑅 𝑖𝑠 𝑇𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒
∴ 𝑅 is partial order
𝑅 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
Example: Draw the Hasse diagram representing the positive divisors of 36
Solution
The set of all positive divisors of 36 is 𝐷36 = {1,2,3,4,6,9,12,18,36}
Unit 1: Introduction to POSET 9
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
The relation 𝑅 is a divisibility (that 𝑎𝑅𝑏 if and only if 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏) is a partial order on this
set. The Hasse diagram for this partial order is required here
We note that, under 𝑅
1 is related all elements of 𝐷36
2 is related to 2, 4, 6, 12, 18, 36
3 is related to 3, 6, 9, 12, 18, 36
4 is related to 4, 12, , 36
6 is related to 6, 12, 18, 36
9 is related to 9, 18, 36
12 is related to 12, 36
18 is related to 18, 36
36 s related 36
3.3. External element:
Maximal element: An element 𝑎 is maximal element of 𝐴 iff in the Hasse diagram of 𝑅 no
edge starts at 𝑎.
Minimal element: An element 𝑎 is minimal element of 𝐴 iff in the Hasse diagram of 𝑅 no
edge terminates at 𝑎.
Greatest element: An element 𝑎 ∈ 𝐴 is called the greatest element if all elements are related
to 𝑎.
Least element: An element 𝑎 ∈ 𝐴 is called the least element if 𝑎 related to all element of 𝐴.
Upper bound: Let 𝐵 be a subset of 𝐴, an element 𝑎 ∈ 𝐴 is called an upper bound of 𝐵 if all
the element of 𝐵 are related to 𝑎.
Unit 1: Introduction to POSET 10
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
Lower bound: Let 𝐵 be a subset of 𝐴, an element 𝑎 ∈ 𝐴 is called an upper bound of 𝐵 if a
related to all the element of 𝐵.
Least upper bound (Supremum): An element 𝑎 ∈ 𝐴 is called as least upper bound of a
subset 𝐵, if the following two conditions holds good
1) If 𝑎 is an upper bound.
2) If 𝑎 related to all upper bound.
Greatest lower bound (Infimum): An element 𝑎 ∈ 𝐴 is called as greatest lower bound of a
subset 𝐵, if the following two conditions holds good
i) If 𝑎 is lower bound.
ii) All lower bounds are related to 𝑎.
Example
Find the maximal, minimal, greatest, and least element (if any) in the given Hasse diagram
f f g
g h
e
e
f
d
d e c d c
c b
b
a b
a
a
Fig 1 Fig 2 Fig 3
Unit 1: Introduction to POSET 11
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
Solution
Unit 1: Introduction to POSET 12
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
4. COMPARABLE AND NON-COMPARABLE ELEMENTS
4.1. Comparable Elements:
Consider an ordered set A. Two elements a and b of set A are called comparable if a≤b
or b≤a
4.2. Non-Comparable Elements:
Consider an ordered set A. Two elements a and b of set A are called non-comparable if neither
a ≤ b nor b ≤ a.
Example: Consider A = {1, 2, 3, 5, 6, 10, 15, 30} is ordered by divisibility. Determine all the
comparable and non-comparable pairs of elements of A.
Solution:
The comparable pairs of elements of A are:
{1, 2}, {1, 3}, {1, 5}, {1, 6}, {1, 10}, {1, 15}, {1, 30}
{2, 6}, {2, 10}, {2, 30}
{3, 6}, {3, 15}, {3, 30}
{5, 10}, {5, 15}, {5, 30}
{6, 30}, {10, 30}, {15, 30}
The non-comparable pair of elements of A are:
{2, 3}, {2, 5}, {2, 15}
{3, 5}, {3, 10}, {5, 6}, {6, 10}, {6, 15}, {10, 15}
4.3. Linearly Ordered Set:
Consider an ordered set A. The set A is called linearly ordered set or totally ordered set, if
every pair of elements in A is comparable.
Unit 1: Introduction to POSET 13
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
Example: The set of positive integers I+ with the usual order ≤ is a linearly ordered set.
Note: Let 𝑅 be a parial order on set 𝐴. Then 𝑅 is called a total order on 𝐴 if for all 𝑥, 𝑦 ∈ 𝐴
either 𝑥𝑅𝑦 𝑜𝑟 𝑦𝑅𝑥. In this case the poset (𝐴, 𝑅) is called a totally ordered set.
Unit 1: Introduction to POSET 14
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
5. SELF-ASSESSMENT QUESTIONS
SA1: Let 𝐴 = {1,2,3,4,6,12} and on A define the relation 𝑅 by 𝑎𝑅𝑏 if "𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏" prove that R
is a partial order on 𝐴 and Hasse Diagram of this relation.
Solution
𝑅 = {(1,1), (1,2), (1,3), (1,4), (1,6), (1,12), (2,2), (2,4), (2,6), (2,12),
(3,3), (3,6), (3,12), (4,4), (4,12), (6,6), (6,12), (12,12)}
We observe the following.
(𝑥, 𝑥) ∈ 𝑅 ∀𝑥 ∈ 𝐴 ⇒ 𝑅 𝑖𝑠 𝑟𝑒𝑓𝑙𝑒𝑥𝑖𝑣𝑒
When (𝑥, 𝑦) ∈ 𝑅 and 𝑦 ≠ 𝑥, (𝑦, 𝑥) ∉ 𝑅 ⇒ 𝑅 𝑖𝑠 𝑎𝑛𝑡𝑖𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐
Also, we can see that when (𝑥, 𝑦) 𝑎𝑛𝑑 (𝑦, 𝑧) ∈ 𝑅, then (𝑥, 𝑧) ∈ 𝑅 which ensures that the
transitive property.
Hence, we conclude that R is a partial order
12on A
4 6
2 3
1
SA2: Let R be the relation on the set of people such that xRy if x and y are people and x is
older than y. Show that R is not a partial ordering.
Solution:
Note that R is antisymmetric because if a person x is older than a person y, then y is not older
than x. That is, if xRy, then y Rx. The relation R is transitive because if person x is older than
person y and y is older than person z, then x is older than z. That is, if xRy and yRz, then xRz.
However, R is not reflexive, because no person is older than himself or herself. That is, xRx
for all people x. It follows that R is not a partial ordering.
Unit 1: Introduction to POSET 15
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
SA3: Determine whether the posets represented by each of the Hasse diagrams in Figure
have a greatest element and a least element.
Solution:
The least element of the poset with Hasse diagram (a) is a. This poset has no greatest
element. The poset with Hasse diagram (b) has neither a least nor a greatest element. The
poset with Hasse diagram (c) has no least element. Its greatest element is d. The poset with
Hasse diagram (d) has least element a and greatest element d.
SA4: In the following cases consider the partial order of divisibility on the set A. Draw the
Hasse diagram of poset and determine whether the poset is totally orderd or not
i) A = {1,2,3,5,6,10,15,30} [positive divisors of 30] and ii) A = {2,4,8,16,32}
Solution
Unit 1: Introduction to POSET 16
Discrete Mathematics and Graph Theory Manipal University Jaipur (MUJ)
By examining the above Hasse diagrams we find that the given relation is totally ordered in
case (ii) as it is evident that every member of 𝐴 divies each one of the succeeding members
of 𝐴. But is not totally ordered in case (i)
6. SUMMARY
This chapter includes concepts of Relations and its types. Here we discussed about reflexive,
antisymmetric and transitive relation which are constitute the partial order or POSET. Also
we discussed about Hasse diagram to represent the POSET along with its Properties.
7. REFERENCES
• Ralph P. Grimaldi (2019) Discrete and Combinatorial Mathematics: An Applied
Introduction (5ed.) Pearson Publication.
• Kenneth H. Rosen (2012) Discrete Mathematics and Its Applications (7 th Edition)
McGraw-Hill Publication.
• Dr. DSC (2016) Discrete Mathematical Structures (5th Edition), PRISM publication.
• https://www.geeksforgeeks.org/elements-of-poset/
Unit 1: Introduction to POSET 17
