# Naive Set Theory: Functions

## Function Classes

Functions can be classified based on some properties of how often elements in their domains map to elements in their ranges.

 A function $f : A \rightarrow B$ is injective if $f(a) = f(b)$ implies that $a = b$ for any two elements $a$ and $b$ in $A$. An injective function is also said to be one-to-one, since each element in the codomain is mapped to by at most one element in the domain. An injective function is called an injection. Pretty intense, right? Injection A function $f : A \rightarrow B$ is surjective if for each element $b \in B$ there exists at least one $a \in A$ such that $f(a) = b$. In other words, a function is surjective if all the elements in its codomain are mapped to by at least one element in its domain. A surjective function is also said to be onto, although this term is harder to remember. Most people think of it as "the other special one that's not one-to-one." A surjective function is also called a surjection. Surjection A function is bijective if it is both injective and surjective. A bijective function is also called a (wait for it) bijection. Bijection There is no special name for a function that is neither an injection nor a surjection. Perhaps we could call it a nonjection? General function or "nonjection"

## Problems

1. Let $f : A \rightarrow B$ be an injective function, and let $A' \subseteq A$. Prove that $A' = f^{-1}(f(A'))$.

First we show that $A' \subseteq f^{-1}(f(A'))$. This was shown in the first problem in the Images and Preimages section.

Next we show that $f^{-1}(f(A')) \subseteq A'$. Let $a \in f^{-1}(f(A'))$. Because $f$ is injective, there is a unique $f(a) \in f(A')$. As a result $a \in A$. Therefore, $f^{-1}(f(A')) \subseteq A'$.

2. Let $f : A \rightarrow B$ be a surjective function, and let $B' \subseteq B$. Prove that $B' = f(f^{-1}(B))$.

First we show that $B' \subseteq f(f^{-1}(B))$. Let $b \in B'$. Because $f$ is surjective, there is at least one $a \in A$ such that $b = f(a)$. Then $a \in f^{-1}(B)$. It follows that $f(a) \in f(f^{-1})(B)$, so $b \in f(f^{-1}(B))$. Therefore $B' \subseteq f(f^{-1}(B))$

The second part of this proof showing $f(f^{-1}(B)) \subseteq B'$ is given in the second problem in the Images and Preimages section.