Let \(X\) and \(Y\) be two nonempty sets. A function \(f\) from \(X\) to \(Y\) is a subset of \(X\times Y\) such that for every \(x\in X\text{,}\) there exists a unique \(y\in Y\) such that \((x,y)\in f\text{.}\) The set \(X\) is called the domain of \(f\) and is denoted by \({\dom(f)}\text{.}\) The set \(Y\) is called the codomain of \(f\) and is denoted by \({\codom(f)}\) while the subset of the codomain defined via
\begin{equation*}
{\range(f)\:= \{y\in Y\mid \mbox{there exists } x\mbox{ such that } (x,y)\in f\}}
\end{equation*}
is called the range of \(f\) or the image of \(X\) under \(f\text{.}\)
There is a variety of notation and terminology associated to functions. We will write \({f:X\to Y}\) to indicate that \(f\) is a function from \(X\) to \(Y\text{.}\) We will make use of statements such as “Let \(f:X\to Y\) be the function defined via…” or “Define \(f:X\to Y\) via…”, where \(f\) is understood to be a function in the second statement. Sometimes the word mapping (or map) is used in place of the word function. If \((x,y)\in f\) for a function \(f\text{,}\) we often write \({f(x)=y}\) and say that “\(f\) maps \(x\) to \(y\)” or “\(f\) of \(x\) equals \(y\)”. In this case, \(x\) may be called an input of \(f\) and is the preimage of \(y\) under \(f\) while \(y\) is called an output of \(f\) and is the image of \(x\) under \(f\text{.}\) Note that the domain of a function is the set of inputs while the range is the set of outputs for the function.
Sometimes we can represent functions visual representations called function (or mapping) diagrams, where the elements of the domain and codomain are indicated by labeled nodes and ordered pairs for the function are indicated by an arrow pointing from the node for input to the node for the output. When drawing function diagrams, it is standard practice to put the elements for the domain on the left and the elements for the codomain on the right, so that all directed edges point from left to right. We may also draw an additional arrow labeled by the name of the function from the domain to the codomain.
Figure 2.1 depicts a function \(f:X\to Y\) for the sets \(X=\{a,b,c,d\}\) to \(Y=\{1,2,3,4\}\text{.}\) In this case, we see that \(\range(f)=\{1,2,4\}\text{.}\) Moreover, we can write things like \(f(a)=2\) and \(c\mapsto 4\text{,}\) and say things like “\(f\) maps \(b\) to 4” and “the image of \(d\) is 1.” Note that it is perfectly okay to have both \(b\) and \(c\) mapped to 4.
Function diagram for a function from \(X=\{a,b,c,d,\}\) to \(Y=\{1,2,3,4\}\text{,}\) where \(a\) maps to \(2\text{,}\)\(b\) and \(c\) map to \(4\text{,}\) and \(d\) maps to \(1\text{.}\)
Sometimes we can define a function using a formula. For example, we can write \(f(x)=x^2-1\) to mean that each \(x\) in the domain of \(f\) maps to \(x^2-1\) in the codomain. However, notice that providing only a formula is ambiguous! A function is determined by its domain, codomain, and the correspondence between these two sets. If we only provide a description for the correspondence, it is not clear what the domain and codomain are. Two functions that are defined by the same formula, but have different domains or codomains are not equal. It is important to point out that not every function can be described using a formula! Despite your prior experience, functions that can be represented succinctly using a formula are rare.
The function \(f:\mathbb{R}\to \mathbb{R}\) defined via \(f(x)=x^{2}-1\) is not equal to the function \(g:\mathbb{N}\to\mathbb{R}\) defined by \(g(x)=x^{2}-1\) since the two functions do not have the same domain.
Provide an example of each of the following. You may draw a function diagram, write down a list of ordered pairs that represents the assignment, or write a formula as long as the domain and codomain are clear.
A function \(f\) from a set with 4 elements to a set with 3 elements such that \(\range(f)=\codom(f)\text{.}\)
In high school you may have been told that a graph represents a function if it passes the vertical line test. Carefully state what the vertical line test says and then explain why it works.
A piecewise-defined function (or piecewise function) is a function defined by specifying its output on a partition (i.e., “disjoint chunks” ) of the domain. Note that “piecewise” is a way of expressing the function, rather than a property of the function itself.
Let \(n\in\mathbb{N}\text{.}\) Count all functions \(f:\{1,2,\ldots,n\}\to \{0,1\}\text{.}\) How is this problem related to Problem 1.30? How is this problem related to Problem 1.31?
Let \(f:X\to Y\) be a function. We define the following.
The function \(f\) is said to be injective (or one-to-one) if for all \(y\in \range(f)\text{,}\) there is a unique \(x\in X\) such that \(y=f(x)\text{.}\) Said another way, \(f\) is one-to-one provided \(f(x) = f(y)\) implies that \(x = y\text{,}\) or equivalently \(x \ne y\) (in \(X\)) implies \(f(x) \ne f(y)\text{.}\) That is, different inputs produce different outputs.
Assume that \(X\) and \(Y\) are finite sets. Provide an example of each of the following. You may draw a function diagram, write down a list of ordered pairs, or write a formula as long as the domain and codomain are clear.
A function \(f:X\to Y\) that is injective but not surjective.
\begin{equation*}
g(n)=\begin{cases}\frac{n}{2}, \amp \text{ if } n\text{ is even } \\ \frac{n+1}{2}, \amp \text{ if } n\text{ is odd } \end{cases}
\end{equation*}
This statement is often called the horizontal line test. Explain why the horizontal line test is true. What kind of theorems to we get if we replace “at most once” with either “at least once” or “exactly once”?
Let \(A\) denote the set of ways to distribute candy in Problem 1.41 (in the situation where the candy is all identical) and let \(B\) denote the set of sequence of coin flips in Problem 1.28. Find a bijection \(f:A\to B\text{.}\)
In mathematics, we say that an expression is well defined (or unambiguous) if its definition yields a unique interpretation. Otherwise, we say that the expression is not well defined (or is ambiguous). For example, if \(a,b,c\in\mathbb{R}\text{,}\) then the expression \(abc\) is well defined since it does not matter if we interpret this as \((ab)c\) or \(a(bc)\) since the real numbers are associative under multiplication.
When we attempt to define a function, it may not be clear without doing some work that our definition really does yield a function. If there is some potential ambiguity in the definition of a function that ends up not causing any issues, we say that the function is well defined. However, this phrase is a bit of misnomer since all functions are well defined. The issue of whether a description for a proposed function is well defined often arises when defining things in terms of how an element of the domain is written. For example, the descriptions given in Parts (c) and (d) of Problem 2.16 are not well defined.
