1
$\begingroup$

Let R be a relation on a set A. True or False ? If true give a proof else give a counter proof.

A) Let S be a reflexive closure of R, T is the symetric closure of S, U is the transitive closure of T. Thus U is an equivalence relation. True or False.

My answer : False.

$A = \left\{ {a,b,c} \right\}$

Let R be $\left\{ {(a,c) , (b,c)} \right\}$

$S = \left\{ { (a,c), (b,c),(a,a), (b,b), (c,c) } \right\} $ (reflexive)

$T = \left\{ { (a,c), (b,c),(a,a), (b,b), (c,c),(c,a), (c,b) } \right\} $ (symetric)

Since (a,b) is not in my final set, it is not transitive.

Is this right ?

B) Let V be a reflexive closure of R, W is the transitive closure of V, X is the symetric closure of W. Thus X is an equivalence relation. True or False.

My answer : True.

$A = \left\{ {a,b,c} \right\} $

Let R be $\left\{ {(a,c) , (b,c)} \right\}$

$V = \left\{ { (a,c), (b,c),(a,a), (b,b), (c,c) } \right\} $ (reflexive)

$W = \left\{ { (a,c), (b,c),(a,a), (b,b), (c,c), (a,b) } \right\} $ (transitive)

$X = \left\{ { (a,c), (b,c),(a,a), (b,b), (c,c), (a,b), (b,a) (c,a), (c,b) } \right\} $ (symetric )

Not so sure how to finish this one... I would just go and say it works... because it seems to work. haha.... ...

$\endgroup$
1
$\begingroup$

In a) you forgot $U={(a,c),(b,c),(a,a),(b,b),(c,c),(c,a),(c,b),(a,b),(b,a)}$ And this is equivalence. In a, you have reflexivity and transitivity granted. Only you need to check if all relation added by transitivity closure have symetry. And they really have, because if there is path $((x_1,x_2),(x_2,x_3),\dots, (x_{n-1} ,x_{n})$ in S, there is path $((x_{n},x_{n-1}),\dots, (x_{2} ,x_{1})$ thanks to symetry closure and so the transitive cover inserts relation in both ways.I hope it is clear.

b)I do not think this will work try $A=(a,b,c)$ and $R=((a,b),(c,b)$. transitivity cover adds nothing. Symmetry cover adds (c,b) (b,a) but you dont have (a,c) and X is not transitive then

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.