
0.5: Introduction and Preliminaries (Exercises)

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\def\d{\displaystyle}$$
$$\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 ParseError: EOF expected (click for details) Callstack: at (Template:MathJaxLevin), /content/body/div/p[1]/span, line 1, column 11 at template() at (Courses/Saint_Mary's_College,_Notre_Dame,_IN/SMC:_MATH_339_-_Discrete_Mathematics_(Rohatgi)/Text/0:_Introduction_and_Preliminaries/0.5:_Introduction_and_Preliminaries_(Exercises)), /content/body/p/span, line 1, column 22$$
$$\renewcommand{\bar}{\overline}$$
$$\newcommand{\card}[1]{\left| #1 \right|}$$
$$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$$
$$\newcommand{\lt}{&lt;}$$
$$\newcommand{\gt}{&gt;}$$
$$\newcommand{\amp}{&amp;}$$

$$\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}{&}$$

0.2: Mathematical Statements

1

Classify each of the sentences below as an atomic statement, and molecular statement, or not a statement at all. If the statement is molecular, say what kind it is (conjuction, disjunction, conditional, biconditional, negation).

1. The sum of the first 100 odd positive integers.
2. Everybody needs somebody sometime.
3. The Broncos will win the Super Bowl or I'll eat my hat.
4. We can have donuts for dinner, but only if it rains.
5. Every natural number greater than 1 is either prime or composite.
6. This sentence is false.
1. This is not a statement; it does not make sense to say it is true or false.
2. This is an atomic statement (there are some quantifiers, but no connectives).
3. This is a molecular statement, specifically a disjunction. Although if we read into it a bit more, what the speaker is really saying is that if the Broncos do not win the super bowl, then he will eat his hat, which would be a conditional.
4. This is a molecular statement, a conditional.
5. This is an atomic statement. Even though there is an “or” in the statement, it would not make sense to consider the two halves of the disjuction. This is because we quantified over the disjunction. In symbols, we have $$\forall x (x > 1 \imp (P(x) \vee C(x)))\text{.}$$ If we drop the quantifier, we are not left with a statement, since there is a free variable.
6. This is not a statement, although it certainly looks like one. Remember that statements must be true or false. If this sentence were true, that would make it false. If it were false, that would make it true. Examples like this are rare and usually arise from some sort of self-reference.

2

Suppose $$P$$ and $$Q$$ are the statements: $$P\text{:}$$ Jack passed math. $$Q\text{:}$$ Jill passed math.

1. Translate “Jack and Jill both passed math” into symbols.
2. Translate “If Jack passed math, then Jill did not” into symbols.
3. Translate “$$P \vee Q$$” into English.
4. Translate “$$\neg(P \wedge Q) \imp Q$$” into English.
5. Suppose you know that if Jack passed math, then so did Jill. What can you conclude if you know that:
1. Jill passed math?
2. Jill did not pass math?
1. $$P \wedge Q\text{.}$$
2. $$P \imp \neg Q\text{.}$$
3. Jack passed math or Jill passed math (or both).
4. If Jack and Jill did not both pass math, then Jill did.
1. Nothing else.
2. Jack did not pass math either.

3

Geoff Poshingten is out at a fancy pizza joint, and decides to order a calzone. When the waiter asks what he would like in it, he replies, “I want either pepperoni or sausage. Also, if I have sausage, then I must also include quail. Oh, and if I have pepperoni or quail then I must also have ricotta cheese.”

1. Translate Geoff's order into logical symbols.
2. The waiter knows that Geoff is either a liar or a truth-teller (so either everything he says is false, or everything is true). Which is it?
3. What, if anything, can the waiter conclude about the ingredients in Geoff's desired calzone?

4

Consider the statement “If Oscar eats Chinese food, then he drinks milk.”

1. Write the converse of the statement.
2. Write the contrapositive of the statement.
3. Is it possible for the contrapositive to be false? If it was, what would that tell you?
4. Suppose the original statement is true, and that Oscar drinks milk. Can you conclude anything (about his eating Chinese food)? Explain.
5. Suppose the original statement is true, and that Oscar does not drink milk. Can you conclude anything (about his eating Chinese food)? Explain.

5

Which of the following statements are equivalent to the implication, “if you win the lottery, then you will be rich,” and which are equivalent to the converse of the implication?

1. Either you win the lottery or else you are not rich.
2. Either you don't win the lottery or else you are rich.
3. You will win the lottery and be rich.
4. You will be rich if you win the lottery.
5. You will win the lottery if you are rich.
6. It is necessary for you to win the lottery to be rich.
7. It is sufficient to win the lottery to be rich.
8. You will be rich only if you win the lottery.
9. Unless you win the lottery, you won't be rich.
10. If you are rich, you must have won the lottery.
11. If you are not rich, then you did not win the lottery.
12. You will win the lottery if and only if you are rich.

The statements are equivalent to the…

1. converse.
2. implication.
3. neither.
4. implication.
5. converse.
6. converse.
7. implication.
8. converse.
9. converse.
10. converse (in fact, this is the converse).
11. implication (the statement is the contrapositive of the implication).
12. neither.

6

Consider the implication, “if you clean your room, then you can watch TV.” Rephrase the implication in as many ways as possible. Then do the same for the converse.

Hint

Of course there are many answers. It helps to assume that the statement is true and the converse is note true. Think about what that means in the real world and then start saying it in different ways. Some ideas: Use “necessary and sufficient” language, use “only if,” consider negations, use “or else” language.

7

Translate into symbols. Use $$E(x)$$ for “$$x$$ is even” and $$O(x)$$ for “$$x$$ is odd.”

1. No number is both even and odd.
2. One more than any even number is an odd number.
3. There is prime number that is even.
4. Between any two numbers there is a third number.
5. There is no number between a number and one more than that number.
1. $$\neg \exists x (E(x) \wedge O(x))\text{.}$$
2. $$\forall x (E(x) \imp O(x+1))\text{.}$$
3. $$\exists x(P(x) \wedge E(x))$$ (where $$P(x)$$ means “$$x$$ is prime”).
4. $$\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\text{.}$$
5. $$\forall x \neg \exists y (x \lt y \lt x+1)\text{.}$$

8

Translate into English:

1. $$\forall x (E(x) \imp E(x +2))\text{.}$$
2. $$\forall x \exists y (\sin(x) = y)\text{.}$$
3. $$\forall y \exists x (\sin(x) = y)\text{.}$$
4. $$\forall x \forall y (x^3 = y^3 \imp x = y)\text{.}$$
1. Any even number plus 2 is an even number.
2. For any $$x$$ there is a $$y$$ such that $$\sin(x) = y\text{.}$$ In other words, every number $$x$$ is in the domain of sine.
3. For every $$y$$ there is an $$x$$ such that $$\sin(x) = y\text{.}$$ In other words, every number $$y$$ is in the range of sine (which is false).
4. For any numbers, if the cubes of two numbers are equal, then the numbers are equal.

9

Suppose $$P(x)$$ is some predicate for which the statement $$\forall x P(x)$$ is true. Is it also the case that $$\exists x P(x)$$ is true? In other words, is the statement $$\forall x P(x) \imp \exists x P(x)$$ always true? Is the converse always true? Explain.

10

For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false.

1. $$\forall x \exists y (y^2 = x)$$.
2. $$\forall x \forall y \exists z (x < z < y)$$.
3. $$\exists x \forall y \forall z (y < z \imp y \le x \le z)$$ Hint: domains need not be infinite.

1. This says that everything has a square root (every element is the square of something). This is true of the positive real numbers, and also of the complex numbers. It is false of the natural numbers though, as for $$x = 2$$ there is no natural number $$y$$ such that $$y^2 = 2\text{.}$$
2. This asserts that between every pair of numbers there is some number strictly between them. This is true of the rationals (and reals) but false of the integers. If $$x = 1$$ and $$y = 2\text{,}$$ then there is nothing we can take for $$z\text{.}$$
3. Here we are saying that something is between every pair of numbers. For almost every domain, this is false. In fact, if the domain contains $$\{1,2,3, 4\}\text{,}$$ then no matter what we take $$x$$ to be, there will be a pair that $$x$$ is not between. However, the set $$\{1,2,3\}$$ as our domain makes the statement true. Let $$x = 2\text{.}$$ Then no matter what $$y$$ and $$z$$ we pick, if $$y < z\text{,}$$ then 2 is between them.

0.3: Sets

1

Let $$A = \{1,2,3,4,5\}\text{,}$$ $$B = \{3,4,5,6,7\}\text{,}$$ and $$C = \{2,3,5\}\text{.}$$

1. Find $$A \cap B\text{.}$$
2. Find $$A \cup B\text{.}$$
3. Find $$A \setminus B\text{.}$$
4. Find $$A \cap \overline{(B \cup C)}\text{.}$$
5. Find $$A \times C\text{.}$$
6. Is $$C \subseteq A\text{?}$$ Explain.
7. Is $$C \subseteq B\text{?}$$ Explain.
1. $$A \cap B = \{3,4,5\}\text{.}$$
2. $$A \cup B = \{1,2,3,4,5,6,7\}\text{.}$$
3. $$A \setminus B = \{1,2\}\text{.}$$
4. $$A \cap \bar{(B \cup C)} = \{1\}\text{.}$$
5. $$A \times C = \{ (1,2), (1,3), (1,5), (2,2), (2,3), (2,5), (3,2), (3,3), (3,5), (4,2)\text{,}$$ $$(4,3), (4,5), (5,2), (5,3), (5,5)\}$$
6. Yes. All three elements of $$C$$ are also elements of $$A\text{.}$$
7. No. There is an element of $$C\text{,}$$ namely the element 2, which is not an element of $$B\text{.}$$

2

Let $$A = \{x \in \N \st 3 \le x \le 13\}\text{,}$$ $$B = \{x \in \N \st x \mbox{ is even} \}\text{,}$$ and $$C = \{x \in \N \st x \mbox{ is odd} \}\text{.}$$

1. Find $$A \cap B\text{.}$$
2. Find $$A \cup B\text{.}$$
3. Find $$B \cap C\text{.}$$
4. Find $$B \cup C\text{.}$$

3

Find an example of sets $$A$$ and $$B$$ such that $$A\cap B = \{3, 5\}$$ and $$A \cup B = \{2, 3, 5, 7, 8\}\text{.}$$

4

Find an example of sets $$A$$ and $$B$$ such that $$A \subseteq B$$ and $$A \in B\text{.}$$

For example, $$A = \{1,2,3\}$$ and $$B = \{1,2,3,4,5,\{1,2,3\}\}$$

5

Recall $$\Z = \{\ldots,-2,-1,0, 1,2,\ldots\}$$ (the integers). Let $$\Z^+ = \{1, 2, 3, \ldots\}$$ be the positive integers. Let $$2\Z$$ be the even integers, $$3\Z$$ be the multiples of 3, and so on.

1. Is $$\Z^+ \subseteq 2\Z\text{?}$$ Explain.
2. Is $$2\Z \subseteq \Z^+\text{?}$$ Explain.
3. Find $$2\Z \cap 3\Z\text{.}$$ Describe the set in words, and using set notation.
4. Express $$\{x \in \Z \st \exists y\in \Z (x = 2y \vee x = 3y)\}$$ as a union or intersection of two sets already described in this problem.
1. No.
2. No.
3. $$2\Z \cap 3\Z$$ is the set of all integers which are multiples of both 2 and 3 (so multiples of 6). Therefore $$2\Z \cap 3\Z = \{x \in \Z \st \exists y\in \Z(x = 6y)\}\text{.}$$
4. $$2\Z \cup 3\Z\text{.}$$

6

Let $$A_2$$ be the set of all multiples of 2 except for $$2\text{.}$$ Let $$A_3$$ be the set of all multiples of 3 except for 3. And so on, so that $$A_n$$ is the set of all multiple of $$n$$ except for $$n\text{,}$$ for any $$n \ge 2\text{.}$$ Describe (in words) the set $$\bar{A_2 \cup A_3 \cup A_4 \cup \cdots}\text{.}$$

7

Draw a Venn diagram to represent each of the following:

1. $$A \cup \bar B$$
2. $$\bar{(A \cup B)}$$
3. $$A \cap (B \cup C)$$
4. $$(A \cap B) \cup C$$
5. $$\bar A \cap B \cap \bar C$$
6. $$(A \cup B) \setminus C$$
1. $$A \cup \bar B\text{:}$$
2. $$\bar{(A \cup B)}\text{:}$$
3. $$A \cap (B \cup C)\text{:}$$
4. $$(A \cap B) \cup C\text{:}$$
5. $$\bar A \cap B \cap \bar C\text{:}$$
6. $$(A \cup B) \setminus C\text{:}$$​​​​​

8

Describe a set in terms of $$A$$ and $$B$$ (using set notation) which has the following Venn diagram:

9

Find the following cardinalities:

1. $$|A|$$ when $$A = \{4,5,6,\ldots,37\}$$
2. $$|A|$$ when $$A = \{x \in \Z \st -2 \le x \le 100\}$$
3. $$|A \cap B|$$ when $$A = \{x \in \N \st x \le 20\}$$ and $$B = \{x \in \N \st x \mbox{ is prime} \}$$
1. 34.
2. 103.
3. 8.

10

Let $$A = \{a, b, c, d\}\text{.}$$ Find $$\pow(A)\text{.}$$

Hint

We are looking for a set containing 16 sets.

11

Let $$A = \{1,2,\ldots, 10\}\text{.}$$ How many subsets of $$A$$ contain exactly one element (i.e., how many singleton subsets are there)? How many doubleton subsets (containing exactly two elements) are there?

12

Let $$A = \{1,2,3,4,5,6\}\text{.}$$ Find all sets $$B \in \pow(A)$$ which have the property $$\{2,3,5\} \subseteq B\text{.}$$

13

Find an example of sets $$A$$ and $$B$$ such that $$|A| = 4\text{,}$$ $$|B| = 5\text{,}$$ and $$|A \cup B| = 9\text{.}$$

For example, $$A = \{1,2,3,4\}$$ and $$B = \{5,6,7,8,9\}$$ gives $$A \cup B = \{1,2,3,4,5,6,7,8,9\}\text{.}$$

14

Find an example of sets $$A$$ and $$B$$ such that $$|A| = 3\text{,}$$ $$|B| = 4\text{,}$$ and $$|A \cup B| = 5\text{.}$$

15

Are there sets $$A$$ and $$B$$ such that $$|A| = |B|\text{,}$$ $$|A\cup B| = 10\text{,}$$ and $$|A\cap B| = 5\text{?}$$ Explain.

16

In a regular deck of playing cards there are 26 red cards and 12 face cards. Explain, using sets and what you have learned about cardinalities, why there are only 32 cards which are either red or a face card.

0.4: Functions

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?

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

\begin{equation*} f = \begin{pmatrix} 1 & 2 & 3 \\ a & a& a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & b & b \end{pmatrix} \end{equation*} \begin{equation*} f = \begin{pmatrix} 1 & 2 & 3 \\ a & a& b \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ a & b & a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & a& a \end{pmatrix} \end{equation*} \begin{equation*} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & b & a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & a& b \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ a & b & 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?

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 & 2}{a& a} \quad f = \twoline{1 & 2}{b & b} \quad f = \twoline{1 & 2}{c & c} \end{equation*} \begin{equation*} f = \twoline{1 & 2}{a& b} \quad f = \twoline{1 & 2}{a & c} \quad f = \twoline{1 & 2}{b & c} \end{equation*} \begin{equation*} f = \twoline{1 & 2}{b & a} \quad f = \twoline{1 & 2}{c & a} \quad f = \twoline{1 & 2}{c & 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 & \text{ if } n \text{ is even} \\ (n+1)/2 & \text{ if } n \text{ is odd} . \end{cases}$$
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{.}$$
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.
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.
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{.}$$

$$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& 2 & 3}{a & a & b}$$ and $$g = \twoline{a& b & c}{5 & 6 & 7}\text{?}$$

13

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

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

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

b: $$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?

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?