Find the smallest relation containing the relation $\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$ that is:
- Reflexive and transitive
- Reflexive, symmetric and transitive
Well my first attempt:
- Reflexive: $ S_1 = \{ (1,1),(2,2),(3,3),(4,4) \}$
- Symmetric: $ S_2=\{ (3,2),(4,3),(1,4)
\}$ - 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?
Best Answer
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.