Equivalence Relation Generated by the Empty Set

Question

I'm reading David Spivak's book "Category Theory for the Sciences" and on page 79 there is a problem related to generating $S \subseteq X \times X$ the smallest equivalence relation that contains $R$.

Part c) of the problem has $R = \emptyset$ and it asks you to graph the resulting equivalence relation generated by $R$. The answer just graphs the line $x = y$ in 2 dimensions (i.e. the identity relation on $X$).

Why is the line $x = y$ the smallest equivalence relation that contains $\emptyset$?

Answer 1

The equivalence relation (on a set $X$) generatd by $R$ is the smallest $S \subseteq X \times X$ such that:

1. $R \subseteq S$;

2. $S$ is reflexive, i.e. $\forall x \in X$, $ x S x$;

3. $S$ is symmetric, i.e. $\forall x, y \in X$ if $xSy$ then $y Sx$;

4. $S$ is transitive, i.e. $\forall x, y, z \in X$ if $xSy$ and $ySz$ then $xSz$.

Let us consider the case $R = \emptyset$. I claim that $S$ is the identity relation $=$ on $X$.

Proof:

Since $R = \emptyset$, we have $R \subseteq \, = $, i.e. the identity is a binary relation on $X$ containing $R$. Moreover, $=$ is also reflexive, symmetric and transitive. Therefore, the identity $=$ is a binary relation on $X$ fulfilling the conditions 1-4.

Reflexivity of $S$ implies that $xSx$ for every $x \in X$, hence $= \, \subseteq S$, i.e. the identity is included in $S$. By minimality of $S$, we have that $S$ coincide with $=$.