You have certainly dealt with functions before, primarily in calculus, where you studied functions from $\R$ to $\R$ or from $\R^2$ to $\R$. Perhaps you have encountered functions in a more abstract setting as well; this is our focus. In the last few sections of the chapter, we use functions to study some interesting topics in set theory.

By a function from a set $A$ to a set $B$ we mean an assignment or rule $f$ such that for every $a\in A$ there is a unique $b\in B$ such that $f(a)=b$. The set $A$ is called the domain of $f$ and the set $B$ is called the codomain. We say two functions $f$ and $g$ are equal if they have the same domain and the same codomain, and if for every $a$ in the domain, $f(a)=g(a)$.

(In the interest of full disclosure of dirty tricks, we should mention that the last paragraph is not really a definition at all! The problem is that the words "assignment'' and "rule'' are synonyms for "function.'' This problem can be "resolved'' by defining functions in terms of sets, but we don't really have a satisfactory definition of "set'' either. For now, all that is needed is an intuitive understanding of the concept and a way of showing two functions are equal.)

We often write $f\colon A\to B$ to indicate that $f$ is a function from $A$ to $B$. Sometimes the word "map'' or "mapping'' is used instead of "function.'' If $f\colon A\to B$ and $f(a)=b$, we say $b$ is the image of $a$ under $f$, and $a$ is a preimage of $b$ under $f$. When the function is clear from context, the phrase `under $f$' may be dropped.

Example 4.1.1 You are familiar with many functions $f\colon \R\to \R$: Polynomial functions, trigonometric functions, exponential functions, and so on. Often you have dealt with functions with codomain $\R$ whose domain is some subset of $\R$. For example, $f(x)=\sqrt x$ has domain $[0,\infty)$ and $f(x)=1/x$ has domain $\{x\in \R : x\ne 0\}$. It is easy to see that a subset of the plane is the graph of a function $f\colon \R\to \R$ if and only if every vertical line intersects it at exactly one point. If this point is $(a,b)$, then $f(a)=b$. $\square$

Example 4.1.2 Functions on finite sets can be defined by listing all the assignments. If $A=\{1,2,3,4\}$ and $B=\{r,s,t,u,v\}$ then "$f(1)= t,f(2)= s,f(3)= u,f(4)= t$'' defines a function from $A$ to $B$. The assignment can be done quite arbitrarily, without recourse to any particular formula. $\square$

Example 4.1.3 The following are not functions from $A=\{1,2,3,4,5\}$ to $B=\{r,s,t,u\}$: $$ \matrix{f(1)= t & \quad & g(1)=u\cr f(2)= s & \quad & g(2)=r\cr f(3)= r & \quad & g(4)=s\cr f(3)= u & \quad & g(5)=t\cr f(4)= u & \quad & \cr f(5)= r & \quad & \cr} $$ The problem is that $f$ maps $3$ to two values and $g$ doesn't map $3$ to any values. When listing the assignments for a function the elements of the domain must appear exactly once. (Elements of the codomain may appear more than once or not at all. In example 4.1.2, the element $t$ of the codomain has two preimages and $r$ and $v$ have none. We will discuss this situation at length in later sections.) $\square$

Example 4.1.4 If $A$ and $B$ are non-empty sets and $b_0$ is a fixed element of $B$, we can define a constant function $f\colon A\to B$ by the formula $f(a)=b_0$ for all $a\in A$. There are as many constant functions from $A$ to $B$ as there are elements of $B$. $\square$

Example 4.1.5 For a set $A$ we define the identity function $i_A\colon A\to A$ by the rule $i_A(a)=a$ for all $a\in A$. In other words, the identity function maps every element to itself. Though this seems like a rather trivial concept, it is useful and important. Identity functions behave in much the same way that 0 does with respect to addition or 1 does with respect to multiplication. $\square$

Example 4.1.6 If $A\subseteq B$, define the inclusion function $f\colon A\to B$ by $f(a)=a$ for every $a\in A$. This is very similar to $i_A$; the only difference is the codomain. $\square$

Definition 4.1.7 If $f\colon A\to B$ and $g\colon B\to C$ are functions, define $g\circ f\colon A\to C$ by the rule $(g\circ f)(a)=g(f(a))$ for all $a\in A$. This is called the composition of the two functions. Observe that $f$ is the first function that is applied to an element $a$ though it is listed on the right. This violation of the usual left-to-right convention sometimes causes confusion. $\square$

Example 4.1.8 If $f\colon \R^+\cup\{0\}\to \R$ is given by $f(x)=\sqrt x$ and $g\colon \R\to\R$ is given by $g(x)=\sin x$, then $g\circ f\colon \R^+\cup\{0\}\to \R$ is given by $(g\circ f)(x)=\sin \sqrt x$. Note that $(f\circ g)(x)=\sqrt{\sin x}$ makes sense only for those $x$ such that $\sin x\ge 0$. In general, $f\circ g$ and $g\circ f$ are not necessarily equal, and (as in this case) they need not be defined at the same points. $\square$

Example 4.1.9 If $A=\{1,2,3,4\}$, $B=\{r,s,t,u\}$, $C=\{\$,\%,\#,\&\}$, and $$ \matrix{ f(1) & = u &\quad g(r)&= \%\cr f(2) & = r &\quad g(s)&= \#\cr f(3) & = s &\quad g(t)&= \$\cr f(4) & = u &\quad g(u)&= \$\cr } $$ then $$ \eqalign{ (g\circ f)(1) & = \$ \cr (g\circ f)(2) & = \% \cr (g\circ f)(3) & = \# \cr (g\circ f)(4) & = \$ \cr} $$ $\square$

Example 4.1.10 If $A\subseteq B$, $f\colon A\to B$ is the inclusion function (example 4.1.6) and $g\colon B\to C$ is a function, then $g\circ f\colon A\to C$ is called the restriction of $g$ to $A$ and is usually written $g\vert_A$. For all $a\in A$, $$ g\vert_A(a)=g(f(a))=g(a), $$ so $g\vert_A$ is just the same function as $g$ with a smaller domain. $\square$

The following is an easy but important observation:

Theorem 4.1.11 If $f\colon A\to B$ then $f\circ i_A=f=i_B\circ f$.

Proof. All three functions have domain $A$ and codomain $B$. For every $a\in A$, $$ (f\circ i_A)(a)=f(i_A(a))=f(a)=i_B(f(a))=(i_B\circ f)(a). $$$\qed$

A similar argument shows that whenever it is defined, composition of functions is associative, i.e., $(f\circ g)\circ h=f\circ (g\circ h)$ (see exercise 7).

Exercises 4.1

Ex 4.1.1 Decide if the following assignments define functions from $A=\{1,2,3,4\}$ to $B=\{r,s,t,u,v\}$. $$ \matrix{f(1)=s &\quad & g(1)= t &\quad & h(1)=v \cr f(2)=t &\quad & g(2)= r &\quad & h(2)=u \cr f(4)=u &\quad & g(3)= s &\quad & h(3)=t \cr &\quad & g(4)= r &\quad & h(2)=s \cr &\quad & &\quad & h(4)=r \cr } $$

Ex 4.1.2 Let $f\colon \{s,t,u,v,w,x\}\to \{1,2,3,4,5\}$ and $g\colon \{1,2,3,4,5\}\to \{m,n,o,p\}$ be given by: $$ \matrix{f(s) = 2 &\quad& g(1) = m \cr f(t) = 1 &\quad& g(2) = n \cr f(u) = 4 &\quad& g(3) = p \cr f(v) = 2 &\quad& g(4) = o \cr f(w) = 1 &\quad& g(5) = m \cr f(x) = 2 &&&\cr} $$ Find the following:

Ex 4.1.3 Suppose that $f\colon \R\to \R$ is given by $f(x)= \cos x$ and $g\colon \R\to \R$ is given by $g(x)=x^2$. Find the following:

Ex 4.1.4 Suppose $f$ and $g$ are both functions from $A$ to $A$. If $f\circ f=g\circ g$, does it follow that $f=g$?

Ex 4.1.5 Suppose $A$ and $B$ are finite non-empty sets with $m$ and $n$ elements respectively. How many functions are there from $A$ to $B$?

Ex 4.1.6 Suppose $f$ and $g$ are two functions from $A$ to $B$. If $A=X\cup Y$, prove $f=g$ iff $f\vert_X=g\vert_X$ and $f\vert_Y=g\vert_Y$.

Ex 4.1.7 Suppose $f\colon C\to D$, $g\colon B\to C$ and $h\colon A\to B$ are functions. Prove $(f\circ g)\circ h=f\circ (g\circ h)$.