Question

Find the smallest equivalence relation on {1, 2, 3} that contains (1, 2) and (2, 3).

Answer 1

Answer on Question #37628 – Math – Discrete Mathematics

Question. Find the smallest equivalence relation on $A = \{1,2,3\}$ that contains $(1,2)$ and $(2,3)$.

Solution. By definition a relation $R$ on a set $A$ is an arbitrary subset of $A \times A$. A relation $R$ is called equivalence if

(1) $R$ is reflexive, that is $(x,x) \in R$ for all $x \in A$;

(2) $R$ is symmetric, that is if $(x,y) \in R$, then $(y,x) \in R$ for all $x,y \in A$;

(3) $R$ is transitive, that is if $(x,y), (y,z) \in R$, then $(x,z) \in R$ as well for all $x,y,z \in A$.

Suppose $R \subset A \times A$ is an equivalence relation on $A = \{1,2,3\}$ containing $(1,2)$ and $(2,3)$. We claim that then $R = A \times A$.

Indeed, since $R$ is reflexive, $(1,1)$, $(2,2)$, and $(3,3) \in R$.

As $R$ is transitive, and $(1,2), (2,3) \in R$, we obtain that $(1,3) \in R$ as well.

Since $R$ is symmetric, we get that then $(2,1)$, $(3,2)$ and $(3,1) \in R$ as well.

Thus we see that each element $(i,j) \in A \times A$ belongs to $R$, and so $R = A \times A$.

Thus $R = A \times A$ is a unique equivalence relation on $A$ containing $(1,2)$ and $(2,3)$.

Answer. $R = A \times A$.