Proofs Regarding Functions

# Proofs Regarding Functions

We will now look at some proofs regarding functions, direct images, inverse images, etc… Before we look at such proofs, let's first recall some very important definitions:

 Definition: A function $f$ is called an injection, injective function, or one-to-one function if for all $m, n \in A$ where $m \neq n$ satisfies that $f(m) \neq f(n)$.
 Definition: A function $f$ is called a surjection, surjective function, or an onto function if $B = R(f)$, that is, the codomain of $f$ is equal to the range of $f$. For every $b \in B$, $b = f(a)$ for some $a \in A$.
 Definition: A function $f$ is called a bijection or bijective function if $f$ is both injective and surjective, that is, for all $m, n \in A$ where $m \neq n$ satisfies $f(m) \neq f(n)$, and $B = R(f)$, so for every $b \in B$, $b = f(a)$ for some $a \in A$.

We also want to acknowledge the following implications that will be very useful:

• $f(x) \in f(E)$ implies that there exists an element $e \in E$ such that $f(e) = f(x)$.
• $x \in f^{-1}(H)$ implies that there exists an element $f(x) \in H$ such that $f^{-1}(f(x)) = x$.

## Example 1

Prove that if $f : A \to B$ is a bijective function then $\forall a \in A$, $f^{-1} ( f(a)) = a$.

We note that from the context of our example that the notation $f^{-1}$ represents the inverse function and NOT an inverse image.

• Proof: Let $a \in A$, and let $x = f^{-1}(f(a))$. By the definition of the inverse function we have that $x = f^{-1}(f(a))$ implies that $f(x) = f(a)$. Now since $f$ is a bijective function, it is injective by definition, so then if $f(x) = f(a)$ then $x = a$. So $a = f^{-1}(f(a))$.

## Example 2

Prove that if $f : A \to B$ is a bijective function then $\forall b \in B$, $f(f^{-1}(b)) = b$.

Once again we note from our context that $f^{-1}$ represents the inverse function.

• Proof: Let $b \in B$. Since $f$ is a bijective function it is surjective by definition, so there exists an $a \in A$ such that [$f(a) = b$. Taking the inverse of both sides we get that $a = f^{-1}(b)$. And since $f$ is a function then $f(a) = f(f^{-1}(b))$. But $f(a) = b$ and so $b = f(f^{-1}(b))$.

## Example 3

Prove that if $f : A \to B$ is a surjective function and $H \subseteq B$ then $f(f^{-1}(H)) = H$.

We note from the context of our example that $f^{-1}$ represents the inverse image of a set and NOT an inverse function. Therefore we have to prove the set $f(f^{-1}(H)) \subseteq H$ and $H \subseteq f(f^{-1}(H))$.

• Proof: $\Rightarrow$ We first want to show that $f(f^{-1}(H)) \subseteq H$. Let $f(x) \in f(f^{-1}(H))$. It follows by the definition of the direct image of a set that then $x \in f^{-1} (H)$. And by the definition of the inverse image image of a set we have that $f(x) \in H$. So therefore $f(f^{-1}(H)) \subseteq H$.
• $\Leftarrow$ We now want to show that $H \subseteq f(f^{-1}(H))$. Let $f(x) \in H$. Now since $f$ is surjective there exists an element $x \in A$ such that $f(x) = y$. So then $y \in H$. This implies that $x \in f^{-1} (H)$ and so $f(x) \in f(f^{-1} (H)$. Therefore we have that $f(f^{-1}(H)) = H$.

## Example 4

Prove that if $f : A \to B$ is an injective function and $E \subseteq A$ then $f^{-1} (f (E)) = E$.

We note that from the context of our example that the notation $f^{-1}$ represents the inverse image of a set and NOT an inverse function. Therefore we have to prove the set $f^{-1} ( f(E)) = E$ by first showing that $f^{-1} (f (E)) \subseteq E$ and $E \subseteq f^{-1} (f (E))$.

• Proof: $\Rightarrow$ We first want to show that $f^{-1} (f (E)) \subseteq E$. Let $x \in f^{-1} (f (E))$. It follows by the definition of the direct image of a set that since $f(x) \in f(E)$, there exists an element $e \in E$ such that $f(x) = f(e)$. Now since $f$ is an injective function we have that $x = e$ and so then $x \in E$. Therefore $f^{-1} (f (E)) \subseteq E$.
• $\Leftarrow$ We now want to show that $E \subseteq f^{-1} (f (E))$. Let $x \in E$. By the definition of direct image we have that $f(x) \in f(E)$. Furthermore, $f^{-1}(f(x)) = x \in f^{-1}(f(E))$ by the definition of an inverse image of a set. So $x \in f^{-1} (f (E))$ and therefore $E \subseteq f^{-1} (f (E))$. We conclude $f^{-1} (f (E)) = E$ if $f$ is injective.