## 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=[4]$$ and $$Y=[5]\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?).