# 2.1: Binary Relations

$$\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}}$$

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$$.

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

Example $$\PageIndex{2}$$:

1. Define $$R$$ by $$a R b$$ if and only if $$a < b$$, for $$a, b \in \mathbb{Z}$$.
2. Define $$R$$ by $$a R b$$ if and only if $$a >b$$, for $$a, b \in \mathbb{Z}$$.
3. Define $$R$$ by $$a R b$$ if and only if $$a \leq b$$, for $$a, b \in \mathbb{Z}$$.
4. Define $$R$$ by $$a R b$$ if and only if $$a \geq b$$, for $$a, b \in \mathbb{Z}$$.
5. 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  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

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

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

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

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

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

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

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

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

This page titled 2.1: Binary Relations is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.