Skip to main content

Section B.4 Binary 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{.}\)

Example B.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.

Example B.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?).