CmSc 175 Discrete Mathematics
Problems on Equivalence Relations, Partial and Total Orders
1. Let X = {1,2,3,4,…, 10}. Define a relation R on X x X :
R = { ((a, b), (c, d)) | a + d = b + c}
Show that R is an equivalence relation on X x X
2. Let X = {1,2,3,4,…, 10}. Define a relation R on X x X :
R = { ((a, b), (c, d)) | ad = bc}
Show that R is an equivalence relation on X x X
3. Let f: A ® B. Show that the following relation R is an equivalence relation on A: (a,b) Î R iff f(a) = f(b).
4. Let R Í A x A be a binary relation as defined below. In which cases R is a partial order? A total order?
a. A = the positive integers; (a,b) Î R iff b is divisible by a
b. A = N x N; ((a,b),(c,d) ) Î R iff a £ c or b £ d.
c. A = N; (a,b) Î R iff b = a or b = a+1
d. A is the set of all English words; (a,b) Î R iff a is no longer than b
e. A is the set of all English words; (a,b) Î R iff a is the same as b or occurs more frequently than b in our textbook.
5. Let R1 and R2 be any two equivalence relations on the same set A. Examine the properties of R1 Ç R2 and determine if it is a relation of equivalence or not.
6. Let R1 and R2 be any two equivalence relations on the same set A. Examine the properties of R1 È R2 and determine if it is a relation of equivalence or not.
7. Let R1 and R2 be any two equivalence relations on the same set A. Examine the properties of R1 - R2 and determine if it is a relation of equivalence or not.
8. Let R1 and R2 be any two partial orders on the same set A. Show that R1 Ç R2 is a partial order
9.
a. Prove that if S is any collection of sets, then RS = {(A,B): A, B Î S and A Í B} is a partial order
b. Let S = 2{1,2,3}. Draw a directed graph representing the partial order RS defined in (a). Which is the minimal element of RS?
10. Let S be any set, and let P be the set of all partitions of S. Let R be the binary relation on P such that (P1, P2) Î R iff for every S1 Î P1 there is an S2 Î P2 such that S1Í S2; if (P1, P2) Î R, we say that P1 refines P2.
Show that R is a partial order on P.
Suppose that P were an arbitrary collection of subsets of 2S, which need not be partitions of S. Would R necessarily be a partial order?
1