Binary Relations (Types and Properties)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

Let $X$ be a set and let $X\times X=\{(a,b): a,b \in X\}.$ A (binary) relation $R$ is a subset of $X\times X$. If $(a,b)\in R$, then we say $a$ is related to $b$ by $R$. It is possible to have both $(a,b)\in R$ and $(a,b’)\in R$ where $b’\neq b$; that is any element in $X$ could be related to any number of other elements of $X$. It is also possible to have some element that is not related to any element in $X$ at all. 

Definition. Let $R$ and $S$ be relations on $X$. The composition of $R$ and $S$ is the relation $$S\circ R  =\{(a,c)\in X\times X : \exists \, b\in X, (a,b)\in R \land (b,c)\in S\}.$$

Compositions of binary relations can be visualized here.

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $R\circ (S\circ T)=(R\circ S)\circ T$.

Proof. The proof follows from the following statements. \begin{align*} (x,y)\in & R\circ (S\circ T) \\ & \Longleftrightarrow \exists z\in X, (x,z)\in S\circ T \land (z,y)\in R\\ & \Longleftrightarrow \exists z\in X, [ \exists w\in X, (x,w)\in T \land (w,z)\in S ] \land  (z,y)\in R \\ & \Longleftrightarrow \exists w, z\in X, (x,w)\in T \land (w,z)\in S \land (z,y)\in R\\ & \Longleftrightarrow \exists w\in X, [\exists z\in X, (w,z)\in S \land (z,y)\in R] \land (x,w)\in T\\ & \Longleftrightarrow \exists w\in X, (x,w)\in T \land (w,y)\in R\circ S \\ & \Longleftrightarrow (x,y)\in (R\circ S) \circ T  \end{align*}

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $R\circ (S\cup T)=(R\circ S)\cup (R\circ T)$.

Proof. The proof follows from the following statements. \begin{align*} (x,y) & \in R\circ (S\cup T) \\ & \Longleftrightarrow \exists z\in X, (x,z)\in S \cup T \land (z,y)\in R \\ & \Longleftrightarrow \exists z\in X, [(x,z)\in S \lor (x,z)\in T ]  \land (z,y)\in R \\ & \Longleftrightarrow \exists z\in X, [(x,z)\in S \land (z,y)\in R] \lor [(x,z)\in T \land (z,y)\in R]\\ & \Longleftrightarrow (x,y)\in R\circ S \lor (x,y)\in R\circ T\\ & \Longleftrightarrow (x,y)\in (R\circ S)\cup (R \circ T)  \end{align*}

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $(S\cup T)\circ R=(S\circ R)\cup (T\circ R)$.

Proof. The proof follows from the following statements. \begin{align*} (x,y) & \in (S\cup T)\circ R \\ & \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in S\cup T\\ & \Longleftrightarrow \exists z\in X, (x,z)\in R \land [(z,y)\in S\lor (z,y)\in T] \\ & \Longleftrightarrow \exists z\in X, [(x,z)\in R \land (z,y)\in S] \lor  [(x,z)\in R \land (z,y)\in T] \\ & \Longleftrightarrow (x,y)\in (S\circ R) \lor (x,y)\in (T\circ R)\\ & \Longleftrightarrow (x,y)\in (S\circ R)\cup (T\circ R) \end{align*}

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $R\circ (S\cap T) \subseteq (R\circ S)\cap (R\circ T)$.

Proof. The proof follows from the following statements. \begin{align*} \qquad \quad  & (x,y) \in R\circ (S\cap T)  \\& \qquad  \Longleftrightarrow \exists z\in X, (x,z)\in S\cap T \land (z,y)\in R  \\& \qquad  \Longleftrightarrow \exists z\in X, [(x,z)\in S \land (x,z)\in T] \land (z,y)\in R  \\& \qquad  \Longleftrightarrow \exists z\in X, [(x,z)\in S \land (z,y)\in R] \land (x,z)\in T \\& \qquad  \Longleftrightarrow \exists z\in X, [(x,z)\in S \land (z,y)\in R] \land [(x,z)\in T \land (z,y)\in R] \\& \qquad  \Longrightarrow [\exists z\in X, [(x,z)\in S \land (z,y)\in R]   \land [ \exists w\in X, (x,w)\in T \land (w,y)\in R] \\& \qquad  \Longleftrightarrow (x,y)\in R\circ S \land (x,y)\in R\circ T  \\& \qquad  \Longleftrightarrow (x,y)\in (R\circ S) \cap (R\circ T) \end{align*}

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $R\subseteq S \implies R\circ T \subseteq S\circ T$.

Proof. The proof follows from the following statements. \begin{align*} & (x,y)\in R\circ T  \Longleftrightarrow \exists z\in X, (x,z)\in T \land (z,y)\in R  \\ &  \qquad \Longrightarrow \exists z\in X, (x,z)\in T \land (z,y)\in S  \Longleftrightarrow (x,y)\in S\circ T \end{align*}

Theorem. If $R$, $S$ and $T$ are relations on $X$, then $R\subseteq S \implies T\circ R \subseteq T\circ S$.

Proof. The proof follows from the following statements. \begin{align*} & (x,y)\in T\circ R  \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in T \\ & \qquad \Longrightarrow \exists z\in X, (x,z)\in S \land (z,y)\in T  \Longleftrightarrow (x,y)\in T\circ S \end{align*}

Definition. Let $R$ and $S$ be relations on $X$. The inverse of $R$ is the relation $$R^{-1}=\{(b,a)\in X\times X : (a,b)\in R\}.$$

Theorem. If $R$ and $S$ are relations on $X$, then $(R^{-1})^{-1}=R$.

Proof. $$ (x,y)\in (R^{-1})^{-1} \Longleftrightarrow (y,x)\in R^{-1} \Longleftrightarrow (x,y)\in R $$

Theorem.If $R$ and $S$ are relations on $X$, then $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$.

Proof. \begin{align*} & (x,y)\in (R\cup S)^{-1} \Longleftrightarrow (y,x)\in R\cup S \Longleftrightarrow (y,x)\in R \lor (y,x)\in S \\ & \qquad  \Longleftrightarrow (x,y)\in R^{-1} \lor (x,y)\in S^{-1}  \Longleftrightarrow (x,y)\in R^{-1}\cup S^{-1} \end{align*}

Theorem. If $R$ and $S$ are relations on $X$, then $(R\cap S)^{-1}=R^{-1}\cap S^{-1}$.

Proof. \begin{align*} & (x,y)\in (R\cap S)^{-1}  \Longleftrightarrow (y,x)\in R\cap S  \Longleftrightarrow (y,x)\in R \land (y,x)\in S \\ &  \qquad  \Longleftrightarrow (x,y)\in R^{-1} \land (x,y)\in S^{-1}  \Longleftrightarrow (x,y)\in R^{-1}\cap S^{-1} \end{align*}

Theorem. If $R$ and $S$ are relations on $X$, then $(R\circ S)^{-1}=S^{-1}\circ R^{-1}$.

Proof. \begin{align*} & (x,y)\in (R\circ S)^{-1}  \Longleftrightarrow (y,x)\in R\circ S \\ & \qquad  \Longleftrightarrow \exists z\in X, (y,z)\in S \land (z,x)\in R \\ &  \qquad  \Longleftrightarrow \exists z\in X, (z,y)\in S^{-1} \land (x,z)\in R^{-1} \\ & \qquad  \Longleftrightarrow \exists z\in X, (x,z)\in R^{-1} \land (z,y)\in S^{-1} \\ &  \qquad  \Longleftrightarrow (x,y)\in S^{-1} \circ R^{-1} \end{align*}

Theorem. If $R$ and $S$ are relations on $X$, then $R\subseteq S \implies R^{-1}\subseteq S^{-1}$. 

Proof. If $R\subseteq S$, then $R^{-1}\subseteq S^{-1}$.  \begin{align*} (x,y)\in & R^{-1}  \Longleftrightarrow (y,x)\in R \Longrightarrow (y,x)\in S \Longleftrightarrow (x,y) \in S^{-1} \end{align*}

Theorem. If $R$ and $S$ are relations on $X$, then $(R^c)^{-1}=(R^{-1})^c$.

Proof. \begin{align*} & (x,y)\in (R^c)^{-1}  \Longleftrightarrow (y,x)\in R^c \Longleftrightarrow (y,x)\in X\times X \land (y,x)\notin R\\ & \qquad \Longleftrightarrow (x,y)\in X\times X \land (x,y)\notin R^{-1}  \Longleftrightarrow (x,y)\in (R^{-1})^c \end{align*}

Theorem. If $R$ and $S$ are relations on $X$, then $(R\setminus S)^{-1}=R^{-1}\setminus S^{-1}$.

Proof. \begin{align*} & (x,y)\in (R\setminus S)^{-1}  \Longleftrightarrow (y,x)\in R\setminus S  \Longleftrightarrow (y,x)\in R \land (y,x)\notin S \\ & \qquad \Longleftrightarrow (x,y)\in R^{-1} \land (y,x)\notin S \Longleftrightarrow (x,y)\in R^{-1} \land (x,y)\notin S^{-1} \\ & \qquad  \Longleftrightarrow (x,y)\in R^{-1}\setminus S^{-1} \end{align*}

Definition. Let $R$ and $S$ be relations on $X$. The image of $A\subseteq X$ under $R$ is the set $$R(A)=\{y\in X : \exists \, x\in A, (x,y)\in R\}.$$

Theorem. If $R$ and $S$ are relations on $X$ and $A, B\subseteq X$, then $A\subseteq B \implies R(A)\subseteq R(B)$.

Proof. If $A\subseteq B$, then $R(A)\subseteq R(B)$.  \begin{align*} \qquad  y\in R(A) \Longleftrightarrow \exists x\in A, (x,y)\in R \implies \exists x\in B, (x,y)\in R \Longleftrightarrow y\in R(B) \end{align*}

Theorem. If $R$ and $S$ are relations on $X$ and $A, B\subseteq X$, then $R(A\cup B)=R(A)\cup R(B)$.

Proof. \begin{align*} \qquad & y\in R(A\cup B)  \Longleftrightarrow \exists x\in X, x\in A\cup B \land (x,y)\in R \\ & \qquad \Longleftrightarrow  \exists x\in X, (x\in A \lor x\in B) \land (x,y)\in R \\ & \qquad \Longleftrightarrow  \exists x\in A, (x,y)\in R \lor \exists x\in B, (x,y)\in R \Longleftrightarrow  y\in R(A) \cup R(B)\end{align*}

Theorem. If $R$ and $S$ are relations on $X$ and $A, B\subseteq X$, then $R(A\cap B)\subseteq R(A)\cap R(B)$.

Proof. \begin{align*} \qquad & y\in R(A\cap B) \Longleftrightarrow \exists x\in X, x\in A\cap B \land (x,y)\in R \\ & \qquad \Longleftrightarrow  \exists x\in X, (x\in A \land x\in B) \land (x,y)\in R \\ & \qquad \Longrightarrow  \exists x\in A, (x,y)\in R \land \exists x\in B, (x,y)\in R \Longleftrightarrow  y\in R(A) \cap R(B) \end{align*}

Theorem. If $R$ and $S$ are relations on $X$ and $A, B\subseteq X$, then $R(A)\setminus R(B)\subseteq R(A\setminus B)$.

Proof. \begin{align*} y\in R(A)\setminus R(B)  & \Longleftrightarrow y\in R(A)\land y\not\in R(B) \\ & \Longleftrightarrow \exists x\in A, (x,y)\in R \land \forall z\in B, (z,y)\not\in R \\ & \Longleftrightarrow \exists x\in A\setminus B, (x,y)\in R \Longleftrightarrow y\in R(A\setminus B) \end{align*}

Theorem. If $R$ and $S$ are relations on $X$ and $R(x)=S(x)$ for all $x\in X$, then $R=S$.

Proof. Assume $R(x)=S(x)$ for all $x\in X$, then $$ (x,y)\in R \Longleftrightarrow y\in R(x)  \Longleftrightarrow y\in S(x)  \Longleftrightarrow (x,y)\in S $$ completes the proof.

Definition. Let $R$ and $S$ be relations on $X$. The preimage of $B\subseteq X$ under $R$ is the set $$R^{-1}(B)=\{x\in X : \exists y\in B, (x,y)\in R\}.$$

Theorem. Let $R$ be a relation on $X$ with $A, B\subseteq X$. Then $A\subseteq B \implies R^{-1}(A)\subseteq R^{1-}(B)$.

Proof. \begin{align*} x\in R^{-1}(A) & \Longleftrightarrow \exists y\in A, (x,y)\in R \\ & \implies \exists y\in B, (x,y)\in R  \Longleftrightarrow x\in R^{-1}(B) \end{align*}

Theorem. Let $R$ be a relation on $X$ with $A, B\subseteq X$. Then $R^{-1}(A\cup B)=R^{-1}(A)\cup R^{-1}(B)$.

Proof. \begin{align*} & x\in R^{-1}(A\cup B)  \Longleftrightarrow \exists y \in A\cup B, (x,y)\in R  \\ & \qquad \Longleftrightarrow \exists y\in A, (x,y)\in R \lor \exists y\in B, (x,y)\in R \\ & \qquad  \Longleftrightarrow x\in R^{-1}(A)\lor R^{-1}(B)  \Longleftrightarrow x\in R^{-1}(A)\cup R^{-1}(B) \end{align*}

Theorem. Let $R$ be a relation on $X$ with $A, B\subseteq X$. Then $R^{-1}(A\cap B)\subseteq R^{-1}(A)\cap R^{-1}(B)$.

Proof. \begin{align*} & x\in R^{-1}(A\cap B)  \Longleftrightarrow \exists y\in A \cap B, (x,y)\in R \\ & \qquad \Longleftrightarrow \exists y\in X, y\in A \land y\in B \land (x,y)\in R \\ & \qquad \Longrightarrow  x\in R^{-1}(A) \land x\in R^{-1}(B) \Longleftrightarrow x\in R^{-1}(A) \cap x\in R^{-1}(B)\end{align*}

Theorem. Let $R$ be a relation on $X$ with $A, B\subseteq X$. Then $R^{-1}(A)\setminus R^{-1}(B)\subseteq R^{-1}(A\setminus B)$.

Proof. \begin{align*} & x\in R^{-1}(A)\setminus R^{-1}(B)\Longleftrightarrow  x\in R^{-1}(A) \land \neg(x\in R^{-1}(B))\\ & \qquad \Longleftrightarrow  x\in R^{-1}(A)\land [\forall y\in B, (x,y)\not\in R] \\ & \qquad \Longleftrightarrow  \exists y\in A, (x,y)\in R \land [\forall y\in B, (x,y)\not\in R]\\ & \qquad \Longrightarrow \exists y\in A\setminus B, (x,y)\in R \Longleftrightarrow x\in R^{-1}(A\setminus B)\end{align*}

Theorem. Let $R$ and $R_i$ be relations on $X$ for $i\in I$ where $I$ is an indexed set. Then $R\circ \left(\bigcup_{i\in I} R_i\right)=\bigcup_{i\in I}(R\circ R_i)$.

Proof. \begin{align*} (x,y)\in R\circ \left(\bigcup_{i\in I} R_i\right)  & \Longleftrightarrow  \exists z\in X, (x,z)\in \bigcup_{i\in I} R_i \land (z,y)\in R \\ & \Longleftrightarrow \exists z\in X, \exists i\in I, (x,z)\in R_i \land (z,y)\in R \\ & \Longleftrightarrow \exists i\in I, (x,y)\in R\circ R_i  \\ & \Longleftrightarrow (x,y) \in \bigcup_{i\in I}(R\circ R_i) \end{align*}

Theorem. Let $R$ and $R_i$ be relations on $X$ for $i\in I$ where $I$ is an indexed set. Then $\left(\bigcup_{i\in I} R_i\right)\circ R=\bigcup_{i\in I}(R_i\circ R)$.

Proof. \begin{align*} (x,y)\in \left(\bigcup_{i\in I} R_i\right)\circ R & \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in \bigcup_{i\in I} R_i \\ & \Longleftrightarrow \exists z\in X, \exists i\in I, (x,z)\in R \land (z,y)\in R_i \\ & \Longleftrightarrow (x,y)\in \bigcup_{i\in I}(R_i\circ R) \end{align*}

Theorem. Let $R$ be a relation on $X$. Then $(R^n)^{-1}=(R^{-1})^n$ for all $n\geq 1$.

Proof. By induction.  The basis step is obvious: $(R^{1})^{-1}=(R^{-1})^1$.  In fact, $(R^2)^{-1}=(R\circ R)^{-1}=R^{-1}\circ R^{-1}=(R^{-1})^2$.  The induction step is $$(R^n)^{-1}=(R^{-1})^n\implies (R^{n+1})^{-1}=(R^{-1})^{n+1}. $$ The result now follows from the argument: \begin{align*} (x,y)\in (R^{n+1})^{-1}  & \Longleftrightarrow (y,x)\in R^{n+1} \\ & \Longleftrightarrow \exists z\in X, (y,z)\in R \land (z,x)\in R^n \\ & \Longleftrightarrow \exists z\in X, (z,y)\in R^{-1} \land (x,z)\in (R^n)^{-1}\\ & \Longleftrightarrow \exists z\in X, (x,z)\in (R^n)^{-1} \land (z,y)\in R^{-1}\\ & \Longleftrightarrow \exists z\in X, (x,z)\in (R^{-1})^n \land (z,y)\in R^{-1} \\ & \Longleftrightarrow (x,y)\in (R^{-1})^{n+1} \end{align*}

Theorem. Let $R$ be a relation on $X$. Then $\left( \bigcup_{n\geq 1} R^n \right)^{-1} = \bigcup_{n\geq 1} (R^{-1})^{n}$.

Proof. \begin{align*} (x,y)\in & \left( \bigcup_{n\geq 1} R^n \right)^{-1}  \Longleftrightarrow (y,x)\in \bigcup_{n\geq 1} R^n \\ & \Longleftrightarrow \exists n\geq 1, (y,x)\in R^n =R^{n-1}\circ R \\ & \Longleftrightarrow \exists n\geq 1, \exists z\in X, (y,z)\in R \land (z,x)\in R^{n-1} \\ & \Longleftrightarrow \exists n\geq 1, \exists z\in X, (z,y)\in R^{-1} \land (x,z)\in (R^{n-1})^{-1}\\ & \Longleftrightarrow \exists n\geq 1, \exists z\in X, (x,z)\in (R^{n-1})^{-1} \land (z,y)\in R^{-1}  \\ & \Longleftrightarrow \exists n\geq 1, \exists z\in X, (x,z)\in (R^{-1})^{n-1} \land (z,y)\in R^{-1}  \\ & \Longleftrightarrow \exists n\geq 1, (x,y)\in (R^{-1})^n  \Longleftrightarrow (x,y)\in \bigcup_{n\geq 1}(R^{-1})^n \end{align*}

Theorem. Let $R$ be a relation on $X$. Then $R^n \cup S^n\subseteq (R\cup S)^n$ for all $n\geq 1$.

Proof. The basis step is obvious. The induction step is: $$R^n \cup S^n\subseteq (R\cup S)^n \implies R^{n+1} \cup S^{n+1}\subseteq (R\cup S)^{n+1} $$ The result holds by  \begin{align*} (R\cup S)^{n+1} & =(R\cup S)^n\circ (R\cup S)  \\ & \supseteq (R^n\cup S^n) \circ (R \cup S) \\ & = [(R^n\cup S^n)\circ R] \cup (R^n\cup S^n) \circ S \\ & = R^{n+1} \cup (S^n \circ R) \cup (R^n\circ S) \cup S^{n+1}  \\ & \supseteq R^{n+1}\cup S^{n+1}. \end{align*}

Theorem. Let $R$ be a relation on $X$.  Then $(x,y)\in R^n$ if and only if there exists $x_1, x_2, x_3, \ldots, x_{n-1}\in X$ such that $(x,x_1)\in R, (x_1,x_2)\in R , \ldots, (x_{n-1},y)\in R$.

Proof. Bases case, $i=1$ is obvious.  We assume the claim is true for $j$.  Then \begin{align*}& (x,y)\in R^{j+1}  \Longleftrightarrow (x,y)\in R^j\circ R\\ & \Longleftrightarrow \exists x_1\in X, (x,x_1)\in R \land (x_1,y)\in R^j \\ & \Longleftrightarrow \exists x_1\in X, (x,x_1)\in R \land \exists x_2, \ldots, x_{j-1}\in X, (x_2, x_3), \ldots, (x_{j-1},y)\in R \\ & \Longleftrightarrow  \exists x_1\in X, x_2, \ldots, x_{j-1}\in X, (x,x_1), (x_2, x_3), \ldots, (x_{j-1},y)\in R  \end{align*} as needed to complete induction.