Answer to Question #259858 in Discrete Mathematics for Mehedi

Question

4. Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.

a) {(0, 0), (1, 1), (2, 2), (3, 3)}

b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}

5. Which relation on the set {1, 2, 3, 4} is an equivalence relation and contain {(1, 2), (2, 3), (2, 4), (3, 1)}.

6. Find the transitive closures of the relation {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}

on the set {1, 2, 3,,4}.

Answer 1

Relation R on the set M is called the relation of equivalence, if:

• R is reflexive ($\forall x\in M:xRx)$
• R is symmetric ($\forall x,y\in R: xRy\to yRx)$
• R is transitive $(\forall x,y,z\in M:(xRy\land yRz)\to xRz)$

M = {0, 1, 2, 3}

a) R = {(0, 0), (1, 1), (2, 2), (3, 3)}

All of the 3 conditions of equivalence relation are met, R is an equivalence relation

b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

There is no element (1,1) in R, so R is non-reflexive, so R is not an equivalence relation

c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

All of the 3 conditions of equivalence relation are met, R is an equivalence relation

d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

R contains pairs (1, 3) and (3, 2), but doesn't contain pair (1, 2), which means R is non-transitive, so R is a non-equivalence relation

e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}

R contains pair (1, 2) but doesn't contain pair (2, 1), which means R i non-symmetric, so R is a non-equivalence relation

5. Which relation on the set {1, 2, 3, 4} is an equivalence relation and contain {(1, 2), (2, 3), (2, 4), (3, 1)}.

If R is an equivalence relation, then it is reflexive, then it certainly must contain (1, 1), (2, 2), (3, 3), (4, 4). So, now we must find what pairs should be added to R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (2, 4), (3, 1)} to make it symmetric and transitive. Adding pairs {(2, 1), (3, 2), (4, 2), (1, 3)} will make the relation symmetric. Now we have

R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (2, 4), (3, 1), (2, 1), (3, 2), (4, 2), (1, 3)}. Now we should add pairs {(3, 4), (4, 3)} to make it transitive and the add (1, 4) to make it transitive again.

R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (2, 4), (3, 1), (2, 1), (3, 2), (4, 2), (1, 3), (3, 4), (4, 3), (1,4)} is the sought relation

6. Find the transitive closures of the relation {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)} on the set {1, 2, 3, 4}.

Transitive closure of R is relation R*, which is the least transitive relation contains R. So, we should find the least amount of pairs that if we add them to the R it will make R transitive

Those pairs are {(1, 2), (1, 3), (2, 4), (2, 2), (3,3), (4, 1), (4, 3), (4, 4)}

so, relation R* = {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2), (1, 2), (1, 3), (2, 4), (2, 2), (3,3), (4, 1), (4, 3), (4, 4)} is a transitive closure of R on the set {1, 2, 3, 4}