# Given a relation, how do I find the smallest symmetric/transitive relation containing it, and the smallest relation with two equivalence classes?

$$R$$ is relation on $$A = \{1,2,3,4\}$$

$$R = \{(1,2), (1,4),(4,1), (3,3)\}$$

I need to find $$S$$, the smallest relation that contains $$R$$ that is

1. symmetric and transitive
2. $$S$$ is equivalence relation on $$A$$ so that $$S$$ has exactly two equivalence class

1. $$S = \{(1,2),(1,4),(4,1),(3,3),(2,1),(2,4),(1,1),(4,4)\}$$

2. $$S = \{(1,2),(2,1),(2,3),(3,4),(4,1),(1,4),(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2)\}$$

but there are more than exactly two equivalence classes. How can I change that?

• It is bad form to put phrases like "is my answer correct?", or "Please help me," or "Can't figure this out," etc. in a title. Can you see why? Apr 13, 2020 at 21:31
• Your answer 1. is not transitive... For example, you have $(1,2) \in S$ and $(2,1) \in S$, but do not have $(1,1) \in S$. Apr 13, 2020 at 21:31
• @AntonVrdoljak is it ok now ? or (4,4) ∈ S too ?
– Dana
Apr 13, 2020 at 21:35
• To @Dana : True, $(4, 4) \in S$ too (for answer 1.). Apr 13, 2020 at 21:47
• @Shaun changed the title , is that better ?
– Dana
Apr 14, 2020 at 7:05

Observe that, if we represent your initial relation $$R$$ as a directed graph (where $$x$$ points to $$y$$ iff $$(x,y) \in R$$), then we have this graph: In graphs like these, certain properties can be intuitively and visually observed:

• Reflexivity appears if every node points to itself.
• Symmetry happens if, whenever $$x$$ points to $$y$$ (and thus a path exists), then $$y$$ points to $$x$$ (and thus a path to "backtrack" exists). Basically, there are no "stray," one-way edges - only closed loops.
• Transitivity is visible when, if there exists paths $$x$$ to $$y$$ and $$y$$ to $$z$$, then there is a path $$x$$ to $$z$$. For distinct nodes, then this means that, whenever two sides of a triangle are filled in, the last one is too, though the direction depends on the direction of the other sides in question.
• Your equivalence classes are all of the nodes in each of the disjoint graphs you have. (Two graphs are disjoint if, basically, one is entirely separate from another, totally isolated.)

For your first part, you want the symmetric and transitive closure. We can work each part in turn. To get symmetry, we need to close a loop with $$2 \to 1$$. We then need to use transitivity: $$4 \to 1 \to 2$$ requires $$4 \to 2$$; similarly, $$2 \to 1 \to 4$$ requires $$2 \to 4$$. The relation $$\{(3,3)\}$$ itself is transitive and symmetric, so there's nothing to change there. We thus get the following graph at this stage: However, since $$1 \to 2 \to 1$$, $$2 \to 4 \to 2$$, and $$4 \to 2 \to 4$$, we need arrows from each of $$1,2,4$$ pointing to themselves as well by symmetry. Thus, the final result is This relation is given by our original relation, plus the arrows we added. Thus, the $$S$$ you seek is

\begin{align*} S &= R \cup \{(2,1),(4,2),(2,4),(1,1),(2,2),(4,4)\} \\ &= \Big\{\underbrace{(1,2),(1,4),(4,1),(3,3)}_{\in R},(2,1),(2,4),(1,1),(4,4), \color{red}{(4,2),(2,2)}\Big\} \end{align*}

In red are those you forgot.

To turn $$R$$ into an equivalence relation in the most minimal fashion possible, we can turn it into the reflexive/transitive/symmetric closure of itself. However, notice that the relation previously is, in fact, also reflexive. Thus, the relation given by that is also an equivalence relation.

The nodes of the disjoint graphs are $$1,2,4$$ and $$3$$, and thus each group is an equivalence class. That is,

$$A/S = \Big\{ \{1,2,4\},\{3\} \Big\}$$