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.