Equivalence Relations (Properties and Closures)

Share on tumblr
Share on facebook
Share on linkedin
Share on twitter
Share on stumbleupon
Share on email
Share on pinterest

Equivalence Relations (Properties and Closures)

Equivalence Relations

We discuss the reflexive, symmetric, and transitive properties and their closures. The relationship between a partition of a set and an equivalence relation on a set is detailed. We then give the two most important examples of equivalence relations.

Reflexive, Symmetric, and Transitive Relations

Definition. Let $X$ be a set.

A relation $R$ on $X$ is called reflexive if it satisfies the  property $$ \forall a\in X, (a,a)\in R. $$
A relation $R$ on $X$ is called symmetric if it satisfies the  property $$ \forall a,b \in X, (a,b)\in R \implies (b,a)\in R. $$
A relation $R$ on $X$ is called transitive if it satisfies the  property $$ \forall a,b,c\in X, ((a,b)\in R \land (b,c)\in R) \implies (a,c)\in R. $$

Theorem. Let $R$ and $S$ be relations on $X$ and let $A\subseteq X.$ 

$\quad (1) $ A relation $R$ is reflexive if and only if $I \subseteq R.$ 

$\quad (2) $ A relation $R$ is symmetric if and only if $R^{-1}\subseteq R.$  

$\quad (3) $ A relation $R$ is transitive if and only if  $R\circ R\subseteq R.$

Proof. The proof of each part follows. $(1)$ If $R$ is reflexive, then $I\subseteq R.$ $$ (x,y)\in I \Leftrightarrow y=x \implies (x,y)\in R $$ Conversely, if $I\subseteq R$,  then $R$ is reflexive. $$ x\in X \implies (x,x)\in I \implies (x,x)\in R $$ $(2)$ If $R$ is symmetric, then $R^{-1}\subseteq R.$ $$ (x,y)\in R^{-1}\Leftrightarrow (y,x)\in R \implies (x,y)\in R $$ Conversely, if $R^{-1}\subseteq R$,  then $R$ is symmetric. $$ (x,y)\in R \implies (y,x)\in R^{-1} \implies (y,x)\in R $$ $(3)$ If $R$ is transitive, then $R\circ R\subseteq R.$ $$ (x,y)\in R\circ R \Leftrightarrow \exists x\in X, (x,z)\in R \land (z,y)\in R \implies (x,y)\in R $$ Conversely, if $R\circ R\subseteq R$,  then $R$ is transitive.  $$ (x,y)\in R \land (y,z)\in R \implies (x,z)\in R\circ R \implies (x,z)\in R. $$ The proof is now complete.

Theorem. If $R$ and $S$ are reflexive, then $R|_A$,  $R^{-1}$,  $S\circ R$,  $R\cup S$,  and  $R\cap S$  are also reflexive, while $R^c$ is not reflexive.

Proof. We find that $R|_A$,  $R^{-1}$,  $S\circ R$,  $R\cup S$,  and $R\cap S$ are reflexive, whenever $R$ and $S$ are reflexive by the following arguments, respectively. 

$\quad (x,x)\in R \land A\subseteq X \implies (x,x)\in R|_{A}$

$\quad (x,x)\in R \implies (x,x)\in R^{-1}$

$\quad (x,x)\in R \land (x,x)\in S \implies (x,x)\in S\circ R$

$\quad (x,x)\in R \land (x,x)\in S \implies (x,x)\in R\cup S$

$\quad (x,x)\in R \land (x,x)\in S \implies (x,x)\in R\cap S$

Notice that $R^c$ is not reflexive because $I\subseteq R\implies I\not\subseteq R^c.$

Theorem. If $R$ and $S$ are symmetric, then $R|_A$,  $R^c$,  $R^{-1}$,  $R^{-1}\circ R$,  $R\cup S$,  and  $R\cap S$ are also symmetric.

Proof. If $R$ is symmetric, then $R|_{A}$ is symmetric. \begin{align*} \qquad \qquad& (x,y)\in R|_A \Longleftrightarrow (x,y) \in (A\times A) \cap R  \\ & \qquad  \Longleftrightarrow (x,y)\in A\times A \land (x,y)\in R  \Longleftrightarrow (y,x)\in A\times A \land (y,x)\in R  \\ & \qquad  \Longleftrightarrow (y,x) \in (A\times A) \cap R  \Longleftrightarrow (x,y)\in R|_A \end{align*} If $R$ is symmetric, then $R^c$ is symmetric. \begin{align*} & (x,y)\in R^c  \Longleftrightarrow (x,y)\notin R \Longleftrightarrow \neg ((x,y)\in R)  \\& \qquad   \Longleftrightarrow \neg( (y,x)\in R)  \Longleftrightarrow (y,x)\notin R \Longleftrightarrow (y,x)\in R^c \end{align*} If $R$ is symmetric, then $R^{-1}$ is symmetric. \begin{align*} \qquad (x,y)\in R^{-1}  \Longleftrightarrow (y,x)\in R \Longleftrightarrow (x,y)\in R \Longleftrightarrow (y,x)\in R^{-1} \end{align*} If $R$ and $S$ are symmetric, then $R\cup S$ is symmetric. \begin{align*} \qquad &  (x,y)\in R\cup S \Longleftrightarrow (x,y)\in R \lor (x,y)\in S  \\ & \qquad  \Longleftrightarrow (y,x)\in R \lor (y,x)\in S \Longleftrightarrow (y,x)\in R\cup S \end{align*} If $R$ and $S$ are symmetric then the relation $R\cap S$ is symmetric. \begin{align*} \qquad &  (x,y)\in R\cap S  \Longleftrightarrow (x,y)\in R \land (x,y)\in S \\ & \qquad  \Longleftrightarrow (y,x)\in R \land (y,x)\in S \Longleftrightarrow (y,x)\in R\cap S \end{align*} If $R$ is symmetric, then $R^{-1}\circ R$ is symmetric. \begin{align*} \qquad \qquad & (x,y)\in R^{-1}\circ R  \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R^{-1}  \\ & \qquad \Longleftrightarrow \exists z\in X, (z,x)\in R^{-1} \land (y,z)\in R  \\ & \qquad \Longleftrightarrow \exists z\in X,  (y,z)\in R \land (z,x)\in R^{-1} \Longleftrightarrow (y,x)\in R^{-1}\circ R \end{align*} which completes the proof.

Theorem. Let $R$ and $S$ be relations on $X$ and let $A\subseteq X.$  If $R$ and $S$ are transitive, then $R|_A$,  $R^{-1}$,  $R^2$, and $R\cap S$ are also transitive, while $R^c$ and $R\cup S$ are not transitive. 

Proof. If $R$ is transitive, then $R|_{A}$ is transitive. \begin{align*} \qquad \qquad & (x,y)\in  R|_A \land (y,z)\in R|_A  \\ & \qquad  \Longleftrightarrow [(x,y)\in A\times A \land (x,y)\in R] \land [(y,z)\in A\times A \land (y,z)\in R] \\ & \qquad  \Longleftrightarrow (x,z)\in A\times A \land (x,z)\in R  \\ & \qquad  \Longleftrightarrow (x,z)\in (A\times A) \cap R  \Longleftrightarrow (x,z)\in R|_A \end{align*} If $R$ is transitive, then $R^{-1}$ is transitive. \begin{align*} \qquad \qquad & (x,y)\in R^{-1} \land (y,z)\in R^{-1} \Longleftrightarrow (y,x)\in R \land (z,y)\in R  \\ & \qquad \Longleftrightarrow (z,y)\in R \land (y,x) \in R  \Longleftrightarrow (z,x)\in R  \Longleftrightarrow (x,z)\in R^{-1} \end{align*} If $R$ is transitive, then $R^2$ is transitive. \begin{align*} \quad \qquad \qquad &  (x,y)\in R^2 \land (y,z)\in R^2  \\ & \Longleftrightarrow [\exists s\in X, (x,s)\in R \land (s,y)\in R] \land [\exists t\in X, (y,t)\in R \land (t,z)\in R] \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,y)\in R \land (y,t)\in R \land (t,z)\in R \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R\land (s,t)\in R \land (t,z)\in R  \\ &  \Longleftrightarrow (x,t) \in R \land (t,z)\in R  \Longleftrightarrow (x,z)\in R^2 \end{align*} If $R$ and $S$ are transitive then the relation $R\cap S$ is transitive. \begin{align*} & (x,y)\in R\cap S \land (y,z)\in R\cap S \\ & \qquad \Longleftrightarrow (x,y)\in R \land (x,y)\in S \land (y,z)\in R \land (y,z)\in S  \\ & \qquad  \Longleftrightarrow (x,z)\in R \land (x,z)\in S \Longleftrightarrow (x,z)\in R\cap S \end{align*} If $R$ and $S$ are transitive then the relation $R\cup S$ is not necessarily transitive.  To see this let $X=\{a,b,c\}$, $R=\{(a,b),(b,c),(a,c)\}$ and $S=\{(b,c),(c,d),(b,d)\}.$  Then $R$ and $S$ are transitive, however, $R\cup S$ is not transitive since $(a,b), (b,d)\in R\cup S$ yet $(a,d)\notin R\cup S.$  If $R$ is transitive then $R^c$ is not necessarily transitive.  To see this let $X=\{a,b\}$ and $R=I.$ The $R$ is transitive and $R^c=\{(a,b),(b,a)\}$ which is not transitive.

Definition. If a relation is reflexive, symmetric, and transitive, then it is called an equivalence relation.

Theorem. Let $R$ and $S$ be relations on $X$ and let $A\subseteq X.$ Let $R$ and $S$ be equivalence relations.  Then  $R|_A$,   $R^{-1}$,   $R^2$,  and  $R\cap S$  are also equivalence relations. 

Proof. The proof is left as an exercise.

Theorem. Let $R$ and $S$ be relations on $X$ and let $A\subseteq X.$ 

(1) If $R$ and $S$ are symmetric, then $S\circ R$ is symmetric if and only if $R\circ S\subseteq  S\circ R.$

(2) If $R$ and $S$ are transitive and $R\circ S\subseteq S\circ R$,  then $S\circ R$ is transitive, but not conversely. 

(3) If $R$ and $S$ are equivalence relations, then $S\circ R$ is an equivalence relation if and only if $R\circ S\subseteq S\circ R.$ 

Proof. The proof of each part follows. 

(1) If $R$ and $S$ are symmetric and $R\circ S\subseteq S\circ R$,  then $S\circ R$ is symmetric. \begin{align*} \qquad  & (x,y)\in S\circ R  \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (z,x)\in R \land (y,z)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (y,z)\in S \land (z,x)\in R \Longleftrightarrow (y,x)\in R\circ S \\ & \qquad \Longleftrightarrow (y,x)\in S\circ R \end{align*} Conversely, assume $R$,  $S$,  and $S\circ R$ are symmetric, then $S\circ R=R\circ S.$ \begin{align*} \qquad  & (x,y)\in S\circ R  \Longleftrightarrow (y,x)\in S\circ R \\ & \qquad \Longleftrightarrow \exists z\in X, (y,z)\in R \land (z,x)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (z,y)\in R \land (x,z)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (x,z)\in S \land (z,y)\in R \Longleftrightarrow (x,y)\in R\circ S \end{align*}

(2) If $R$ and $S$ are transitive and $R\circ S\subseteq S\circ R$,  then $S\circ R$ is transitive. \begin{align*}  &  (x,y)\in S\circ R \land (y,z)\in S\circ R  \\ &  \Longleftrightarrow [\exists s\in X, (x,s)\in R\land (s,y)\in S] \land [\exists t\in X, (y,t)\in R \land (t,z)\in S]  \\ &  \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,y)\in S \land (y,t)\in R \land (t,z)\in S \\ & \Longleftrightarrow \exists s,t,\in X, (x,s)\in R \land (s,t)\in R\circ S \land (t,z)\in S  \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,t)\in S\circ R \land (t,z)\in S \\ & \Longleftrightarrow \exists s,t,w\in X, (x,s)\in R \land (s,w)\in R \land (w,t)\in S \land (t,z)\in S \\ & \Longleftrightarrow \exists w\in X, (x,w)\in R \land (w,z)\in S \Longleftrightarrow (x,z)\in S\circ R\end{align*} Let $X=\{a,b,c\}$,  $R=\{(a,a), (a,b)\}$,  and $S=\{(b,b),(b,c)\}.$ Then $R$ and $S$ are transitive and so is $S\circ R=\{(a,b),(a,c)\}.$  However, $R\circ S=\emptyset.$

(3) If $R$,  $S$,  and $S\circ R$ are equivalence relations on $X$,  then $R\circ S \subseteq S\circ R.$ \begin{align*} \qquad S\circ R & \textrm{ is an equivalence relation} \\ & \Longleftrightarrow S\circ R \textrm{ is reflexive, symmetric, and transitive} \\ & \Longrightarrow S\circ R \textrm{ is symmetric } \Longleftrightarrow R\circ S \subseteq S\circ R\end{align*} Conversely, if $R$ and $S$ are equivalence relations and $R\circ S\subseteq S\circ R$,  then $S\circ R$ is an equivalence relation. \begin{align*} \qquad & R\circ S \subseteq S\circ R \land S, R \textrm{ are equivalence relations}  \\ & \qquad \Longrightarrow S\circ R \textrm{ is reflexive, symmetric, and transitive }  \\ & \qquad  \Longleftrightarrow S\circ R \textrm{ is an equivalence relation } \end{align*}
which completes the proof.

Theorem. Let $R$ be a relation on $X.$ Then $R$ is an equivalence relation if and only if  $$ R=I\cup R^{-1} \cup R^2. $$

Proof. Let $R$ be a relation on $X.$  If $R$ is reflexive, symmetric, and transitive it follows $I\subseteq R$,  $R^{-1} =R$,  and $R^2=R$; and thus $I\cup R^{-1}\cup R^2=R.$  Conversely, assume $R$ be a relation on $X.$  If $I\cup R^{-1}\cup R^2=R$,  then $I\subseteq R$,  $R^{-1} \subseteq R$,  and $R^2\subseteq R$; and therefore $R$ is an equivalence relation. 

Theorem. Let $\sim$ be a relation on $X.$ Then $\sim$ is an equivalence relation if and only if the following property holds: \begin{equation} \forall \, a,b\in X, a\sim b  \Leftrightarrow \forall \, c\in X, a\sim c \Leftrightarrow b\sim c. \end{equation}

Proof. Assume $\sim$ is an equivalence relation on $X.$  Assume $a\sim b$ for arbitrary $a,b\in X.$  Let $c\in X.$  By symmetry and transitivity it follows that $$ a\sim c \implies c\sim a \implies c\sim b \implies b\sim c $$ and conversely, $b\sim c \implies a\sim c$ follows by transitivity. Therefore, by symmetry and transitivity we have $$ \forall a,b \in X, a\sim b \implies \forall c\in X, a\sim c \Leftrightarrow b\sim c. $$ Assume for all $c\in X$ that $a\sim c \Leftrightarrow b\sim c.$ Let $c=a.$ Then we have $a\sim a \Leftrightarrow b\sim a.$ Since $\sim$ is reflexive, $a\sim b$ must hold.  Whence, $$ \forall c\in X, (a\sim c \Leftrightarrow b\sim c) \implies a\sim b $$ as desired.

Conversely, assume the given property holds.  To show reflexivity, let $a\in X.$ Since, $a\sim a$ if and only if $a\sim a$,  obviously holds, it follows $a\sim a$ is valid.  To prove the symmetric property holds, assume $a\sim b.$ Therefore the following holds, $\forall c\in X, a\sim c \Leftrightarrow b\sim c. $ Equivalently, the following holds $ \forall c\in X, b\sim c \Leftrightarrow a\sim c.$ Thus is it obvious that, $a\sim b \implies b\sim a$ holds; and therefore $\sim$ is also symmetric.  To show transitivity, let $a,b,c\in X$ and assume $a\sim b$ and $b\sim c.$  Therefore the following holds, $$ [\forall c\in X, a\sim c \Leftrightarrow b \sim c]  \land  [\forall d\in X, b\sim d \Leftrightarrow c \sim d].  $$ Let $e\in X.$  Then the following holds, $$ a\sim e \Leftrightarrow b\sim e \Leftrightarrow c\sim e. $$ Therefore, $a\sim c$ and so $\sim $ is also transitive.  In conclusion, $\sim $ is an equivalence relation. 

The importance of equivalence relations is discussed here.

Partitions

Definition. If $\sim$ is an equivalence relation on $X$,  then the set $$[a]=\{b\in X : b\sim a\}$$ is called the equivalence class of $a$ with respect to $\sim.$

Definition. A partition of $X$ is a collection of pairwise disjoint nonempty sets whose union is $X.$

Theorem. Let $\sim$ be a relation on $X.$ Then $\sim$ is an equivalence relation on $X$ if and only if the set $$P=\{\{b\in X: a\sim b \}: a\in X\}$$ is a partition of $X$ with the property $\forall a,b\in X, a\sim b \Leftrightarrow \exists A\in P$ such that $a,b\in A.$

Proof. Assume $\sim$ is an equivalence relation on $X.$ We will prove that $P$ is a partition of $X$ with the desired property by proving the following four statements hold.

(1) $X$ is the union of all equivalence classes of $\sim.$  Proof: Since $\sim$ is reflexive it follows that $$ x\in \bigcup_{a\in X}[a] \Leftrightarrow \exists a\in X, x\in [a] \Leftrightarrow x\in X. $$
(2) For all $a,b\in X$,  $[a]\cap [b]\neq \emptyset \Leftrightarrow [a]=[b].$  Proof:  Assume $[a]\cap [b] \neq \emptyset.$ Since $\sim$ is symmetric and transitive, it follows \begin{align*} x\in [a]  & \Leftrightarrow x\sim a \Leftrightarrow x\sim a \land \, \exists y\in [a] \cap [b]  \\ &  \Leftrightarrow \exists y\in X, x\sim a \land y\sim a \land y\sim b  \\ &  \Leftrightarrow \exists y\in X, x\sim a \land a\sim y \land y\sim b  \\ &  \Leftrightarrow \exists y\in X, x\sim y \land y\sim b  \Leftrightarrow x\sim b \Leftrightarrow x\in [b]  \end{align*} Assume $[a]=[b].$  Since $\sim$ is reflexive  $$ a\in [a]  \implies  a\in [a] \land a\in [b] \\ \implies a\in [a] \cap [b] \\ \implies [a]\cap [b] \neq \emptyset $$
(3) Every equivalence class of $\sim$ is nonempty.  Proof: Since $\sim$ is reflexive, it follows that $$ a\in X \implies a\sim a \implies a\in [a] \implies [a]\neq \emptyset. $$
(4) For all $a,b\in X$,  $a\sim b \Leftrightarrow [a]=[b].$  Proof: Let $a,b\in X$ and assume $a\sim b.$  Then it follows that $$ x\in [a] \Leftrightarrow x\sim a \Leftrightarrow x\sim b \Leftrightarrow x\in [b]. $$ Thus we have that $[a]=[b].$ Conversely, assume $[a]=[b]$ for all $a,b$ in $X.$  Then it follows that  $$ a\in [a] \implies a\in [b] \implies a\sim b. $$ and so $a\sim b$ holds.  \end{enumerate} Therefore we have shown that $P$,  the collection of equivalence class of $\sim$,  is a partition on $X$ with the desired property.  Conversely, assume $\sim$ is a relation on $X$ and $P$ is a partition of $X$ with the stated property.  First we notice $\sim$ is reflexive since  $$ a\in X \implies a\in\bigcup_{A\in P} A \implies \exists A\in P, a\in A \implies a\sim a.$$ The symmetric property of $\sim$ follows by  $$ a\sim b \implies \exists A\in P, a\in A \land b\in A \implies b\sim a. $$ We also notice $\sim$ is transitive by the following  $$ a\sim b \land b\sim c \Leftrightarrow \exists a, b\in P, a,b\in A\land b,c\in B \Longrightarrow A=B  \Leftrightarrow a\sim c. $$
In conclusion $\sim$ is an equivalence relation where $a\sim b$ is equivalent to the existence of a set $A\in P$ with $a,b\in A$,  namely the equivalence class $A=[a].$ 

Closures

In order to fully understand reflexive, symmetric, and transitive closures is first reading families of sets.

Theorem. Let $R$ be relation on $X$ and $A\subseteq X.$  The reflexive closure of $R$ is the relation  $$ r(R)=R \cup I. $$

Proof. Let $R$ b a relation, then $r(R)=R\cup I.$  Notice $R\cup I$ is reflexive since  $$ x\in X \implies (x,x)\in I\implies (x,x)\in R\cup I. $$ Let $T$ be a reflexive relation containing $R.$  Then $R\cup I\subseteq T$ since  \begin{align*} & (x,y)\in R\cup I  \implies (x,y)\in R \lor (x,y)\in I   \\&\qquad  \implies (x,y)\in T \lor (x,y)\in I  \implies (x,y)\in T \cup I =T  \end{align*} Since $R\subseteq R\cup I \subseteq T$ where $T$ is an arbitrary reflexive relation containing $R$,  it follows $r(R)=R\cup I.$ 

Theorem. Let $R$ be relation on $X$ and $A\subseteq X.$  The symmetric closure of $R$ is the relation  $$ s(R)=R \cup R^{-1}. $$

Proof. Let $R$ b a relation, then $s(R)=R\cup R^{-1}.$  Notice $R\cup R^{-1}$ is symmetric since  \begin{align*} \qquad \qquad & (x,y) \in R\cup R^{-1}  \implies  (x,y)\in R \lor (x,y)\in R^{-1} \\ & \qquad  \implies  (y,x)\in R^{-1} \lor (y,x)\in R  \implies  (y,x)\in R^{-1} \cup R=R\cup R^{-1} \end{align*} Let $T$ be a symmetric relation containing $R.$  Then $R\cup R^{-1}\subseteq T$ since  \begin{align*} \qquad \qquad & (x,y) \in R\cup R^{-1}  \implies (x,y)\in R \lor (x,y)\in R^{-1}  \\ & \qquad  \implies (x,y)\in T \lor (x,y)\in R^{-1}  \implies (x,y)\in T \lor (y,x)\in T  \\ & \qquad  \implies (x,y)\in T \lor (x,y)\in T \implies (x,y)\in T \end{align*} Since $R\subseteq R\cup R^{-1} \subseteq T$ where $T$ is an arbitrary symmetric relation containing $R$,  it follows $s(R)=R\cup R^{-1}.$

Transitive closures are important for partial order relations as well.

Theorem. Let $R$ be relation on $X$ and $A\subseteq X.$  The transitive closure of $R$ and the reflexive transitive closure of $R$ are $$ t(R)=\bigcup_{n\geq 1} R^n. \qquad \qquad rt(R)=\bigcup_{n\geq 0} R^n. $$  respectively.

Proof. For $i>0$ define $$R^i=R^{i-1}\cup \{(a,b) : \exists c\in X, (a,c)\in R^{i-1} \land (c,b)\in R^{i-1}\}$$ The transitive closure of $R$,  denoted by $t(R)$,  is the relation $t(R)=\cup_{n\geq 1} R^n.$ First notice $t(R)$ contains all powers of $R$ and so in particular $t(R)$ contains $R.$  Next notice that $t(R)$ is transitive since \begin{align*}\qquad \qquad & (a,b)\in t(R) \land (b,c)\in t(R)  \implies \exists R^n, R^m, (a,b)\in R^n \land (b,c)\in R^m \\ & \qquad \implies (a,c) \in R^m\circ R^n\subseteq t(R) \end{align*} Let $T$ be a transitive relation containing $R.$  By induction it follows $R^k\subseteq T$ for all $k.$  This is true for $k=1$ since $T$ contains $R.$  Then $$ R^k\subseteq T  \implies R^{k+1} =R^{k}\circ R \subseteq T\circ R \subseteq T \circ T  =T $$ demonstrates the claim. Whence, $t(R)=\bigcup_{n\geq 1}R^n\subseteq T$ as desired.  Define $R^0=I$,  then  $$ rt(R)=r\left(\bigcup_{n\geq1}R^n\right) = \bigcup_{n\geq1}R^n\cup I = \bigcup_{n\geq1}R^n \cup R^0 = \bigcup_{n\geq0}R^n. $$ which completes the proof.

Theorem. Let $R$ be a relation on $X.$ Then $R$ is transitive if and only if $R^n\subseteq R$,  for $n\geq 1.$ 

Proof. Assume $R$ is transitive. We will prove $R^n \subseteq $R for $n\geq 1$ by induction.  The basis step is obvious. The induction step is: $$ R^n\subseteq R \implies R^{n+1}\subseteq R $$ Assume $R^n\subseteq R$ for some $n\geq 1.$  Then  \begin{align*} (x,y)\in R^{n+1}  & \Leftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R^n  \\ & \Leftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R  \implies (x,z)\in R  \end{align*} Therefore, by induction $R^n\subseteq R$,  for all $\geq 1.$  Conversely, assume $R^n\subseteq R$,  for all $n\geq 1.$  Then $(x,y)\in R\land (y,z)\in R \implies (x,z)\in R^2 \implies (x,y)\in R.$ Thus, $R$ is transitive.

Theorem. Let $R$ be a relation on $X.$ If $R$ is reflexive, then $s(R)$ and $t(R)$ are reflexive.

Proof. If $R$ is reflexive, then $s(R)$ and $t(R)$ are reflexive, then  $$ I\subseteq R\subseteq s(R) \text{ and } I\subseteq R \subseteq t(R) $$ as desired.

Theorem. Let $R$ be a relation on $X.$ If $R$ is symmetric, then $r(R)$ and $t(R)$ are symmetric.

Proof. If $R$ is symmetric, then $r(R)$ and $t(R)$ are symmetric.  \begin{align*} & (x,y)\in r(R)=R\cup I \implies (x,y)\in R \lor (x,y)\in I \\ & \qquad  \implies (y,x)\in R \lor (y,x)\in I  \implies (y,x)\in R \cup I =r(R) \\ &  (x,y)\in t(R)= \bigcup_{n\geq 1}R^n  \implies \exists R^n, (x,y)\in R^n  \\ & \qquad  \implies \exists R^n, (y,x)\in R^n  \implies (y,x)\in \bigcup_{n\geq 1}R^n=t(R)  \end{align*} which completes the proof.

Theorem. Let $R$ be a relation on $X.$ If $R$ is transitive, then $r(R)$ is transitive; however, $s(R)$ may not be transitive. 

Proof. If $R$ is transitive, then $r(R)$ is transitive.  \begin{align*} & (x,y)\in r(R) \land (y,z)\in r(R) \implies (x,y)\in R\cup I \land (y,z)\in R\cup I  \\ & \qquad  \implies ((x,y)\in R \lor (x,y)\in I)\land ((y,z)\in R \lor (y,z)\in I) \\ & \qquad  \implies (x,z)\in R \lor (x,z)\in I \implies (x,z)\in R \cup I =r(R) \end{align*} Let $X=\{a,b\}$ and $R=\{(a,b)\}.$  Then $R$ is transitive and $s(R)=\{(a,b),(b,a)\}$ is not transitive.  Therefore, the symmetric closure of a transitive relation may not be transitive.

Theorem. Let $R$ be a relation on $X.$ The following hold: $rt(R)=tr(R)$, $rs(R)=sr(R)$, $st(R)\subseteq ts(R)$, and $st(R)\subsetneq ts(R)$ can hold.

Proof. The proof of each part follows.

$rt(R)=tr(R)$ $$  tr(R) =t(R\cup I)=\bigcup_{n\geq 1} (R\cup I)^n =\left(\bigcup_{n\geq 1}R^n \right) \cup I  =\bigcup_{n\geq 0} R^n =rt(R) $$
$rs(R)=sr(R)$ \begin{align*}  & rs(R) = r(R\cup R^{-1}) = I\cup R\cup R^{-1}\\ &  =r(R)\cup R^{-1} =r(R)\cup (R^{-1}\cup I) =r(R)\cup r(R)^{-1} =sr(R) \end{align*}
$st(R)\subseteq ts(R)$
Let $A=\{a,b,c\}.$  Then $st(R)=\{(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\}$ and $ts(R)=A\times A$ which completes the proof.

Theorem. Let $R$ be a relation on a set $X.$  Then $R$ is an equivalence relation if and only if $R=rts(R).$

Proof. Assume $R$ is an equivalence relation on $X.$ Notice $R\subseteq rts(R)$,  where $r$,  $s$,  and $t$ denote the reflexive, symmetric and transitive closure operators, respectively.  Let $T$ be an arbitrary equivalence relation on $X$ containing $R$. Since $R\subseteq T$ and $T$ is symmetric, if follows that $s(R)\subseteq T$. Then $ts(R)\subseteq t(T)=T$ and so $rts(R)\subseteq r(T)=T$. Thus it follows $rts(R)$ is contained in $T$.  Since $R$ is an equivalence relation on $X$ containing $R$,  it follows that $rts(R)\subseteq R.$  Whence, $R=rts(R).$  Conversely, assume $R$ is a relation on $X$ such that $R=rts(R).$ It is easy to check that $ts(R)$ is symmetric and that $rts(R)$ is symmetric and transitive.  It follows that $rts(R)$ is an equivalence relation.  Thus $R$ is an equivalence relation. 

Theorem. Let $\longrightarrow$ be a relation on $X$ with transitive closure denoted by $\stackrel{+}{\longrightarrow}.$  Then $a\stackrel{+}{\longrightarrow} b$ if and only if there exists elements $a=x_1, x_2, x_3, …, x_n=b$ in $X$ such that $x_1\longrightarrow x_2 \longrightarrow \cdots \longrightarrow x_n.$

Proof. The proof is left for the reader.

Theorem. Let $f:X\to X$ be a function and let $\sim$ be the binary relation defined on $X$ by $a\sim b$ if and only if $f(a)=f(b).$ Then $\sim$ is an equivalence relation.

Proof. Since $f(a)=f(a)$ holds for all $a\in X$,  it follows $\sim$ is reflexive.  Let $a,b\in X$ and assume $a\sim b.$  Then $f(b)=f(a)$,  and thus $f(b)=f(a)$ also holds.  Thus, $b\sim a$ and so $\sim$ is also symmetric.  Let $a,b,c\in X$ and assume $a\sim b$ and $b\sim c.$  Then $f(a)=f(b)$ and $f(b)=f(c).$  Thus $f(a)=f(c)$ and so $a\sim c$,  which means $\sim$ is also transitive; and in conclusion an equivalence relation on $X.$

Recall, if $R$ is a binary relation on $X$,  then $R(x)=\{y\in X : (x,y)\in R\}$,  that is $R(x)$ is the set of outputs of $R$ for a given input $x.$  Of course when $R$ is a function $R(x)$ is a singleton set for each $x\in X.$  In general $R(x)$ can have many elements. 

Theorem. Let $R$ be a binary relation on $X$ and let $\ker(R)$ be the  relation defined on $X$ by $(a,b)\in \ker(R)$ if and only if $R(a)=R(b).$ Then $\ker(R)$ is an equivalence relation.

Proof. Since $R(a)=R(a)$ holds for all $a\in X$,  it follows $\ker(R)$ is reflexive.  Let $a,b\in X$ and assume $(a,b)\in \ker(R).$  Then $R(b)=R(a)$,  and thus $R(b)=R(a)$ also holds.  Thus, $(b,a)\in\ker(R)$ and so $\ker(R)$ is also symmetric.  Let $a,b,c\in X$ and assume $(a,b)$ and $(b,c)\in\ker(R).$  Then $R(a)=R(b)$ and $R(b)=R(c).$  Thus $R(a)=R(c)$ and so $(a,c)\in\ker(R)$,  which means $\ker(R)$ is also transitive; and in conclusion an equivalence relation on $X.$

Recall, if $R$ is a binary relation on $X$,  then $R^{-1}(y)=\{x\in X : (x,y)\in R\}$,  that is $R^{-1}(y)$ is the set of inputs of $R$ for a given output $y.$  In general $R(y)$ can have many elements. 

Theorem. Let $R$ be a binary relation on $X$ and let $\mathop{im}(R)$ be the  relation defined on $X$ by $(a,b)\in \mathop{im}(R)$ if and only if $R^{-1}(a)=R^{-1}(b).$ Then $\mathop{im}(R)$ is an equivalence relation. 

Proof. Since $R^{-1}(a)=R^{-1}(a)$ holds for all $a\in X$,  it follows $\mathop{im}(R)$ is reflexive.  Let $a,b\in X$ and assume $(a,b)\in\mathop{im}(R).$  Then $R^{-1}(b)=R^{-1}(a)$,  and thus ${R^{-1}(b)=R^{-1}(a)}$ also holds.  Thus, $(b,a)\in\mathop{im}(R)$ and so $\mathop{im}(R)$ is also symmetric.  Let $a,b,c\in X$ and assume $(a,b)\in\mathop{im}(R)$ and $(b,c)\in\mathop{im}(R).$  Then $R^{-1}(a)=R^{-1}(b)$ and $R^{-1}(b)=R^{-1}(c).$  Thus $R^{-1}(a)=R^{-1}(c)$ and so $(a,c)\in\mathop{im}(R)$,  which means $\mathop{im}(R)$ is also transitive; and in conclusion an equivalence relation on $X.$

Theorem. Let $R$ be a binary relation on $X.$  Then $R$ is an equivalence relation if and only if $\ker(R)=R$ if and only if $\mathop{im}(R)=R$ if and only if $R=R^*.$

Proof. The proof is left as an exercise.

0/5 (0 Reviews)
About the author David Smith Verified icon 1
David Smith is the Founder and CEO of Direct Knowledge. Inspired by more than two decades of teaching undergraduate mathematics, he founded Direct Knowledge to share high-quality educational content with anyone seeking to learn. In addition to teaching and coordinating undergraduate courses in calculus, linear algebra, and number theory at both a junior college and a Tier One research university, David pursued his personal interest in computer science with several graduate level courses in artificial intelligence and machine learning. David has a B.S. and M.S. in Mathematics.

Reply