Listing all equivalence relations

Question

I am unsure how to find the all the equivalence relations. I know that a relation is an equivalence relation if it is reflexive, symmetric, and transitive. However I'm still uncertain how to find them all.

Answer 1

Let us recall the definition of an equivalence relation $R$ on a set $S$. It means the following hold:

• Reflexivity: for all $s \in S$, $(s,s) \in R$ (emphasis on for all)
• Symmetry: Whenever $(a,b) \in R$, so is $(b,a)$
• Transitivity: Whenever $(a,b),(b,c) \in R$, so is $(a,c)$

Bear in mind that the first condition requires that $(a,a),(b,b),(c,c) \in R$ for all equivalence relations $R$, so the "minimal size" relation $R$ is

$$R = \{ (a,a),(b,b),(c,c) \}$$

unlike what you're suggesting in the comments elsewhere.

---

It might be easiest to visualize this exercise through a table:

$$\begin{array}{|c|c|c|c|} \hline & a & b & c \\ \hline a & & & \\ \hline b & & & \\ \hline c & & & \\ \hline \end{array}$$

Put a mark in a given square. Then it will mean that $(x,y)$ is in the relation $R$, where $x$ is the element from the left and $y$ the element from above.

To be an equivalence relation, we need to be reflexive, transitive, and symmetric. Reflexive would require a mark on all elements of the diagonal as so:

$$\begin{array}{|c|c|c|c|} \hline & a & b & c \\ \hline a & X & & \\ \hline b & & X & \\ \hline c & & & X \\ \hline \end{array}$$

What else? Well, this already gives one equivalence relation, trivially. Suppose we add more pairs to $R$ that are non-diagonal entries. Then we would have to add the pair that is flipped across the diagonal, sort of like taking the transpose of a matrix. That means if you mark $(a,b)$ you have to mark $(b,a)$ too, and vice versa.

Just be sure to mark off further pairs that transitivity also has to imply!

---

Transitivity also has a condition related to this table method, but we instead have to use a condition that is slightly more formal and perhaps harder to visualize. Relations can be envisioned as matrices, where the rows and columns represent the elements, $0$'s are in the unrelated entries, and $1$ in the related entries. That is, for example,

$$\begin{array}{|c|c|c|c|} \hline & a & b & c \\ \hline a & X & & \\ \hline b & & X & \\ \hline c & & & X \\ \hline \end{array} \implies R = \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} \right]$$

In this case, the conditions are

• Reflexivity: All entries in the diagonal of $R$ are nonzero.
• Symmetry: $R = R^T$.
• Transitivity: Find $R^2$. If the nonzero entries in $R^2$ and those in $R$ are in the same position, we have transitivity.

---

Finally, as pointed out, just be sure you enumerate all of the equivalence relations. You only found one, but as you have already seen above, there's at least one you forgot.

Answer 2

That is one of the equivalence relations on the set: the relation in which everything is equivalent to everything else. There's another in which the only pairs are $(x,x)$: each element is related only to itself.

To find all the others, think about or look up the connection between equivalence relations and partitions. Here's one reference:

https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/6%3A_Relations/6.3%3A_Equivalence_Relations_and_Partitions