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$.

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.

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.)

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$.

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.

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.

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.

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.

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} $$

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.

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).
$$

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:

a) $h=g\circ f$ | e) The preimage(s) of $p$ under $g$ |

b) The image of $u$ under $f$ | f) The preimage(s) of $1$ under $f$ |

c) The image of $2$ under $g$ | g) The preimage(s) of $n$ under $h$ |

d) The image of $v$ under $h$ | h) The preimage(s) of $5$ under $f$ |

**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:

a) $h=g\circ f$ | e) The preimage(s) of $\sqrt 3/2$ under $f$ |

b) The image of $4\pi$ under $f$ | f) The preimage(s) of $9/25$ under $g$ |

c) The image of $-\sqrt 2$ under $g$ | g) The preimage(s) of $1$ under $h$ |

d) The image of $\pi/4$ under $h$ | h) The preimage(s) of $2$ under $f$ |

**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)$.