I'm preparing for an exam in discrete mathematics and found the following question in my course materials.
Let c be the equivalence relation generated by $\{(6,3), (0,2), (2,1), (4,9), (8,3), (1,7)\}$ on [0,9]. Determine $[7]_c$.
I know how to determine $[7]_c$ once I have the equivalence relation. But how do I get the equivalence relation? What does this generated mean? I don't get it. Could you please give me an hint?
If one is given a subset $S \subset A \times A$, then there is a 'smallest' equivalence relation $\sim$ such that if $(a,b) \in S$, then $a \sim b$. The resulting equivalence relation is called the equivalence relation generated by $S$. By smallest, I mean finest.
First, the relation $\sim_* $ defined by $a \sim_* b$ iff $a,b \in A$ is an equivalence class that is compatible with $S$.
Now suppose $E=\{ \sim_\alpha\}_\alpha$ is a collection of equivalence relations on $A \times A$, then we can define the relation $\sim_E$ by $a \sim_E b$ iff $a \sim_\alpha b$ for all $\alpha$. (Note that $\sim_* \in E$ so $E$ is non empty.)
It is easy to establish that this is an equivalence relation.
So, let $E = \{ \sim | \sim \text{ is compatible with } S \}$ and let $\sim_E$ be the relation as defined above. Then $\sim_E$ is the smallest or finest equivalence relation that is compatible with $S$.
One way of generating the equivalence relation for a finite $A$ is to start with a graph that has vertices $A$ and add an undirected edge for each pair $(a,b) \in S$. Now compute the transitive closure of the graph and read off the equivalence classes (the connected subsets).
So, one starts with \begin{eqnarray} (6,3), (8,3) & &\\ (0,2), (2,1), (1,7)& & \\ (4,9) & & \end{eqnarray} from which we can read off the equivalence classes $\{ 3,8,6 \}$, $\{ 0,1,2,7 \}$, $\{4,9\}$.