# 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?

## 1 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.

• 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
• I understand, thank you. – Dimitri Nov 23 '13 at 3:40