Binary Relations

Binary Relations (Types and Properties)


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

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.

5/5 (1 Review)

Leave a Comment

Scroll to Top