Equivalence relation on a set

Question

I need to find the smallest equivalence relation on the following set: $\{a,b,c,d,e\}$ that contains the relation $\{(a,b),(a,c),(d,e)\}$.

Answer 1

Here is an outline of how I would approach the problem.

Let $R$ be the smallest such equivalence relation. Then $R$ must contain the three pairs you listed but $R$ must also be reflexive, symmetric and transitive.

Reflexive means that $(x,x) \in R$ for every $x \in \{a,b,c,d,e\}$. This gives 5 pairs that we need to add to $R$.

Symmetric means that whenever $(x,y) \in R$, $(y,x)$ is also in $R$. This gives us three more pairs to add to $R$.

Transitive means that if $(x,y),(y,z) \in R$, then $(x,z) \in R$. To fulfill this condition we need to add two more pairs to $R$.

Once you have done that, it is time to check that $R$ is indeed an equivalence relation. Next you should check that if you removed any of the pairs i $R$ would no longer be an equivalence relation and hence $R$ is the smallest such equivalence relation.

Answer 2

How about $a\equiv b\equiv c$ and $d\equiv e$?

So that you get $2$ classes: $\{a,b,c\}$ and $\{d,e\}$.

Note that then $a\equiv b$, $a\equiv c$ and $d\equiv e$ as required. About the only thing we need additionally is that $b\equiv c$ (this follows from transitivity, since $a$ is equivalent to both...).