2

I've been looking at a past paper with solutions, and I can't quite make sense of the answers given here (which is odd considering I get these questions right every time on the online practice tests), where am I going wrong with this?

Consider the set A = {a,b,c,d,e,f} and the relation defined on A X A by setting R = {(a,b),(c,d),(d,c),(b,c),(b,f),(f,a),(b,a),(b,b)}

List the elements of A X A that must be added to R to make up its reflexive closure.

Solution: {(a,a),(c,c),(d,d),(e,e),(f,f)

Does it have to include ones that weren't even included in R, such as e? If so, I guess this one is an easy one to figure out.

List the elements of A X A that must be added to R to make up its symmetric closure.

Solution: {(a,f),(f,b),(c,b),(c,a),(e,a)}

This one I can't make sense of, I'd have thought the answer would be {(c,b),(f,b),(a,f)}. I don't see where (a,c) comes from when there's no (c,a) present, and I especially don't see where the (e,a) comes from when no e is present in R.

List the elements of A X A that must be added to R to make up its transitive closure.

Solution: {(f,b),(b,d),(a,a),(c,c),(d,d),(f,f)}

I really can't make sense of this answer at all.

Would anyone be able to explain to me why these answers are true?

Dalekcaan1963
  • 181

1 Answers1

1

You need to carefully read the definitions of reflexive, symmetric, and transitive so you can apply them. Reflexive says that every element is related to itself, so you need all the pairs of the form $(x,x)$ Nothing else matters for this. I agree with your answer for symmetric. For transitive, the definition is that if we have $(x,y)$ and $(y,z)$ we must have $(x,z)$ so since we have $(c,d)$ and $(d,c)$ we must have $(c,c)$ and $(d,d)$. Similarly, since we have $(b,c)$ and $(c,d)$ we must have $(b,d)$ Can you explain why we need $(f,b)$?

Ross Millikan
  • 374,822
  • Wouldn't (f,b) require (f,e),(e,d),(d,c),(c,b)? Also, shouldn't there be an (a,d) there since we have (a,b),(b,c)(c,d)?

    Are you sure my answer was correct for the symmetric one? The other was given as the official answer on the previous paper, but it wouldn't be the first time they've gotten something like this wrong...

     – Dalekcaan1963 Jun 03 '15 at 05:07
  • For symmetric I can't see why we need $(c,a),(e,c)$. For transitive I wasn't saying that adding $(f,b)$ was enough, just asking if you saw why it was required. But there is no reason you need $(f,e)$. As you say, $e$ is not mentioned in the original $R$. $(d,c)$ is already present. I don't see why you need $(c,b)$ (remember you don't have the ones needed fo reflexive and symmetric here) but it is easy to overlook things, so if you have a proof please show it. – Ross Millikan Jun 03 '15 at 05:16
  • I still can't see why we need (f,b). If transitive is, for example, adding (a,c) when there's (a,b) and (b,c), I don't see which parts make (f,b) necessary without (f,e),(e,d),(d,c),(c,b).

    Also, would (a,d) be correct here? It seems to follow that (a,d) and perhaps even (a,c) should count, but they aren't given as potential answers.

     – Dalekcaan1963 Jun 03 '15 at 05:24
  • @GeorgeDolley $f, R, a, R, b$ so $f, R, b$, and yes $a, R, b, R, c, R, d$ implies $a, R, c$ and $a, R, d$ – Mario Carneiro Jun 03 '15 at 05:27
  • So shouldn't there also be (f,c) and (f,d) since there's (f,a),(a,b),(b,c) and (c,d), or does it not carry on further than (f,a), (a,b)? – Dalekcaan1963 Jun 03 '15 at 05:32
  • @GeorgeDolley By my calculations I get $${(a,a),(a,c),(a,d),(a,f),(b,d),(c,c),(d,d),(f,b),(f,c),(f,d),(f,f)}$$ as the full list of additions. – Mario Carneiro Jun 03 '15 at 05:36
  • I did it using the same method and got the same answer, thanks :) To make sure I have the right idea, would R = (a,b),(b,c),(c,d),(d,e) require (a,c),(a,d),(a,e),(b,d),(b,e),(c,e) to be transitive? – Dalekcaan1963 Jun 03 '15 at 05:46
  • @GeorgeDolley Yes, that's right. Recall that the transitive closure is the smallest relation that contains the given elements and is itself transitive; this means that you have to repeat the adding process until you don't get anything new. – Mario Carneiro Jun 03 '15 at 05:53
  • Awesome, I understand it now, thanks so much :D – Dalekcaan1963 Jun 03 '15 at 05:55