Type of Relations

The three basic properties. Let $R$ be a relation on a non-empty set $S$.

• $R$ is reflexive if $(a,a)\in R$ for every $a\in S$.
• $R$ is symmetric if $(a,b)\in R\Rightarrow(b,a)\in R$.
• $R$ is transitive if $(a,b)\in R$ and $(b,c)\in R\Rightarrow(a,c)\in R$.

Equivalence relation. $R$ is an equivalence relation on $S$ if it is reflexive, symmetric and transitive all at once.

Worked checks (from the book's illustrations).

• $R=\{(1,1),(2,1),(2,2),(3,3),(1,3),(4,4),(1,2),(3,1)\}$ on $\{1,2,3,4\}$: reflexive (all four $(a,a)$ present); symmetric (every pair's reverse is also listed); not transitive, since $(2,1),(1,3)\in R$ but $(2,3)\notin R$ -- so it is not an equivalence relation.
• "$\ell$ is parallel to $m$" on the set of all lines in a plane: reflexive, symmetric, transitive $\Rightarrow$ equivalence relation.
• "$a$ is a sister of $b$" on a family (children and elders): not reflexive (no one is their own sister), not symmetric, not transitive -- but restricted to only the female members it becomes symmetric (though still not transitive).
• On $N$, "$xRy$ if $x+2y=21$" gives the explicit finite set $\{(1,10),(3,9),(5,8),(7,7),(9,6),(11,5),(13,4),(15,3),(17,2),(19,1)\}$: not reflexive ($(1,1)\notin R$), not symmetric ($(1,10)\in R$ but $(10,1)\notin R$), not transitive ($(3,9),(9,6)\in R$ but $(3,6)\notin R$).
• The empty relation on any set is (vacuously) both symmetric and transitive, but never reflexive on a non-empty set. The universal relation is always an equivalence relation. A relation with a single pair is always transitive.

A worked equivalence check. $R=\{(1,1),(2,2),\dots,(n,n)\}$ on $\{1,\dots,n\}$ (the diagonal relation) is trivially reflexive, and vacuously symmetric/transitive (there is no pair to violate either property), so it is an equivalence relation -- in fact the smallest possible one on an $n$-element set.

Building a relation of a required type. Given a relation that fails a property, we can repair it by inserting or deleting pairs. For $S=\{1,2,3\},\ \rho=\{(1,1),(1,2),(2,2),(1,3),(3,1)\}$: adding $(3,3)$ makes it reflexive; adding $(2,1)$ makes it symmetric; adding $(3,3)$ and $(3,2)$ (or instead removing $(3,1)$) makes it transitive; combining all the additions and then also adding $(2,3)$ (needed once $(3,2)$ appears, for symmetry) yields the equivalence relation $\{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(3,2),(2,3)\}$.

Counting theorem. The number of relations from an $m$-element set to an $n$-element set is $2^{mn}$ (each of the $mn$ possible pairs is independently in or out), so the number of relations on an $n$-element set is $2^{n^2}$. Among these, the number of reflexive relations on $n$ elements is $2^{n^2-n}$ (the $n$ diagonal pairs are forced in, the rest free), and the number of symmetric relations is $2^{(n^2+n)/2}$ (the $n$ diagonal pairs are free, and each of the $\binom n2$ off-diagonal pairs is decided together with its mirror pair). …