## SectionB.4Binary Relations and Functions

A subset $R\subseteq X\times Y$ is called a binary relation on $X\times Y\text{,}$ and a binary relation $R$ on $X\times Y$ is called a function from $X$ to $Y$ when for every $x\in X\text{,}$ there is exactly one element $y\in Y$ for which $(x,y)\in R\text{.}$

Many authors prefer to write the condition for being a function in two parts:

1. For every $x\in X\text{,}$ there is some element $y\in Y$ for which $(x,y)\in R\text{.}$

2. For every $x\in X\text{,}$ there is at most one element $y\in Y$ for which $(x,y)\in R\text{.}$

The second condition is often stated in the following alternative form: If $x\in X\text{,}$ $y_1,y_2\in Y$ and $(x,y_1),(x,y_2)\in R\text{,}$ then $y_1=y_2\text{.}$

###### ExampleB.4.

For example, let $X=$ and $Y=\text{.}$ Then let

\begin{align*} R_1\amp =\{(2,1),(4,2),(1,1),(3,1)\}\\ R_2\amp =\{(4,2),(1,5),(3,2)\}\\ R_3\amp=\{(3,2),(1,4),(2,2),(1,1),(4,5)\} \end{align*}

Of these relations, only $R_1$ is a function from $X$ to $Y\text{.}$

In many settings (like calculus), it is customary to use letters like $f\text{,}$ $g$ and $h$ to denote functions. So let $f$ be a function from a set $X$ to a set $Y\text{.}$ In view of the defining properties of functions, for each $x\in X\text{,}$ there is a unique element $y\in Y$ with $(x,y)\in f\text{.}$ And in this case, the convention is to write $y=f(x)\text{.}$ For example, if $f=R_1$ is the function in Example B.4, then $2=f(4)$ and $f(3) =1\text{.}$

The shorthand notation $f:X\rightarrow Y$ is used to indicate that $f$ is a function from the set $X$ to the set $Y\text{.}$

In calculus, we study functions defined by algebraic rules. For example, consider the function $f$ whose rule is $f(x) = 5x^3-8x+7\text{.}$ This short hand notation means that $X=Y=\reals$ and that

\begin{equation*} f=\{(x,5x^3-8x+7):x\in\reals\} \end{equation*}

In combinatorics, we sometimes study functions defined algebraically, just like in calculus, but we will frequently describe functions by other kinds of rules. For example, let $f:\posints\rightarrow\posints$ be defined by $f(n) = |n/2|$ if $n$ is even and $f(n)=3|n|+1$ when $n$ is odd.

A function $f:X\rightarrow Y$ is called an injection from $X$ to $Y$ when for every $y\in Y\text{,}$ there is at most one element $x\in X$ with $y=f(x)\text{.}$

When the meaning of $X$ and $Y$ is clear, we just say $f$ is an injection. An injection is also called a $1$–$1$ function (read this as “one to one”) and this is sometimes denoted as $f:X\injection Y\text{.}$

A function $f:X\rightarrow Y$ is called a surjection from $X$ to $Y$ when for every $y\in Y\text{,}$ there is at least one $x\in X$ with $y=f(x)\text{.}$

Again, when the meaning of $X$ and $Y$ is clear, we just say $f$ is a surjection. A surjection is also called an onto function and this is sometimes denoted as $f:X\surjection Y\text{.}$

A function $f$ from $X$ to $Y$ which is both an injection and a surjection is called a bijection. Alternatively, a bijection is referred to as a $1$–$1\text{,}$ onto function, and this is sometimes denoted as $f:X \bijection Y$. A bijection is also called a $1$–$1$-correspondence.

###### ExampleB.5.

Let $X=Y=\reals\text{.}$ Then let $f\text{,}$ $g$ and $h$ be the functions defined by

1. $f(x)=3x-7\text{.}$
2. $g(x)=3(x-2)(x+5)(x-7)\text{.}$
3. $h(x)=6x^2-5x+13\text{.}$

Then $f$ is a bijection; $g$ is a surjection but not an injection (Why?); and $h$ is neither an injection nor a surjection (Why?).