Suppose I have the following relation $$R = \{(1,1), (2,3), (3,1)\}$$ To make it reflexive we add the following missing pairs: $$ \{(2,2), (3,3)\}$$ Now I wonder how to find the reflexive transitive closure of that relation?

  • $\begingroup$ add ${(1,2),(2,1)}$ $\endgroup$ – Guy Mar 12 '14 at 12:06
  • $\begingroup$ Do you mean that $$R = \{(1,1),(2,2),(3,3), (2,3), (3,1),(1,2),(2,1) \}$$ ? $\endgroup$ – Bledi Boss Mar 12 '14 at 12:08
  • $\begingroup$ Yes. I believe that is reflexive transitive, yes? I don't remember the definition of transitive though. $\endgroup$ – Guy Mar 12 '14 at 12:10
  • $\begingroup$ I'm supposing that transitive must implies that from (1,2) and (2,3), (1,3) follows ... $\endgroup$ – Mauro ALLEGRANZA Mar 12 '14 at 12:13

Reflexive and transitive are two different things.
Transitive means: if $a \sim b$ and $b \sim c$ then $a \sim c$. While reflexive means that $a\sim a$ in your realtion.

You have $R = \{(1,1), (2,3), (3,1)\}$ and you want it to be closed under transitivity . Since $2\sim 3$ and $3\sim 1$ you must have $2\sim 1$ so you add $(2,1)$.


Suppose that $R$ is a relation on a set $A$. The reflexive transitive closure of $R$ is the smallest relation $S$ on $A$ such that:


$S$ is reflexive;

and $S$ is transitive.

  • $\begingroup$ "Reflexive and transitive are two different things" - that's true. But there exist also something called 'reflexive transitive closure' and that's what I am looking for $\endgroup$ – Bledi Boss Mar 12 '14 at 12:25
  • $\begingroup$ I edited my answer. you can see that adding $(2,1)$ does the job. $\endgroup$ – Spock Mar 12 '14 at 12:59
  • $\begingroup$ I got it now :) thanks $\endgroup$ – Bledi Boss Mar 12 '14 at 13:03

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.