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

Question

$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

My answers are

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?

Answer 1

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\}$$

is your quotient set - your set of equivalence classes.

---

...granted, this question is a bit old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.