Equivalence Relations

Equivalence Relations (Properties and Closures)


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-21 18:27:13

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.

5/5 (1 Review)

Leave a Comment

Scroll to Top