Fewest number of possible ordered pairs in a relation

Question

There are many different equivalence relation possible on the set $A = \{a, b, c, d\}.$ For example, here are just two different ones:

(a) $E_1 = \{(a, a), (b, b), (c, c), (d, d), (a, c), (c, a), (b, d), (d, b)\}.$
(b) $E_2 = \{(a, a), (b, b), (c, c), (d, d), (a, c), (c, a), (a, b), (b, a), (b, c), (c, b)\}.$

$E_1$ has $8$ ordered pairs while $E_2$ has $10.$ Question: Of all the possible equivalence relations on $A$, what is the fewest number of ordered pairs possible in the relation?

Answer 1

Let $A=\{a,b,c,d\}$ and let $E \subseteq A\times A$ be the equivalence relation on $A$ with the smallest cardinality.

Since $E$ must satisfy reflexivity, $$\{(a,a),(b,b),(c,c),(d,d)\} \subseteq E$$ This set also satisfies reflexivity and transitivity, so

$$E = \{(a,a),(b,b),(c,c),(d,d)\}$$

The fewest number of ordered pairs in an equivalence relation on $A$ is therefore $4$.