Smallest relation for reflexive, symmetry and transitivity

1.9k Views Asked by At

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.

1

There are 1 best solutions below

6
On BEST ANSWER

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