# Finding the smallest relation that is reflexive, transitive, and symmetric

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?

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.
• 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? – Dimitri Nov 23 '13 at 3:29
• $(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. – Annisar Nov 23 '13 at 3:31