$\def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #1} \newcommand{\s}[1]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.6) node[above]{A}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{B}} \def\C{\mathbb C} \def\circleC{(0,-1) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{C}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,1.5)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,1.5)} \def\E{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{\sigma-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-1.5,.6) node[above]{A}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{B}} \def\circleC{(0,-1) circle (1)} \def\circleClabel{(.5,-2) node[right]{C}} \def\twosetbox{(-2,-1.4) rectangle (2,1.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section0.4Functions

A function is a rule that assigns each input exactly one output. We call the output the image of the input. The set of all inputs for a function is called the domain. The set of all allowable outputs is called the codomain. We would write $f:X \to Y$ to describe a function with name $f\text{,}$ domain $X$ and codomain $Y\text{.}$ This does not tell us which function $f$ is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule).

For example, consider the function $f:\N \to \N$ defined by $f(x) = x^2 + 3\text{.}$ Here the domain and codomain are the same set (the natural numbers). The rule is: take your input, multiply it by itself and add 3. This works because we can apply this rule to every natural number (every element of the domain) and the result is always a natural number (an element of the codomain). Notice though that not every natural number actually is an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural numbers that are actually outputs is called the range of the function (in this case, the range is $\{3, 4, 7, 12, 19, 28, \ldots\}\text{,}$ all the natural numbers that are 3 more than a perfect square).

The key thing that makes a rule actually a function is that there is exactly one output for each input. That is, it is important that the rule be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function.

The description of the rule can vary greatly. We might just give a list of the images of each input. You could also describe the function with a table or a graph or in words.

###### Example0.4.1

The following are all examples of functions:

1. $f:\Z \to \Z$ defined by $f(n) = 3n\text{.}$ The domain and codomain are both the set of integers. However, the range is only the set of integer multiples of 3.
2. $g: \{1,2,3\} \to \{a,b,c\}$ defined by $g(1) = c\text{,}$ $g(2) = a$ and $g(3) = a\text{.}$ The domain is the set $\{1,2,3\}\text{,}$ the codomain is the set $\{a,b,c\}$ and the range is the set $\{a,c\}\text{.}$ Note that $g(2)$ and $g(3)$ are the same element of the codomain. This is okay since each element in the domain still has only one output.
3. $h:\{1,2,3\} \to \{1,2,3\}$ defined as follows:

This means that the function $f$ sends 1 to 2, 2 to 1 and 3 to 3: just follow the arrows.

The arrow diagram used to define the function above can be very helpful in visualizing functions. We will often be working with functions with finite domains, so this kind of picture is often more useful than a traditional graph of a function. A graph of the function in example 3 above would look like this:

It would be absolutely WRONG to connect the dots or try to fit them to some curve. There are only three elements in the domain. A curve suggests that the domain contains an entire interval of real numbers. Remember, we are not in calculus any more!

Since we will so often use functions with small domains and codomains, let's adopt some notation that is a little easier to work with than that of examples 2 and 3 above. All we need is some clear way of denoting the image of each element in the domain. In fact, writing a table of values would work perfectly:

 $x$ 0 1 2 3 4 $f(x)$ 3 3 2 4 1

We simplify this further by writing this as a matrix with each input directly over its output:

\begin{equation*} f = \begin{pmatrix}0 \amp 1 \amp 2\amp 3 \amp 4 \\ 3 \amp 3 \amp 2 \amp 4 \amp 1\end{pmatrix} \end{equation*}

Note this is just notation and not the same sort of matrix you would find in a linear algebra class (it does not make sense to do operations with these matrices, or row reduce them, for example).

It is important to know how to determine if a rule is or is not a function. Drawing the arrow diagrams can help.

###### Example0.4.2

Which of the following diagrams represent a function? Let $X = \{1,2,3,4\}$ and $Y = \{a,b,c,d\}\text{.}$

Solution

$f$ is a function. So is $g\text{.}$ There is no problem with an element of the codomain not being the image of any input, and there is no problem with $a$ from the codomain being the image of both 2 and 3 from the domain. We could use our two-line notation to write these as

\begin{equation*} f= \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \\ d \amp a \amp c \amp b \end{pmatrix} \qquad g = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \\ d \amp a \amp a \amp b \end{pmatrix}. \end{equation*}

However, $h$ is NOT a function. In fact, it fails for two reasons. First, the element 1 from the domain has not been mapped to any element from the codomain. Second, the element 2 from the domain has been mapped to more than one element from the codomain ($a$ and $c$). Note that either one of these problems is enough to make a rule not a function. In general, neither of the following mappings are functions:

It might also be helpful to think about how you would write the two-line notation for $h\text{.}$ We would have something like:

\begin{equation*} h=\begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \\ \amp a,c? \amp d \amp b\end{pmatrix}. \end{equation*}

There is nothing under 1 (bad) and we needed to put more than one thing under 2 (very bad). With a rule that is actually a function, the two-line notation will always “work”.

### SubsectionSurjections, Injections, and Bijections

We now turn to investigating special properties functions might or might not possess.

In the examples above, you may have noticed that sometimes there are elements of the codomain which are not in the range. When this sort of the thing does not happen, (that is, when everything in the codomain is in the range) we say the function is onto or that the function maps the domain onto the codomain. This terminology should make sense: the function puts the domain (entirely) on top of the codomain. The fancy math term for an onto function is a surjection, and we say that an onto function is a surjective function.

In pictures:

###### Example0.4.3

Which functions are surjective (i.e., onto)?

1. $f:\Z \to \Z$ defined by $f(n) = 3n\text{.}$
2. $g: \{1,2,3\} \to \{a,b,c\}$ defined by $g = \begin{pmatrix}1 \amp 2 \amp 3 \\ c \amp a \amp a \end{pmatrix}\text{.}$
3. $h:\{1,2,3\} \to \{1,2,3\}$ defined as follows:

Solution

1. $f$ is not surjective. There are elements in the codomain which are not in the range. For example, no $n \in \Z$ gets mapped to the number 1 (the rule would say that $\frac{1}{3}$ would be sent to 1, but $\frac{1}{3}$ is not in the domain). In fact, the range of the function is $3\Z$ (the integer multiples of 3), which is not equal to $\Z\text{.}$
2. $g$ is not surjective. There is no $x \in \{1,2,3\}$ (the domain) for which $g(x) = b\text{,}$ so $b\text{,}$ which is in the codomain, is not in the range. Notice that there is an element from the codomain “missing” from the bottom row of the matrix.
3. $h$ is surjective. Every element of the codomain is also in the range. Nothing in the codomain is missed.

To be a function, a rule cannot assign a single element of the domain to two or more different elements of the codomain. However, we have seen that the reverse is permissible: a function might assign the same element of the codomain to two or more different elements of the domain. When this does not occur (that is, when each element of the codomain is the image of at most one element of the domain) then we say the function is one-to-one. Again, this terminology makes sense: we are sending at most one element from the domain to one element from the codomain. One input to one output. The fancy math term for a one-to-one function is an injection. We call one-to-one functions injective functions.

In pictures:

###### Example0.4.4

Which functions are injective (i.e., one-to-one)?

1. $f:\Z \to \Z$ defined by $f(n) = 3n\text{.}$
2. $g: \{1,2,3\} \to \{a,b,c\}$ defined by $g = \begin{pmatrix}1 \amp 2 \amp 3 \\ c \amp a \amp a \end{pmatrix}\text{.}$
3. $h:\{1,2,3\} \to \{1,2,3\}$ defined as follows:

Solution

1. $f$ is injective. Each element in the codomain is assigned to at most one element from the domain. If $x$ is a multiple of three, then only $x/3$ is mapped to $x\text{.}$ If $x$ is not a multiple of 3, then there is no input corresponding to the output $x\text{.}$
2. $g$ is not injective. Both inputs $2$ and $3$ are assigned the output $a\text{.}$ Notice that there is an element from the codomain that appears more than once on the bottom row of the matrix.
3. $h$ is injective. Each output is only an output once.

From the examples above, it should be clear that there are functions which are surjective, injective, both, or neither. In the case when a function is both one-to-one and onto (an injection and surjection), we say the function is a bijection, or that the function is a bijective function.

### SubsectionInverse Image

When discussing functions, we have notation for talking about an element of the domain (say $x$) and its corresponding element in the codomain (we write $f(x)\text{,}$ which is the image of $x$). It would also be nice to start with some element of the codomain (say $y$) and talk about which element or elements (if any) from the domain it is the image of. We could write “those $x$ in the domain such that $f(x) = y\text{,}$” but this is a lot of writing. Here is some notation to make our lives easier.

Suppose $f:X \to Y$ is a function. For $y \in Y$ (an element of the codomain), we write $f\inv(y)$ to represent the set of all elements in the domain $X$ which get sent to $y\text{.}$ That is, $f\inv(y) = \{x \in X \st f(x) = y\}\text{.}$ We say that $f\inv(y)$ is the complete inverse image of $y$ under $f\text{.}$

WARNING: $f\inv(y)$ is not an inverse function! Inverse functions only exist for bijections, but $f\inv(y)$ is defined for any function $f\text{.}$ The point: $f\inv(y)$ is a set, not an element of the domain.

###### Example0.4.5

Consider the function $f:\{1,2,3,4,5,6\} \to \{a,b,c,d\}$ given by

\begin{equation*} f = \begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \\ a \amp a \amp b \amp c \amp c \amp c\end{pmatrix}. \end{equation*}

Find the complete inverse image of each element in the codomain.

Solution

Remember, we are looking for sets.

\begin{equation*} f\inv(a) = \{1,2\} \end{equation*} \begin{equation*} f\inv(b) = \{3\} \end{equation*} \begin{equation*} f\inv(c) = \{4,5,6\} \end{equation*} \begin{equation*} f\inv(d) = \emptyset. \end{equation*}
###### Example0.4.6

Consider the function $g:\Z \to \Z$ defined by $g(n) = n^2 + 1\text{.}$ Find $g\inv(1)\text{,}$ $g\inv(2)\text{,}$ $g\inv(3)$ and $g\inv(10)\text{.}$

Solution

To find $g\inv(1)\text{,}$ we need to find all integers $n$ such that $n^2 + 1 = 1\text{.}$ Clearly only 0 works, so $g\inv(1) = \{0\}$ (note that even though there is only one element, we still write it as a set with one element in it).

To find $g\inv(2)\text{,}$ we need to find all $n$ such that $n^2 + 1 = 2\text{.}$ We see $g\inv(2) = \{-1,1\}\text{.}$

If $n^2 + 1 = 3\text{,}$ then we are looking for an $n$ such that $n^2 = 2\text{.}$ There are no such integers so $g\inv(3) = \emptyset\text{.}$

Finally, $g\inv(10) = \{-3, 3\}$ because $g(-3) = 10$ and $g(3) = 10\text{.}$

Since $f\inv(y)$ is a set, it makes sense to ask for $\card{f\inv(y)}\text{,}$ the number of elements in the domain which map to $y\text{.}$

###### Example0.4.7

Find a function $f:\{1,2,3,4,5\} \to \N$ such that $\card{f\inv(7)} = 5\text{.}$

Solution

There is only one such function. We need five elements of the domain to map to the number $7 \in \N\text{.}$ Since there are only five elements in the domain, all of them must map to 7. So

\begin{equation*} f = \begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \\ 7 \amp 7 \amp 7 \amp 7 \amp 7\end{pmatrix}. \end{equation*}
###### Function Definitions

• A function is a rule that assigns each element of a set, called the domain, to exactly one element of a second set, called the codomain.

• Notation: $f:X \to Y$ is our way of saying that the function is called $f\text{,}$ the domain is the set $X\text{,}$ and the codomain is the set $Y\text{.}$

• To specify the rule for a function with small domain, use two-line notation by writing a matrix with each output directly below its corresponding input, as in:

\begin{equation*} f = \begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \\ 2 \amp 1 \amp 3 \amp 1 \end{pmatrix}. \end{equation*}
• $f(x) = y$ means the element $x$ of the domain (input) is assigned to the element $y$ of the codomain. We say $y$ is an output. Alternatively, we call $y$ the image of $x$ under $f$.

• The range is a subset of the codomain. It is the set of all elements which are assigned to at least one element of the domain by the function. That is, the range is the set of all outputs.

• A function is injective (an injection or one-to-one) if every element of the codomain is the output for at most one element from the domain.

• A function is surjective (a surjection or onto) if every element of the codomain is the output of at least one element of the domain.

• A bijection is a function which is both an injection and surjection. In other words, if every element of the codomain is the output of exactly one element of the domain.

• The image of an element $x$ in the domain is the element $y$ in the codomain that $x$ is mapped to. That is, the image of $x$ under $f$ is $f(x)\text{.}$

• The complete inverse image of an element $y$ in the codomain, written $f\inv(y)\text{,}$ is the set of all elements in the domain which are assigned to $y$ by the function.

### SubsectionExercises

###### 1

Write out all functions $f: \{1,2,3\} \to \{a,b\}$ (using two-line notation). How many are there? How many are injective? How many are surjective? How many are both?

Solution

There are 8 different functions. In two-line notation these are:

\begin{equation*} f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ a \amp a\amp a \end{pmatrix} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ b \amp b \amp b \end{pmatrix} \end{equation*} \begin{equation*} f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ a \amp a\amp b \end{pmatrix} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ a \amp b \amp a \end{pmatrix} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ b \amp a\amp a \end{pmatrix} \end{equation*} \begin{equation*} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ b \amp b \amp a \end{pmatrix} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ b \amp a\amp b \end{pmatrix} \quad f = \begin{pmatrix} 1 \amp 2 \amp 3 \\ a \amp b \amp b \end{pmatrix} \end{equation*}

None of the functions are injective. Exactly 6 of the functions are surjective. No functions are both (since no functions here are injective).

###### 2

Write out all functions $f: \{1,2\} \to \{a,b,c\}$ (in two-line notation). How many are there? How many are injective? How many are surjective? How many are both?

Solution

There are 9 functions: you have a choice of three outputs for $f(1)\text{,}$ and for each, you have three choices for the output $f(2)\text{.}$ Of these functions, 6 are injective, 0 are surjective, and 0 are both:

\begin{equation*} f = \twoline{1 \amp 2}{a\amp a} \quad f = \twoline{1 \amp 2}{b \amp b} \quad f = \twoline{1 \amp 2}{c \amp c} \end{equation*} \begin{equation*} f = \twoline{1 \amp 2}{a\amp b} \quad f = \twoline{1 \amp 2}{a \amp c} \quad f = \twoline{1 \amp 2}{b \amp c} \end{equation*} \begin{equation*} f = \twoline{1 \amp 2}{b \amp a} \quad f = \twoline{1 \amp 2}{c \amp a} \quad f = \twoline{1 \amp 2}{c \amp b} \end{equation*}
###### 3

Consider the function $f:\{1,2,3,4,5\} \to \{1,2,3,4\}$ given by the table below:

 $x$ 1 2 3 4 5 $f(x)$ 3 2 4 1 2

1. Is $f$ injective? Explain.

2. Is $f$ surjective? Explain.

3. Write the function using two-line notation.

###### 4

Consider the function $f:\{1,2,3,4\} \to \{1,2,3,4\}$ given by the graph below.

1. Is $f$ injective? Explain.

2. Is $f$ surjective? Explain.

3. Write the function using two-line notation.

###### 5

For each function given below, determine whether or not the function is injective and whether or not the function is surjective.

1. $f:\N \to \N$ given by $f(n) = n+4\text{.}$
2. $f:\Z \to \Z$ given by $f(n) = n+4\text{.}$
3. $f:\Z \to \Z$ given by $f(n) = 5n - 8\text{.}$
4. $f:\Z \to \Z$ given by $f(n) = \begin{cases}n/2 \amp \text{ if } n \text{ is even} \\ (n+1)/2 \amp \text{ if } n \text{ is odd} . \end{cases}$
Solution

1. $f$ is injective, but not surjective (since 0, for example, is never an output).
2. $f$ is injective and surjective. Unlike in the previous question, every integers is an output (of the integer 4 less than it).
3. $f$ is injective, but not surjective (10 is not 8 less than a multiple of 5, for example).
4. $f$ is not injective, but is surjective. Every integer is an output (of twice itself, for example) but some integers are outputs of more than one input: $f(5) = 3 = f(6)\text{.}$
###### 6

Let $A = \{1,2,3,\ldots,10\}\text{.}$ Consider the function $f:\pow(A) \to \N$ given by $f(B) = |B|\text{.}$ That is, $f$ takes a subset of $A$ as an input and outputs the cardinality of that set.

1. Is $f$ injective? Prove your answer.

2. Is $f$ surjective? Prove your answer.

3. Find $f\inv(1)\text{.}$

4. Find $f\inv(0)\text{.}$

5. Find $f\inv(12)\text{.}$

Solution

1. $f$ is not injective. To prove this, we must simply find two different elements of the domain which map to the same element of the codomain. Since $f(\{1\}) = 1$ and $f(\{2\}) = 1\text{,}$ we see that $f$ is not injective.
2. $f$ is not surjective. The largest subset of $A$ is $A$ itself, and $|A| = 10\text{.}$ So no natural number greater than 10 will ever be an output.
3. $f\inv(1) = \{\{1\}, \{2\}, \{3\}, \ldots \{10\}\}$ (the set of all the singleton subsets of $A$).
4. $f\inv(0) = \{\emptyset\}\text{.}$ Note, it would be wrong to write $f\inv(0) = \emptyset$ - that would claim that there is no input which has 0 as an output.
5. $f\inv(12) = \emptyset\text{,}$ since there are no subsets of $A$ with cardinality 12.
###### 7

Let $A = \{n \in \N \st 0 \le n \le 999\}$ be the set of all numbers with three or fewer digits. Define the function $f:A \to \N$ by $f(abc) = a+b+c\text{,}$ where $a\text{,}$ $b\text{,}$ and $c$ are the digits of the number in $A\text{.}$ For example, $f(253) = 2 + 5 + 3 = 10\text{.}$

1. Find $f\inv(3)\text{.}$

2. Find $f\inv(28)\text{.}$

3. Is $f$ injective. Explain.

4. Is $f$ surjective. Explain.

Solution

1. $f\inv(3) = \{003, 030, 300, 012, 021, 102, 201, 120, 210, 111\}$
2. $f\inv(28) = \emptyset$ (since the largest sum of three digits is $9+9+9 = 27$)
3. Part (a) proves that $f$ is not injective. The output 3 is assigned to 10 different inputs.

4. Part (b) proves that $f$ is not surjective. There is an element of the codomain (28) which is not assigned to any inputs.

###### 8

Let $f:X \to Y$ be some function. Suppose $3 \in Y\text{.}$ What can you say about $f\inv(3)$ if you know,

1. $f$ is injective? Explain.
2. $f$ is surjective? Explain.
3. $f$ is bijective? Explain.
Solution

1. $|f\inv(3)| \le 1\text{.}$ In other words, either $f\inv(3)$ is the emptyset or is a set containing exactly one element. Injective functions cannot have two elements from the domain both map to 3.
2. $|f\inv(3)| \ge 1\text{.}$ In other words, $f\inv(3)$ is a set containing at least one elements, possibly more. Surjective functions must have something map to 3.
3. $|f\inv(3)| = 1\text{.}$ There is exactly one element from $X$ which gets mapped to 3, so $f\inv(3)$ is the set containing that one element.
###### 9

Find a set $X$ and a function $f:X \to \N$ so that $f\inv(0) \cup f\inv(1) = X\text{.}$

Solution

$X$ can really be any set, as long as $f(x) = 0$ or $f(x) = 1$ for every $x \in X\text{.}$ For example, $X = \N$ and $f(n) = 0$ works.

###### 10

What can you deduce about the sets $X$ and $Y$ if you know …

1. there is an injective function $f:X \to Y\text{?}$ Explain.

2. there is a surjective function $f:X \to Y\text{?}$ Explain.

3. there is a bijectitve function $f:X \to Y\text{?}$ Explain.

###### 11

Suppose $f:X \to Y$ is a function. Which of the following are possible? Explain.

1. $f$ is injective but not surjective.
2. $f$ is surjective but not injective.
3. $|X| = |Y|$ and $f$ is injective but not surjective.
4. $|X| = |Y|$ and $f$ is surjective but not injective.
5. $|X| = |Y|\text{,}$ $X$ and $Y$ are finite, and $f$ is injective but not surjective.
6. $|X| = |Y|\text{,}$ $X$ and $Y$ are finite, and $f$ is surjective but not injective.
###### 12

Let $f:X \to Y$ and $g:Y \to Z$ be functions. We can define the composition of $f$ and $g$ to be the function $g\circ f:X \to Z$ which the image of each $x \in X$ is $g(f(x))\text{.}$ That is, plug $x$ into $f\text{,}$ then plug the result into $g$ (just like composition in algebra and calculus).

1. If $f$ and $g$ are both injective, must $g\circ f$ be injective? Explain.
2. If $f$ and $g$ are both surjective, must $g\circ f$ be surjective? Explain.
3. Suppose $g\circ f$ is injective. What, if anything, can you say about $f$ and $g\text{?}$ Explain.
4. Suppose $g\circ f$ is surjective. What, if anything, can you say about $f$ and $g\text{?}$ Explain.
Hint

Work with some examples. What if $f = \twoline{1\amp 2 \amp 3}{a \amp a \amp b}$ and $g = \twoline{a\amp b \amp c}{5 \amp 6 \amp 7}\text{?}$

###### 13

Consider the function $f:\Z \to \Z$ given by $f(n) = \begin{cases}n+1 \amp \text{ if }n\text{ is even} \\ n-3 \amp \text{ if }n\text{ is odd} . \end{cases}$

1. Is $f$ injective? Prove your answer.

2. Is $f$ surjective? Prove your answer.

Solution

1. $f$ is injective.

###### Proof

Let $x$ and $y$ be elements of the domain $\Z\text{.}$ Assume $f(x) = f(y)\text{.}$ If $x$ and $y$ are both even, then $f(x) = x+1$ and $f(y) = y+1\text{.}$ Since $f(x) = f(y)\text{,}$ we have $x + 1 = y + 1$ which implies that $x = y\text{.}$ Similarly, if $x$ and $y$ are both odd, then $x - 3 = y-3$ so again $x = y\text{.}$ The only other possibility is that $x$ is even an $y$ is odd (or visa-versa). But then $x + 1$ would be odd and $y - 3$ would be even, so it cannot be that $f(x) = f(y)\text{.}$ Therefore if $f(x) = f(y)$ we then have $x = y\text{,}$ which proves that $f$ is injective.

2. $f$ is surjective.

###### Proof

Let $y$ be an element of the codomain $\Z\text{.}$ We will show there is an element $n$ of the domain ($\Z$) such that $f(n) = y\text{.}$ There are two cases: First, if $y$ is even, then let $n = y+3\text{.}$ Since $y$ is even, $n$ is odd, so $f(n) = n-3 = y+3-3 = y$ as desired. Second, if $y$ is odd, then let $n = y-1\text{.}$ Since $y$ is odd, $n$ is even, so $f(n) = n+1 = y-1+1 = y$ as needed. Therefore $f$ is surjective.

###### 14

At the end of the semester a teacher assigns letter grades to each of her students. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

Solution

Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective – it will be if there is at least one student who gets each grade.

###### 15

In the game of Hearts, four players are each dealt 13 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

###### 16

Suppose 7 players are playing 5-card stud. Each player initially receives 5 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

Solution

This cannot be a function. If the domain were the set of cards, then it is not a function because not every card gets dealt to a player. If the domain were the set of players, it would not be a function because a single player would get mapped to multiple cards. Since this is not a function, it doesn't make sense to say whether it is injective/surjective/bijective.