Math151 Discrete Mathematics (4.

3) Partial Orderings By: Malek Zein AL-Abidin

King Saud University

College of Science
Department of Mathematics

151 Math Exercises

(4.3)

Partial Orderings

Malek Zein AL-Abidin

‫ه‬
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Partial Orderings

DEFINITION 1 A relation R on a non empty set S is called a partial ordering or partial order if it
is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a
partially ordered set, or poset, and is denoted by (S,R). Members of S are called elements of the
poset.

DEFINITION 2 Let a and b be in the set S. Assume (S, ) is a poset. We say that and are
comparable if either a R b or b R a. When a and b are elements of S such that neither a R b nor
b R a, a and b are called incomparable.

DEFINITION 3 If (S, ) is a poset and every two elements of S are comparable, S is called a
totally ordered or linearly ordered set, and is called a total order or a linear order. A totally
ordered set is also called a chain.

Hasse Diagrams
If (S, ) is a partially ordered set, we can represent this group in a schematic format called
(Hasse diagram), where S is a finite set, as follows:
We represent each element of S in a small circle and if we place above and
connect between them by a straight line segment, ignoring the cut of the lines we
automatically get by means of a transitive property.
For example, if ( )∧ ( ) and there is no such that ,also there is
no y such that , then we get a straight line segment between and and
between and but we do not get between and .

Example 1. Let R be a relation defined on the set :

(i) Show that R is a partial ordering relation (poset) on .
(ii) In case R is defined on , is R still a partial ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation R on the set

(iv) Decide whether R is totally ordering relation on , why?

(v) In case R is defined on , is R a total ordering relation on B,
why?
(vi) Draw the Hasse diagram representing the totally ordering relation R on the set
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Solution: (i)
1- .

2-

3-

is , and is partial ordering .

(ii) ∧ is not
is not a partial ordering on .

(iii)

Hasse diagram of
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

(iv) ∧ is not a total

ordering

(v) , or
is comparable is totally ordered.

(iv)

Hasse diagram of R ( chain)

Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Example 2. Let R be a relation defined on the set :

(i) Show that R is a partial ordering relation on .

(ii) Decide whether R is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation R on the set

(i)
(1) is

(2)

(3)

R
, and

is partial ordering relation .

(ii) ∧ is not totally
ordering relation .
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Hasse diagram of R

Example 3. Draw the Hasse diagram representing the partial ordering relation

on the set

2 3

1
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Example 4. Let be a partial ordering relation defined on the set 𝒫 where :

Draw the Hasse diagram representing the partial ordering on the .

Solution : 𝒫

The Hasse Diagram

of (P ({a, b, c}),⊆
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

Exercises
1. Let R be a relation defined on the set

(i) Show that R is a partial ordering relation on .

(ii) Decide whether R is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation R
on the set
Solution :
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

2. Let R be a relation defined on the set :

(i) Show that R is a partial ordering relation on .

(ii) Decide whether R is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation R on
the set .
Solution : (i)
1-

2-

3-

, and

is partial ordering relation .

(ii) ∧

is not totally ordering relation .

Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

(iv)

Hasse diagram of R
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

3. Let be a relation defined on the set :

(i) List all ordered pairs of T .

(ii) Represent the relation T by diagram .
(iii) Show that T is a partial ordering relation on .
(iv) Decide whether T is totally ordering relation on , why?
(v) Draw the Hasse diagram representing the partial ordering relation T on the set .
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

4. Let be a relation defined on the set :

(i) Show that is a partial ordering relation on .

(ii) Decide whether is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation
on the set .
Solution: (i)
1-

2-
∧

3-
∧

:
is , and
is partial ordering relation .
(ii) ∧
is not totally ordering relation .

(iii)

0 1

2 3

Hasse diagram of T
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

5. Let T be a relation defined on the set :

(i) Show that T is a partial ordering relation on .

(ii) Decide whether T is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation T on
the set .
Solution : (i)
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

6. Let T be a relation defined on the set :

(i) Show that T is a partial ordering relation on .

(ii) Decide whether T is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation T on
the set .
Solution : (i)
1-
2-
∧

(by substitution )

3-
∧

(by substitution )

is , and
is partial ordering relation on .
(ii) ∧
is not totally ordering relation .

(iii)

Hasse diagram of T
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

7. Let be a relation defined on the set

(i) Represent the relation T by diagram .

(ii) Show that T is a partial ordering relation on .
(iii) Decide whether T is totally ordering relation on , why?
(iv) Draw the Hasse diagram representing the partial ordering relation T
on the set .
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

8. Let be a relation defined on the set :

(i) Show that is a partial ordering relation on .

(ii) Decide whether is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation
on the set .
Solution: (i)
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

9. Let T be a partial ordering relation defined on the set shown in

the given Hasse diagram
(i) List all ordered pairs of T .
(ii) Decide whether T is totally ordering relation on , why?

o n

p
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

10. Let S be a partial ordering relation defined on the set

shown in the given Hasse diagram

(i) List all ordered pairs of S .

(ii) Decide whether S is totally ordering relation on , why?

Solution:

is not totally ordering relation .

.
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

11. Let be a relation defined on the set :

(i) Show that is a partial ordering relation on .

(ii) Decide whether is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation
on the set .
Solution: (i)
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

12. Let T be a relation defined on the set :

(i) Show that T is a partial ordering relation on .

(ii) Decide whether T is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation T on
the set .
Solution : (i)
1-

2-
∧

3-
∧

is , and
is partial ordering relation on .

1 (ii) ∧

2 3 (iii)

6 5
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

13. Let T be a relation defined on the set

(i) Show that T is a partial ordering relation on .

(ii) Decide whether T is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation T on
the set .
Solution : (i)

:
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

14. Let R be a relation defined on the set :

(i) Show that R is a partial ordering relation (poset) on .
(ii) In case R is defined on , decide whether R a partial ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation R on the set

(iv) Decide whether R is totally ordering relation on , why?

Solution: (i)
1-
2-
∧

3-
∧

is , and
is partial ordering relation on .
(ii)
∧
R is not partial ordering relation on
(iii)
8
9 6 4

3 2

∧
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

15. Let be a relation defined on the set

. Decide whether T is reflexive , symmetric , antisymmetric ,
transitive , equivalence , partial ordering relation . Why?

Solution:
1-

2- ∧

3- ∧

4- ∧

#
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

16. Let be a relation defined on the set

. Decide whether R is reflexive , symmetric , antisymmetric ,
transitive , equivalence , partial ordering , totally ordering relation . Why?

Solution:
1-

2- ∧ ∧

∧ ∧

3- ∧ , also same for

4- ∧ , also same for

5-

6-

7- ∧

#
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

17. Let be a relation defined on the set .

Decide whether is reflexive , symmetric , antisymmetric ,
transitive , equivalence , partial ordering , totally ordering relation . Why?
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

18. Let R be a relation defined on the set

Decide whether R is reflexive , symmetric , antisymmetric , transitive ,

equivalence , partial ordering relation . Why?

Solution :

1-

2-

3- ∧

but .

4- ∧

But .

Finally , .

#
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

19. Let be a relation defined on the

set . Decide whether T is reflexive , symmetric ,

antisymmetric ,transitive . Why?

Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

20. Let R be a relation defined on the set

(i) List all the ordered pairs of R .

(ii) Represent R in a diagram .

(iii) Decide whether R is reflexive , symmetric , antisymmetric ,

transitive . Why?
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

21. Let R be a relation defined on the set

Decide whether R is reflexive , symmetric , antisymmetric , transitive . Why?

Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

22. Suppose T is a relation defined on the integers set

Decide whether the relation T is reflexive, symmetric, antisymmetric,

and/or transitive.
Solution:
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

23. Let T be a partial ordering relation defined on the set

shown in the given Hasse diagram

(i) List all ordered pairs of T .

(ii) Decide whether T is totally ordering relation on , why?
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

24. Let be a relation defined on the set :

(i) Show that is a partial ordering relation on .

(ii) Decide whether is totally ordering relation on , why?
(iii) Draw the Hasse diagram representing the partial ordering relation on
the set
Math151 Discrete Mathematics (4.3) Partial Orderings By: Malek Zein AL-Abidin

25. Let T be a relation defined on the set :

Decide whether the relation T is reflexive, symmetric, antisymmetric,
and/or transitive.
Solution: