Relations and Functions

A binary relation from $A$ to $B$ is a subset of $A \times B$. It is a characterization of the intuitive notion that some of the elements of $A$ are related to some of the elements of $B$. Familiar binary relations from $\mathbb{N}$ to $\mathbb{N}$ are $=,\;\neq,\;<,\;\leq,\;>,\;\geq$. Thus the elements of the set $\{(0,0),(0,1),(0,2),\ldots,(1,1),(1,2),\ldots\}$ are all members of the relation $\leq$ which is a subset of $\mathbb{N}\times \mathbb{N}$.

In general, an n-ary relation among the sets $A_1,A_2,\ldots,A_n$ is a subset of the set $A_1 \times A_2 \times \cdots \times A_n$.

A function from $A$ to $B$ is a binary relation $R$ from $A$ to $B$ such that for every element $a \in A$ there is a unique element $b \in B$ so the $(a,b) \in R$ ($R(a) = b$). We will use the notation $R: A \rightarrow B$ to denote a function $R$ from $A$ to $B$. The set $A$ is called the domain of the function $R$ and the set $B$ is called the co-domain of the function $R$. The range of a function $R: A \rightarrow B$ is the set $\{b \in B \mid$   for some $a \in A$, $R(a) = b$$\}$. Some familiar examples of functions are

1. $+$ and $*$ (addition and multiplication) are functions of the type $f: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$
2. $-$ (subtraction) is a function of the type $f: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{Z}$.
3. $div$ and $mod$ are functions of the type $f: \mathbb{N}\times \mathbb{P}\rightarrow \mathbb{N}$. If $a = q*b + r$ such that $0 \leq r < b$ and $a,b,q,r \in \mathbb{N}$ then the functions $div$ and $mod$ are defined as $div(a,b) = q$ and $mod(a,b) = r$. We will often write these binary functions as $a * b$, $a\; div \;b$, $a \; mod \; b$ etc.
4. The binary relations $=,\;\neq,\;<,\;\leq,\;>,\;\geq$ are also functions of the type $f: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{B}$ where $\mathbb{B}= \{false,true\}$.