Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.... ...

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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