27 - Additional facts about functions

ˆ!Screenshot 2023-11-13 at 12.26.30 AM.png
!Screenshot 2023-11-13 at 12.26.54 AM.png!Screenshot 2023-11-13 at 12.27.05 AM.png
!Screenshot 2023-11-13 at 12.27.53 AM.png!Screenshot 2023-11-13 at 12.28.20 AM.png!Screenshot 2023-11-13 at 12.30.46 AM.png!Screenshot 2023-11-13 at 12.31.02 AM.png

In Class Practice

HW 27

Ben Finch

E 27.1
$f$ is surjective iff $| i m (f) | = | B |$ .
Proof.
Let $f, A, B$ be as stated above.
(=>)
Assume that $f$ is surjective. Then $B = i m (f)$ . Thus $| B | = | i m (f) |$ .

(<=)
Assume that $| i m (f) | = | B |$ . We work contrapositively.. Assume that $f$ is not surjective. Then there exists $b \in B$ such that $b \notin i m (f)$ . Thus if $| B | = n$ , $| i m (f) | \leq n - 1$ . Hence $| B | \neq | i m (f) |$ . $◻$

E 27.2

$f_{1} (n) = n / 2$
Injective.
Let $a_{1}, a_{2} \in N$ such that $a_{1}, a_{2}$ are even. Assume that $f_{1} (a_{1}) = f_{1} (a_{2})$ . We find that

\begin{aligned} \frac{a_{1}}{2} & = \frac{a_{2}}{2} \\ a_{1} & = a_{2} \end{aligned}

So $f_{1}$ is injective.

Surjective.
Let $b \in N$ . Define $a = 2 b$ . We find that

\begin{aligned} f_{1} (a) & = \frac{a}{2} \\ = \frac{2 b}{2} \\ = b \end{aligned}

So $f_{1}$ is surjective. Since $f_{1}$ is both injective and surjective, it is bijective.

$f_{2} = - \frac{n - 1}{2}$

Injective
Let $a_{1}, a_{2} \in N$ such that $a_{1}, a_{2}$ are odd. Assume that $f_{2} (a_{1}) = f_{2} (a_{2})$ . We see that

\begin{aligned} - \frac{a_{1} - 1}{2} & = - \frac{a_{2} - 1}{2} \\ \frac{a_{1} - 1}{2} & = \frac{a_{2} - 1}{2} \\ a_{1} - 1 & = a_{2} - 1 \\ a_{1} & = a_{2} \end{aligned}

So $f_{2}$ is injective.

Surjective
Let $b \in N$ . Define $a = - 2 b + 1$ . We find that

\begin{aligned} f (a) & = - \frac{a - 1}{2} \\ = - \frac{(- 2 b + 1) - 1}{2} \\ = - \frac{- 2 b}{2} \\ = \frac{2 b}{2} \\ = b \end{aligned}

So $f_{2}$ is surjective .Since $f_{2}$ is both injective and surjective, it is bijective.

Hence, both $f_{1}$ and $f_{2}$ are bijective. $◻$

E 27.3

f (x) = {\begin{cases} (0, 1 + x) if x \geq 0 \\ (1, - x) if x < 0 \end{cases}

Injective:

Let $a_{1}, a_{2} \in Z$ . Assume $f (a_{1}) = f (a_{2})$ . There are two cases:

If $a_{1}, a_{2} \geq 0$ , then $(0, 1 + a_{1}) = (0, 1 + a_{2})$ so $1 + a_{1} = 1 + a_{2}$ , which means $a_{1} = a_{2}$ .
If $a_{1}, a_{2} < 0$ , then $(1, - a_{1}) = (1, - a_{2})$ , so $- a_{1} = - a_{2}$ , which means $a_{1} = a_{2}$ .

So, using the pasting together theorem $f$ is injective.

Surjective:

Given any element $(i, n)$ in ${0, 1} \times N$ , we want to find an integer $a$ such that $f (a) = (i, n)$ .

If $i = 0$ , define $a = n - 1$ . Then $f (a) = f (n - 1) = (0, 1 + (n - 1)) = (0, n)$ .
If $i = 1$ , define $a = - n$ . Then $f (a) = f (- n) = (1, - (- n)) = (1, n)$ .

So, using the pasting together theorem, $f$ is surjective.

Hence, $f$ is bijective.

E 27.4
$f (x) = x^{2} + 2 x + 2$

a) $f =$ ${(- 3, 5), (- 2, 2), (- 1, 1), (0, 2), (1, 5), (2, 10), (3, 17)}$
b) $i m (f) = {5, 2, 1, 10, 17}$
c) $C = {(- 1, 1), (0, 2), (1, 5), (2, 10), (3, 17)}$ . We see that $C$ is a subset of $A$ . $C$ is injective since every second component appears exactly once. Also, im( $f |_{c}$ ) = im( $f$ ),

E 27.5

a)
Proof.
Let $f : A \to B$ be an injective function and let $S \subseteq A$ . Let $a_{1}, a_{2} \in S$ . Assume that $f |_{s} (a_{1}) = f |_{s} (a_{2})$ . Note that $f |_{s} (a_{1}) = f (a_{1})$ and $f |_{s} (a_{2}) = f (a_{2})$ . Therefore, $f (a_{1}) = f (a_{2})$ . Since $f$ is injective, $a_{1} = a_{2}$ . So $f |_{s}$ is injective. $◻$
b)
Proof.

(Surjective)
Let $b \in i m (f)$ . Then $\exists a \in A$ such that $f (a) = b$ . Hence $\hat{f} (a) = b$ . Thus $\hat{f}$ is surjective.

(Injective)
Let $a_{1}, a_{2} \in A$ . Assume that $\hat{f} (a_{1}) = \hat{f} (a_{2})$ . Then $f (a_{1}) = f (a_{2})$ . Hence $a_{1} = a_{2}$ . Thus $\hat{f}$ is injective.

So $\hat{f}$ is bijective.

E 27.6

a) Prove that $f$ is surjective iff $f^{- 1} ({b}) \neq \emptyset$ for each $b \in B$ .

( $\Rightarrow$ ) Assume $f$ is surjective. By definition, for every element $b \in B$ , there exists at least one element $a \in A$ such that $f (a) = b$ . This implies $f^{- 1} ({b})$ is not empty for each $b \in B$ , because there is at least one element in $A$ that maps to each $b$ in $B$ .

( $\Leftarrow$ ) Conversely, assume $f^{- 1} ({b}) \neq \emptyset$ for each $b$ in $B$ . This means for each $b$ in $B$ , there is at least one element in $A$ that maps to $b$ . This is the definition of a surjective function. Therefore, $f$ is surjective.

b) Prove that $f$ is injective iff $| f^{- 1} ({b}) | \leq 1$ for each $b \in B$ .

( $\Rightarrow$ ) Assume $f$ is injective. By definition, for every element $b$ in $B$ that is the image of an element $a$ in $A$ , there is no other element in $A$ that maps to $b$ . This implies that the preimage $f^{- 1} ({b})$ contains at most one element for each $b$ in $B$ , so $| f^{- 1} ({b}) | \leq 1$ .

( $\Leftarrow$ ) Conversely, assume $| f^{- 1} ({b}) | \leq 1$ for each $b$ in $B$ . This means for each $b$ in $B$ , there is at most one element in $A$ that maps to $b$ . This is the definition of an injective function. Therefore, $f$ is injective.

E 27.7

a) $f (X \cup Y) = f (X) \cup f (Y)$

$f (X \cup Y) \subseteq f (X) \cup f (Y)$ :

Take any element $y \in f (X \cup Y)$ . Then there exists an $x \in X \cup Y$ such that $f (x) = y$ . Now, $x$ is either in $X$ or $Y$ , so $y$ will be in $f (X)$ or $f (Y)$ , and hence in $f (X) \cup f (Y)$ .
$f (X) \cup f (Y) \subseteq f (X \cup Y)$ :

Take any element $y \in f (X) \cup f (Y)$ . This means $y$ is either in $f (X)$ or $f (Y)$ . If $y \in f (X)$ , then there is an $x \in X$ such that $f (x) = y$ . Also, if $y \in f (Y)$ , then there is an $x \in Y$ such that $f (x) = y$ . In either case, $x$ is in $X \cup Y$ , so $y$ is in $f (X \cup Y)$ .

Therefore, $f (X \cup Y) = f (X) \cup f (Y)$ . $◻$

b) $f (X \cap Y) = f (X) \cap f (Y)$

This statement is not always true. We will disprove it.

Consider $f$ such that $f (a) = f (b)$ for some $a \in X$ , $b \in Y$ , and $a \neq b$ . Then $f (a) = f (b)$ is in both $f (X)$ and $f (Y)$ , but there is no element in $X \cap Y$ that maps to it because $a \neq b$ . Hence, $f (X \cap Y) \neq f (X) \cap f (Y)$ . $◻$

c) $f^{- 1} (C \cup D) = f^{- 1} (C) \cup f^{- 1} (D)$

Proof.

$f^{- 1} (C \cup D) \subseteq f^{- 1} (C) \cup f^{- 1} (D)$ :

If $x \in f^{- 1} (C \cup D)$ , then $f (x) \in C \cup D$ , which means $f (x) \in C$ or $f (x) \in D$ . Hence, $x$ is in either $f^{- 1} (C)$ or $f^{- 1} (D)$ , and thus in their union.
$f^{- 1} (C) \cup f^{- 1} (D) \subseteq f^{- 1} (C \cup D)$ :

If $x$ is in $f^{- 1} (C)$ or $f^{- 1} (D)$ , then $f (x)$ is in $C$ or $D$ , and thus in $C \cup D$ . Hence, $x \in f^{- 1} (C \cup D)$ .

Therefore, $f^{- 1} (C \cup D) = f^{- 1} (C) \cup f^{- 1} (D)$ .

d) $f^{- 1} (C \cap D) = f^{- 1} (C) \cap f^{- 1} (D)$

Proof.

$f^{- 1} (C \cap D) \subseteq f^{- 1} (C) \cap f^{- 1} (D)$ : If $x \in f^{- 1} (C \cap D)$ , then $f (x) \in C \cap D$ , which means $f (x) \in C$ and $f (x) \in D$ . Thus, $x$ is in both $f^{- 1} (C)$ and $f^{- 1} (D)$ .
$f^{- 1} (C) \cap f^{- 1} (D) \subseteq f^{- 1} (C \cap D)$ : If $x$ is in both $f^{- 1} (C)$ and $f^{- 1} (D)$ , then $f (x)$ is in both $C$ and $D$ , and therefore in their intersection $C \cap D$ . Hence, $x \in f^{- 1} (C \cap D)$ .

So, $f^{- 1} (C \cap D) = f^{- 1} (C) \cap f^{- 1} (D)$ . $◻$