5
$\begingroup$

Find the smallest relation containing the relation

$$R=\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$$ that is

  • Reflexive and transitive

  • Reflexive, transitive and symmetric

Well this seems easy to do. However, I'm not sure whether the question is meant to find the (for the first part) the reflexive and transitive closures, or is it something else?

If it's a closure case, then the first part would be: $$R=\{ (1,2),(2,1),(2,3),(3,4),(4,1),(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2)\}$$

But this doesn't seem right for some reason and just wanted to clarify what the question is asking.

$\endgroup$
5
  • 1
    $\begingroup$ Your interpretation of the question is correct. The $R$ you propose isn't correct: $(1,3)\in R\land (3,4)\in R$, but $(1,4)\not \in R$. You shouldn't use the same letter for the closure. You're using $R$ with two different meanings. $\endgroup$
    – Git Gud
    Commented Nov 30, 2013 at 23:52
  • $\begingroup$ Great! I guess the "smallest" doesn't seem so small after all. $\endgroup$
    – Dimitri
    Commented Nov 30, 2013 at 23:54
  • $\begingroup$ That interpretation looks right to me. Also, in the future, you can edit your previous, identical question: math.stackexchange.com/questions/577802/… $\endgroup$
    – Henry Swanson
    Commented Nov 30, 2013 at 23:55
  • $\begingroup$ If the relation is 'connected' in that you can reach every 'node' from every other 'node', then if the relation is transitive, it must contain every pair. $\endgroup$
    – copper.hat
    Commented Nov 30, 2013 at 23:57
  • $\begingroup$ @HenrySwanson Yes, I knew there was a previous question related to this but was more concerned about the definitions of the properties. I just wasn't sure how to "follow up" on the same question though.. $\endgroup$
    – Dimitri
    Commented Dec 1, 2013 at 0:00

1 Answer 1

Reset to default
4
$\begingroup$

You’re missing $\langle 1,4\rangle,\langle 3,2\rangle$, and $\langle 4,3\rangle$; the first is required by $\langle 1,2\rangle$ and $\langle 2,4\rangle$, the second by $\langle 3,4\rangle$ and $\langle 4,2\rangle$, and the last by $\langle 4,1\rangle$ and $\langle 1,3\rangle$, for instance. The reflexive, transitive closure of $R$ is in fact $\{1,2,3,4\}\times\{1,2,3,4\}$. (And you should not call it $R$, as that name is already in use for the original relation.)

$\endgroup$
6
  • $\begingroup$ Yes, I keep forgetting to check that for every new ordered pair I add to my relation, I must also check for transitivity and symmetry in there as well. $\endgroup$
    – Dimitri
    Commented Dec 1, 2013 at 0:05
  • $\begingroup$ @Dimitri: Note that in this particular case symmetry comes for free with transitivity. $\endgroup$
    – Brian M. Scott
    Commented Dec 1, 2013 at 0:07
  • $\begingroup$ By the looks of it you're right. So does the order matter in cases like these? It seems as though transitivity should be done the same time as the reflexive. Or am I just over-thinking this? $\endgroup$
    – Dimitri
    Commented Dec 1, 2013 at 0:11
  • $\begingroup$ @Dimitri: When you compute the reflexive, transitive closure, it makes no difference whether you add the pairs $\langle x,x\rangle$ first or last. $\endgroup$
    – Brian M. Scott
    Commented Dec 1, 2013 at 0:13
  • $\begingroup$ Yes, very true. Thank you once again. $\endgroup$
    – Dimitri
    Commented Dec 1, 2013 at 0:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .