2.1: Binary Relations

Last updated
Save as PDF

Page ID: 7426

This page is a draft and is under active development.

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Definition: Binary Relation

Let $S$ be a non-empty set. Then any subset $R$ of $S \times S$ is said to be a relation over $S$. In other words, a relation is a rule that is defined between two elements in $S$. Intuitively, if $R$ is a relation over $S$, then the statement $a R b$ is either true or false for all $a,b\in S$.

If the statement $a R b$ is false, we denote this by $ a \not R b$.

Example $\PageIndex{1}$:

Let $S=\{1,2,3\}$. Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in S$.

Then $1 R 2, 1 R 3, 2 R 3 $ and $ 2 \not R 1$.

We can visualize the above binary relation as a graph, where the vertices are the elements of S, and there is an edge from $a$ to $b$ if and only if $a R b$, for $a b\in S$.

$sog8mVfmrjo7_-GoB-mBjEQ.png$

The following are some examples of relations defined on $\mathbb{Z}$.

Example $\PageIndex{2}$:

Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in \mathbb{Z}$.
Define $R$ by $a R b$ if and only if $a >b$, for $a, b \in \mathbb{Z}$.
Define $R$ by $a R b$ if and only if $a \leq b$, for $a, b \in \mathbb{Z}$.
Define $R$ by $a R b$ if and only if $a \geq b$, for $a, b \in \mathbb{Z}$.
Define $R$ by $a R b$ if and only if $a = b$, for $a, b \in \mathbb{Z}$.

Multiples and divisors

Next, we will introduce the notion of "divides."

Definition: Divisor/Divides

Let $ a$ and $b$ be integers. We say that $a$ divides $b$ is denoted $a\mid b$, provided we have an integer $m$ such that $b=am$. In this case we can also say the following:

$b$ is divisible by $a$
$a$ is a factor of $b$
$a$ is a divisor of $b$
$b$ is a multiple of $a$

If $a$ does not divide $b$, then it is denoted by $a \not \mid b$.

Example $\PageIndex{3}$:

Find all positive integers divisible by $16.$

Solution

Multiples of $16. $

Example $\PageIndex{4}$:

Find all positive integers divides $16.$

Solution

$1, 2, 4, 8, 16$

Example $\PageIndex{5}$:

$4 \mid 12$ and $12 \not\mid 4$

Next, we will introduce the notion of "divides" for positive integers.

Definition: Divides

Let $ a$ and $b$ be positive integers. We say that $a$ divides $b$ is denoted $a\mid b$, there exists a positive integer $m$ such that $b=am$.

Theorem $\PageIndex{1}$: Divisibility inequality theorem

If $a\mid b$, for $a, b \in \mathbb{Z_+}$ then $a \leq b$,

Proof: Let $a, b \in \mathbb{Z_+}$ such that $a\mid b$, Since (a\mid b\), there is a positive integer $m$ such that $b=am$. Since $m \geq 1$ and $a$ is a positive integer, $b=am \geq (a)(1)=a. $

Note that if $a\mid b$, for $a, b \in \mathbb{Z_+}$ then $a \leq b$, but the converse is not true. For example: $2 <3$, but $2 \not\mid 3$.

Example $\PageIndex{6}$:

According to our definition $0 \mid 0$.

Definition: Even integer

An integer is even provided that it is divisible by $2$.

Properties of binary relation:

Definition: Reflexive

Let $S$ be a set and $R$ be a binary relation on $S$. Then $R$ is said to be reflexive if $ a R a, \forall a \in S.$

Example $\PageIndex{5}$: Visually

$Pamini Thangarajah$

$\forall a \in S, a R a$ holds.

We will follow the template below to answer the question about reflexive.

$alt$

Example $\PageIndex{7}$:

Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in \mathbb{Z}$. Is $R$ reflexive?

Counter Example:

Choose $a=2.$

Since $ 2 \not< 2$, $R$ is not reflexive.

Example $\PageIndex{8}$:

Define $R$ by $a R b$ if and only if $a \mid b$, for $a, b \in \mathbb{Z}$. Is $R$ reflexive?

Proof:

Let $ a \in \mathbb{Z}$. Since $a=(1) (a)$, $a \mid a$.

Thus $R$ is reflexive. $ \Box$

Definition: Symmetric

Let $S$ be a set and $R$ be a binary relation on $S$. Then $R$ is said to be symmetric if the following statement is true:

$ \forall a,b \in S$, if $ a R b $ then $b R a$, in other words, $ \forall a,b \in S, a R b \implies b R a.$

Example $\PageIndex{8}$: Visually

$alt$

$\forall a,b \in S, a R b \implies b R a.$ holds!

We will follow the template below to answer the question about symmetric.

$stXO_6c-DcCh0t5duFY2Ejw.png$

Example $\PageIndex{9}$:

Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in \mathbb{Z}$. Is $R$ symmetric?

Counter Example:

$1<2$ but $2 \not < 1$.

Example $\PageIndex{10}$:

Define $R$ by $a R b$ if and only if $a \mid b$, for $a, b \in \mathbb{Z}$. Is $R$ symmetric?

Counter Example:

$2 \mid 4$ but $4 \not \mid 2$.

Definition: Antisymmetric

Let $S$ be a set and $R$ be a binary relation on $S$. Then $R$ is said to be antisymmetric if the following statement is true:

$ \forall a,b \in S$, if $ a R b $ and $b R a$, then $a=b$.

In other words, $ \forall a,b \in S$, $ a R b \wedge b R a \implies a=b.$

Example $\PageIndex{11}$: VISUALLY

$alt$

$ \forall a,b \in S$, $ a R b \wedge b R a \implies a=b $ holds!

We will follow the template below to answer the question about anti-symmetric.

$alt$

Example $\PageIndex{12}$:

Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in \mathbb{Z}$. Is $R$ antisymmetric?

Example $\PageIndex{13}$:

Define $R$ by $a R b$ if and only if $a \mid b$, for $a, b \in \mathbb{Z_+}$. Is $R$ antisymmetric?

Definition: Transitive

Let $S$ be a set and $R$ be a binary relation on $S$. Then $R$ is said to be transitive if the following statement is true

$ \forall a,b,c \in S,$ if $ a R b $ and $b R c$, then $a R c$.

In other words, $ \forall a,b,c \in S$, $ a R b \wedge b R c \implies a R c$.

Example $\PageIndex{14}$: VISUALLY

$alt$

$ \forall a,b,c \in S$, $ a R b \wedge b R c \implies a R c$ holds!

We will follow the template below to answer the question about transitive.

$ssUmTK4d9hHGQc-mZjO6p5g.png$

Example $\PageIndex{15}$:

Define $R$ by $a R b$ if and only if $a < b$, for $a, b \in \mathbb{Z}$. Is $R$ transitive?

Example $\PageIndex{16}$:

Define $R$ by $a R b$ if and only if $a \mid b$, for $a, b \in \mathbb{Z_+}$. Is $R$ transitive?

Summary:

In this section, we learned about binary relations and the following properties:

Reflexive

Symmetric

Antisymmetric

Transitive

Search

Text Color

Text Size

Margin Size

Font Type

Example \(\PageIndex{3}\):

Example \(\PageIndex{4}\):

Definition: Divides