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:
For every \(x\in X\text{,}\) there is some element \(y\in Y\) for which \((x,y)\in R\text{.}\)
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
\(f(x)=3x-7\text{.}\)
\(g(x)=3(x-2)(x+5)(x-7)\text{.}\)
\(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?).
Proposition B.6.
Let \(X\) and \(Y\) be sets. Then there is a bijection from \(X\) to \(Y\) if and only if there is a bijection from \(Y\) to \(X\text{.}\)
