Find the smallest relation containing the relation $\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$ that is:

  1. Reflexive and transitive
  2. Reflexive, symmetric and transitive

Well my first attempt:

  1. Reflexive: $ S_1 = \{ (1,1),(2,2),(3,3),(4,4) \}$
  2. Symmetric: $ S_2=\{ (3,2),(4,3),(1,4) \}$
  3. Transitive: $S_3= ? $Is where I'm stuck.

So that $S_1\cup S_2 \cup S_3 $ would be my equivalence relation?

Also, When you're testing for transitivity, what combinations do we test for? If we take: $(1,2) \land (2,3)\land(3,4) \rightarrow(1,3)$, must it be done for the converse? Starting with $(2,1)$ rather than $(1,2)$. It seems that there are many conbinations of $x,y$ that need to be tested. Is this correct? In fact, is my attempt correct to begin with?


1 Answer 1


It is very important in logic to understand your definition as hard as you can: $$\forall_{x,y,z\in X}\, xRy\wedge yRz\Rightarrow xRz$$ So. That tells us that if we have two elements, let's say, following your example, $(1,2)$ and $(2,3)$, there must be direct connection between $1$ and $3$. Do the same for all possible pairs from $S$, $S_1$ and $S_2$ (where $S$ is your base relation), and you will have your answer. And yes, you may have many elements in your relation after all those changes.

  • $\begingroup$ Right, so taking: $(1,2) \land (2,3)\land(3,4) \rightarrow(1,3)$, then ordered pair $(1,3)$ would need to be added, correct? $\endgroup$
    – Dimitri
    Nov 23, 2013 at 3:29
  • 1
    $\begingroup$ $(1,3)$ and $(1,4)$ to be very accurate, but you have your $(1,4)$ in symmetry, so, yes. Also, it will make things a lot easier if you think of your relation as of directed graph - draw it, and check what more do you need: if you have an edge between A, B and B, C, you need another one between A and C, and this one goes to your $S_3$. Graphs are good for this because you can see all: reflexivity, symmetry and transitivity from them. $\endgroup$
    – Annisar
    Nov 23, 2013 at 3:31
  • $\begingroup$ I understand, thank you. $\endgroup$
    – Dimitri
    Nov 23, 2013 at 3:40

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.