Introduction

Definition

Let A and B be sets. A binary relation from A to B is a subset of $A\times B$

INFO

We use the notation $aRb$ to denote that $(a,b)\in R$ and $a\mathrm{R̸}b$ to denote that $(a,b)\notin R$. Moreover, when (a, b) belongs to R, a is said to be related to b by R.

• Relations are a generalization of graphs of functions

Relations on a Set

Definition

• A relation on a set A is a relation from A to A.
• In other words, a relation on a set A is a subset of $A\times A$.

Properties of Relations

Reflexive

Definition

A relation R on a set A is called reflexive if $(a,a)\in R$ for every element $a\in A$.

Remark

Using Quantifier, we see that the relation R on the set A is reflexive if

$$\mathrm{\forall }a((a,a)\in R)$$

where the universe of discourse is the set of all elements in A.

• Example:
  • Relation R on set $A=\{1,2,3,4\}$
  • $R=\{(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)\}$ is reflexive, but
  • $R=\{(1,1),(1,2),(1,4)\}$ isn't relexive

Symmetric

Definition

A relation R on a set A is called symmetric if $(b,a)\in R$ whenever $(a,b)\in R$, for all a, $b\in A$.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

$$\mathrm{\forall }a\mathrm{\forall }b((a,b)\in R\to (b,a)\in R).$$

• Example:
  • Relation R on set $A=\{1,2\}$
  • $R=\{(1,2),(2,1)\}$ is symmetric,

Antisymmetric

Definition

A relation R on a set A is called antisymmetric if $(a,b)\in R$ and $(b,a)\in R$, then $a=b$, for all a, $b\in A$.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

$$\mathrm{\forall }a\mathrm{\forall }b((a,b)\in R\wedge (b,a)\in R\to (a=b)$$

• Example:
  • Relation R on set $A=\{1,2\}$
  • $R=\{(1,1),(1,2)\}$ is antisymmetric

Transitive

Definition

A relation R on a set A is called transitive if whenever $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$, for all $a,b,c\in A$.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

$$\mathrm{\forall }a\mathrm{\forall }b\mathrm{\forall }c((a,b)\in R\wedge (b,c)\in R\to (a,c)\in R)$$

• Example:
  • Relation R on set $A=\{1,2,3\}$
  • $R=\{(1,3),(3,2),(1,2)\}$ is transitive

Combining Relations

TIP

Two relations from A to B can be combined in any way two sets can be combined

Composite definition

• Given two relations R and S from A to B:

  • R: relation from $A\to B$
  • S: relation from $B\to C$

• Composite $S\circ R$ is relation from $A\to C$ including $(a,c)$ that there exists an element $b\in B$ such that:

$$(a,b)\in R\text{ and }(b,c)\in S$$

• Example:

The powers of a relation R

INFO

Let R be a relation on the set A. The powers $R^n$, n = 1, 2, 3, ..., are recursively defined by

BASIS STEP:

$$R^1=R$$

RECURSIVE STEP:

$$R^{n+1}=R^n\circ R$$

Theorem 1

INFO

The relation R on a set A is transitive if and only if $R^n\subseteq R$ for n = 1, 2, 3, ...

Inverse relation of R

INFO

Let $R^{-1}$ be a reverse of relation $R$:

$$R^{-1}=\{(b,a)|(a,b)\in R\}$$

Complementary relation of R

INFO

Let $\bar{R}$ be a complement of relation $R$:

$$\bar{R}=\{(a,b)|(a,b)\notin R\}$$

Representing relations

Using Matrices

• The relation $R$ can be represented by the matrix $M_R=[m_{ij}]$, where

INFO

$$m_{ij}=\{\begin{array}{ll}1& \text{if }(a_i,b_j)\in R\\ 0& \text{if }(a_i,b_j)\notin R\end{array}$$

Relfexive relations

• The relation $R$ is self-reflexive if $m_{ii}=1$ for all $i\in R$.

TIP

$$\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & ...& \\ & & & 1\end{array}\right]$$

Off diagonal elements can be 0 or 1

Symmetric relations

• The relation $R$ is symmetric if $m_{ij}=m_{ji}$ for all $i,j\in R$.

TIP

$$M_R=(M_R{)}^t$$

Antisymmetric relations

• The relation $R$ is antisymmetric if $m_{ij}=0\vee m_{ji}=0$ when $i\ne j$.

Using Digraphs