Find the smallest equivalence relation containing the pairs (a, b), (a, c), (d, e), and (b, f)

Question

I don't understand. I know I will need to prove if the pairs are transitive, symmetric, and reflective but how do I do it with just letters? I thought numbers are suppose to be given within some sort of set.

Answer 1

$$\newcommand{\X}{\text{X}} \newcommand{\RX}{\color{red}{\text{X}}}$$

Start:

$$\begin{array} {r|c|c|c|c|c|c|} & a & b & c & d & e & f \\ \hline a & ~ & \X & \X & ~ & ~ & ~ \\ \hline b & ~ & ~ & ~ & ~ & ~ & \X \\ \hline c & ~ & ~ & ~ & ~ & ~ & ~ \\ \hline d & ~ & ~ & ~ & ~ & \X & ~ \\ \hline e & ~ & ~ & ~ & ~ & ~ & ~ \\ \hline f & ~ & ~ & ~ & ~ & ~ & ~ \\ \hline \end{array}$$

Reflexive:

$$\begin{array} {r|c|c|c|c|c|c|} & a & b & c & d & e & f \\ \hline a & \RX & \X & \X & ~ & ~ & ~ \\ \hline b & ~ & \RX & ~ & ~ & ~ & \X \\ \hline c & ~ & ~ & \RX & ~ & ~ & ~ \\ \hline d & ~ & ~ & ~ & \RX & \X & ~ \\ \hline e & ~ & ~ & ~ & ~ & \RX & ~ \\ \hline f & ~ & ~ & ~ & ~ & ~ & \RX \\ \hline \end{array}$$

Symmetric:

$$\begin{array} {r|c|c|c|c|c|c|} & a & b & c & d & e & f \\ \hline a & \X & \X & \X & ~ & ~ & ~ \\ \hline b & \RX & \X & ~ & ~ & ~ & \X \\ \hline c & \RX & ~ & \X & ~ & ~ & ~ \\ \hline d & ~ & ~ & ~ & \X & \X & ~ \\ \hline e & ~ & ~ & ~ & \RX & \X & ~ \\ \hline f & ~ & \RX & ~ & ~ & ~ & \X \\ \hline \end{array}$$

Transitive (if (x, y) is marked, then row x gets everything from row y):

$$\begin{array} {r|c|c|c|c|c|c|} & a & b & c & d & e & f \\ \hline a & \X & \X & \X & ~ & ~ & \RX \\ \hline b & \X & \X & \RX & ~ & ~ & \X \\ \hline c & \X & \RX & \X & ~ & ~ & ~ \\ \hline d & ~ & ~ & ~ & \X & \X & ~ \\ \hline e & ~ & ~ & ~ & \X & \X & ~ \\ \hline f & \RX & \X & ~ & ~ & ~ & \X \\ \hline \end{array}$$

More transitivity:

$$\begin{array} {r|c|c|c|c|c|c|} & a & b & c & d & e & f \\ \hline a & \X & \X & \X & ~ & ~ & \X \\ \hline b & \X & \X & \X & ~ & ~ & \X \\ \hline c & \X & \X & \X & ~ & ~ & \RX \\ \hline d & ~ & ~ & ~ & \X & \X & ~ \\ \hline e & ~ & ~ & ~ & \X & \X & ~ \\ \hline f & \X & \X & \RX & ~ & ~ & \X \\ \hline \end{array}$$

And now it is an equivalence relation. This assumes $\{a, b, c, d, e, f\}$ are distinct.

Please explain what the smallest equivalence relation means.

Your source is using the set theoretic interpretation of "relation". A relation is a mapping from a tuple of objects to true/false. For example:

$$\begin{array} {|rcl|} \hline (1, 2) & \to & \text{True} \\ (a, b) & \to & \text{False} \\ (\text{blue}, \text{red}) & \to & \text{False} \\ (+, -) & \to & \text{True} \\ \hline \end{array}$$

The above (partial) relation maps 4 tuples (pairs specifically) into true or false. The set theoretic interpretation of the above relation is simply the set with the affirming tuples:

$$\{(1, 2), (+, -)\}$$

The size of that relation is the size of the set which is 2, since it has 2 pairs. The minimum relation, as the question asks, would be the relation with the fewest affirming elements that satisfies the conditions. The conditions are that the relation must be an equivalence relation and it must affirm at least the 4 pairs listed in the question.

So another possible relation that satisfies the conditions would be one that affirmed all 36 pairs. But that is larger than necessary, there is a relation that affirms fewer pairs while still being an equivalence relation.