El menor número de pares ordenados posibles en una relación

Question

Hay muchas relaciones de equivalencia posibles en el conjunto $A = \{a, b, c, d\}.$ Por ejemplo, aquí hay dos diferentes:

(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$ tiene $8$ pares ordenados mientras que $E_2$ tiene $10.$ Pregunta: De todas las posibles relaciones de equivalencia en $A$ ¿cuál es el menor número de pares ordenados posible en la relación?

Answer 1

Dejemos que $A=\{a,b,c,d\}$ y que $E \subseteq A\times A$ sea la relación de equivalencia en $A$ con la menor cardinalidad.

Desde $E$ debe satisfacer la reflexividad, $$\{(a,a),(b,b),(c,c),(d,d)\} \subseteq E$$ Este conjunto también satisface la reflexividad y la transitividad, por lo que

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

El menor número de pares ordenados en una relación de equivalencia sobre $A$ es por lo tanto $4$ .