PubTeX output 2020.08.14:1558
4. Prove that R is a partial order in X iff R 1 is a partial order in X.
(i) R is reflexive (Definition of reflexivity)
�1 (Definition of R 1)
R 1 is reflexive (Definition of reflexivity)
(ii) R is antisymmetric
(Definition of antisymmetricity)
�1 �1
(Definition of R 1)
�1 �1 (E9)
R 1 is antisymmetric (Definition of transitivity)
(iii) R is transitive (Definition of transitivity)
�1 �1 �1
(Definition of R 1)
�1 �1 �1 (E9)
R 1 is transitive. (Definition of transitivity)
Hence, R is a partial order in X iff R 1 is a partial order in X.
5.8 Exercises
1. Let R be a relation from to such that iff . Write R as a
set of ordered pairs.
2. Prove that if R is a symmetric relation, then .
3. Let R and S be relations in a set A. Prove or disprove the following:
(a) If R and S are asymmetric, then (i) is a symmetric relation; (ii) is a symmetric relation.
(b) If R and S are antisymmetric, then (i) is an antisymmetric relation; (ii) is an antisymmetric
relation.
4. Let and be two equivalence relations in a set A. Prove that is an equivalence relation in A,
but need not be an equivalence relation.
5. Let and be non-empty sets and . Prove that the set
is a partition of X.
6. Use Theorem 5.3.6 to prove that the following relation R is an equivalence relation.
Let R+ be the set of nonnegative real numbers and is the largest integer less than or equal to x. The
relation R is defined as:
7. Let R be a symmetric and transitive relation in a set A. Prove that if for every , there exists
such that , then R is an equivalence relation. Show that the conclusion is false if symmetricity is
replaced by reflexivity.
8. Let Z be the set of integers and R is a relation in Z such that
.
Prove that R is an equivalence relation.
9. Let N be the set of all positive integers and R is a relation in N such that
.
Prove that R is an equivalence relation.
143
Describe the equivalence class . List all the integers in that fall within the range from 0 to
50, inclusive.
10. Let R be an equivalence relation in X and R’ be an equivalence relation in Y. Let iff
. Prove that S is an equivalence relation in X Y.
11. Let be a partial order and be its corresponding strict order. Prove that:
(a) if and , then .
(b) if and , then .
12. Let R be a reflexive and transitive relation in X. Let S be a relation in X such that
.
(a) Prove that S is an equivalence relation.
(b) Let be a relation in such that . Prove that is a partial order.
13. Let and be partially ordered sets. Let iff . Prove that
is a partially ordered set.
14. Let and be partitions of X. is finer than , denoted by , iff . Prove
that is a partial order in the set of all partitions of X.
15. Let be a partially ordered set. Prove that if X has two distinct minimal elements, then it has no
smallest element.
16. Let R be a relation in X. Prove that is the smallest symmetric relation including R and that
is the largest symmetric relation included in R.
17. Let R be a relation from X to Y. Let and be the equality relation in X and Y, respectively. Prove that
and .
18. Let R be a relation in X. Prove that:
(a) R is reflexive iff
(b) R is irreflexive iff
(c) R is symmetric iff
(d) R is antisymmetric iff
(e) R is transitive iff .
19. Let be a strict order in X. Prove that .
20. Let R be a relation in a set X. If , then R is reflexive R is not asymmetric.
144