26 - Composition of Functions

!Screenshot 2023-11-10 at 2.07.56 PM.png
!Screenshot 2023-11-10 at 2.12.40 PM.png
!Screenshot 2023-11-10 at 2.13.07 PM.png
!Screenshot 2023-11-10 at 2.36.16 PM.png
!Screenshot 2023-11-10 at 2.38.30 PM.png
!Screenshot 2023-11-10 at 2.39.27 PM.png
!Screenshot 2023-11-10 at 2.40.54 PM.png

Not communicative
Are associative

HW 26

Ben Finch

E 26.1
a)
Proof.
Assume $f$ and $g$ are injective. By definition, a function $h$ is injective if for all elements $x_{1}$ and $x_{2}$ in the domain of $h$ , $h (x_{1}) = h (x_{2)} ⟹ x_{1} = x_{2}$ . Let $x_{1}, x_{2} \in A$ and assume $(g \circ f) (x_{1}) = (g \circ f) (x_{2})$ . By the definition of composition, $g (f (x_{1})) = g (f (x_{2}))$ . Since $g$ is injective, $f (x_{1}) = f (x_{2})$ . And since $f$ is also injective, $x_{1} = x_{2}$ . Thus, $g \circ f$ is injective. $◻$

b)
Proof. We work directly.

Assume $g \circ f$ is surjective. By definition, a function $h$ is surjective if for every element $y$ in the codomain of $h$ , there exists an element $x$ in the domain of $h$ such that $h (x) = y$ . Let $y \in C$ . Since $g \circ f$ is surjective, there exists an $x \in A$ such that $(g \circ f) (x) = y$ . By the definition of composition, $g (f (x)) = y$ . Let $b = f (x)$ , where $b \in B$ because $f$ maps from $A$ to $B$ . Therefore, $g (b) = y$ . Since $y$ was an arbitrary element in $C$ and we found a $b \in B$ such that $g (b) = y$ , $g$ is surjective. $◻$

E 26.2
The composition of $f \circ i d_{A}$ is defined that for each element $a \in A$ , $(f \circ i d_{A}) (a) = f (i d_{A} (a))$ . Since $i d_{A} (a) = a$ for each $a \in A$ , we can substitute this into the composition, getting $f (i d_{A} (a)) = f (a)$ . Since $f (a)$ is the result of applying $f$ directly to each element $a \in A$ , it follows that $f \circ i d_{A} = f$ .

Therefore, $f \circ i d_{A} = f$ . $◻$

E 26.3
Disproof.
Define the function $f : A \to B$ . Let $A = {1, 2}$ and $B = {a, b}$ . Define $f$ such that $f (1) = a$ and $f (2) = a$ . Note that $f$ is not surjective since no element in $A$ is mapped to $b$ in $B$ .
Define the function $g : B \to C$ . Let $C = {x, y}$ . Define $g$ such that $g (a) = x$ and $g (b) = y$ . $g$ is surjective because every element in $C$ is a second component in $g$ . Defines $g \circ f : A \to C$ . For $1$ in $A$ , $g (f (1)) = g (a) = x$ . For $2$ in $A$ , $g (f (2)) = g (a) = x$ . In this composition, no element of $A$ is mapped to $y$ in $C$ . Thus, even though $g$ is surjective, the composition $g \circ f$ is not surjective, as there is no element in $A$ that maps to $y$ in $C$ through $g \circ f$ . This disproves the statement. $◻$

E 26.4
Disproof.
Define the function $g : R \to R$ as $g (x) = x^{2}$ . Define the function $f : R \to R$ as $f (x) = \sqrt{x}$ . We see that $g (f (x)) = {\sqrt{x}}^{2} = x$ . Let $x_{1}, x_{2} \in R$ . Assume that $g (f (x_{1})) = g (f (x_{2}))$ . This gives us:

x_{1} = x_{2}

Therefore, $g (f (x))$ is injective. Take $z = 1$ and $y = - 1$ . Then $g (- 1) = g (1) = 1$ . So $g (x)$ is not injective. Therefore, the implication that if $g \circ f$ is injective then $g$ is injective is false. $◻$

E 26.5
Let $f : A \to B$ and $g : B \to C$ be bijective functions. Per Theorem 26.12, since $f$ and $g$ are both bijective, $g \circ f$ is bijective. By theorem 26.15, $(g \circ f)^{- 1}$ is a function since $g \circ f$ is bijective. We want to show that for every element $c \in C$ , $(g \circ f)^{- 1} (c) = (f^{- 1} \circ g^{- 1}) (c)$ . Let $c \in C$ . Since $g$ is bijective, there exists a unique $b \in B$ such that $g (b) = c$ . Similarly, as $f$ is bijective, there exists a unique $a \in A$ such that $f (a) = b$ . By the definition of function composition, $(g \circ f) (a) = g (f (a)) = g (b) = c$ . Since $g \circ f$ is bijective, its inverse function, $(g \circ f)^{- 1}$ , will map $c$ back to $a$ , so $(g \circ f)^{- 1} (c) = a$ . Also, $g^{- 1} (c) = b$ and $f^{- 1} (b) = a$ , so $(f^{- 1} \circ g^{- 1}) (c) = f^{- 1} (g^{- 1} (c)) = f^{- 1} (b) = a$ . Therefore, for every $c \in C$ , $(g \circ f)^{- 1} (c) = (f^{- 1} \circ g^{- 1}) (c)$ , proving that $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ . $◻$

E 26.6
Fix $f : R - 5 \to R - 3$ given by

f (x) = \frac{3 x + 1}{x - 5}

Proof.

(Injective)
Let $a_{1}, a_{2} \in R - 5$ . Assume $f (a_{1)} = f (a_{2})$ . We find

\begin{aligned} \frac{3 a_{1} + 1}{a_{1} - 5} & = \frac{3 a_{2} + 1}{a_{2} - 5} \\ (3 a_{1} + 1) (a_{2} - 5) & = (3 a_{2} + 1) (a_{1} - 5) \\ 3 a_{1} a_{2} + a_{2} - 15 a_{1} - 5 & = 3 a_{1} a_{2} + a_{1} - 15 a_{2} - 5 \\ - 16 a_{1} & = - 16 a_{2} \\ a_{1} & = a_{2} \end{aligned}

So $f$ is injective.

(Surjective)

Let $b \in R - {3}$ . Define $a = \frac{5 b + 1}{b - 3}$ . We see that

\begin{aligned} f (a) & = \frac{3 a + 1}{x - 5} \\ = \frac{3 (\frac{5 b + 1}{b - 3}) + 1}{\frac{5 b + 1}{b - 3} - 5} \\ = \frac{\frac{15 b + 3}{b - 3} + 1}{\frac{5 b + 1}{b - 3} - 5} \\ = \frac{\frac{16 b}{b - 3}}{\frac{16}{b - 3}} \\ = \frac{16 b}{16} \\ = b \end{aligned}

Hence, for every $b \in R - {3}$ , we have found an $a \in R$ (specifically $a = \frac{5 b + 1}{b - 3}$ ) such that $f (a) = b$ . Therefore, $f$ is surjective.

Since $f$ is surjective and injective, $f$ is bijective. $◻$

$f^{- 1} (y) = \frac{5 y + 1}{y - 3}$

E 26.7
a) $f^{- 1} = {(2, 1), (3, 2), (1, 3)}$
b) $f \circ f = {(1, 3), (2, 1), (3, 2)}$
c) $f \circ f \circ f = {(1, 1), (2, 2), (3, 3)}$
d) The function $f^{n}$ will be:

${(1, 1), (2, 2), (3, 3)}$ if $n$ is a multiple of 3.
The function $f$ if $n$ mod 3 is 1.
The function $f^{2}$ if $n$ mod 3 is 2.