# Naive Set Theory: Functions

## Images and Preimages

For a function $f : A \rightarrow B$ and a subset $A' \subseteq A$, the image of $A'$ under $f$ is the set of all values $b \in B$ such that $b = a$ for some $a \in A'$ and is denoted as $f(A')$. In set builder notations, $f(A') = \{ f(a) : a \in A' \}$. Note that $f(A')$ has a subset of the domain between the parentheses and denotes a set of points called the image of $A'$ under $f$, and $f(a)$ has an element of the domain between the parentheses and denotes a value in the image set of $f$. Also note that the image of $A$ itself under $f$ is in fact the image set of $f$, so the reuse of the word image isn't entirely malicious.

Similarly, the preimage of a subset $B' \subseteq B$ under $f$ is the set of all $a \in A$ such that $f(a) = b$ for some $b \in B'$. The preimage is denoted as $f^{-1}(B')$. In set builder notation, $f^{-1}(B') = \{ a \in A : f(a) \in B' \}$. Note that the notation $f^{-1}(B')$ has so far only been defined when a subset of the codomain is between the parentheses. Placing an element of the codomain between the parentheses instead denotes use of the inverse of $f$, which will be defined in a later section.

## Problems

1. For any function $f : A \rightarrow B$, show that if $A' \subseteq A$, then $f(A') \subseteq f(A)$.

Let $f(a) \in f(A')$. Then $a \in A$, so $f(a) \in f(A)$. Therefore, $f(A') \subseteq f(A)$.

2. Let $f : A \rightarrow B$ be a function, and let $A' \subseteq A$. Show that $A' \subseteq f^{-1}(f(A'))$, then give an example of where $A' \neq f^{-1}(f(A'))$.

Proof: Let $a \in A'$. Then by the definition of image, $f(a) \in f(A')$. By the definition of preimage, $a \in f^{-1}(f(A'))$. Therefore $A' \subseteq f^{-1}(f(A'))$.

Example: Let $f : A \rightarrow B$ be a function where $A = \{-2,-1,0,1,2\}$ and $B = \{0,1,4\}$ whose rule is $f(x) = x^2$, and let $A' = \{0,1,2\}$. Then $f(A') = \{0,1,4\}$. However, we can see that $f^{-1}(f(A')) = \{-2,-1,0,1,2\}$.

3. Let $f : A \rightarrow B$ be a function, and let $B' \subseteq B$. Show that $f(f^{-1}(B')) \subseteq B'$, then give an example of where $f(f^{-1}(B')) \neq B'$.

Proof: Let $b \in f(f^{-1}(B'))$. Then by the definition of image, $b = f(a)$ for some $a \in f^{-1}(B')$. Since $a \in f^{-1}(B')$, then by the definition of preimage, $f(a) \in B'$. Therefore $b \in B'$, and therefore $f(f^{-1}(B')) \subseteq B'$.

Example: Let $f : A \rightarrow B$ be a function where $A = \{1,2,3\}$, $B=\{1,2,3,4\}$, and $f(x) = x + 1$, and let $B' = \{1,2\}$. Then $f(f^{-1}(B')) = f(\{1\}) = \{2\}$.

4. Let $f : A \rightarrow B$ be a function, and let $A_0, A_1 \subseteq A$. Prove the following properties of images

1. Inclusion is preserved: $A_0 \subseteq A_1 \implies f(A_0) \subseteq f(A_1)$.
2. Unions are preserved: $f(A_0 \cup A_1) = f(A_0) \cup f(A_1)$
3. The image of an intersection is a subset of the intersection of the images: $f(A_0 \cap A_1) \subseteq f(A_0) \cap f(A_1)$
4. The difference of two images is a subset of the image of the difference: $f(A_0) - f(A_1) \subseteq f(A_0 - A_1)$.
1. If $f(a) \in f(A_0)$, then $a \in A_0$. By definition of subset, $a \in A_1$. Therefore $f(a) \in f(A_1)$. Thus $f(A_0) \subseteq f(A_1)$.

2. First we show that $f(A_0) \cup f(A_1) \subseteq f(A_0 \cup A_1)$. Let $a \in A_0$ such that $f(a) \in f(A_0)$. Then $f(a) \in f(A_0 \cup A_1)$. Likewise, let $a \in A_1$ such that $f(a) \in f(A_1)$. Then $f(a) \in f(A_0 \cup A_1)$. Therefore $f(A_0) \cup f(A_1) \subseteq f(A_0 \cup A_1)$.

Next we show that $f(A_0 \cup A_1) \subseteq f(A_0) \cup f(A_1)$. Let $a \in (A_0 \cup A_1)$ such that $f(a) \in f(A_0 \cup A_1)$. Then $a$ is either in $A_0$ or $A_1$. If $a \in A_0$, then $f(a) \in f(A_0)$. Alternatively, if $a \in A_1$, then $f(a) \in f(A_1)$. Then $f(a) \in f(A_0) \cup f(A_1)$. Therefore $f(A_0 \cup A_1) \subseteq f(A_0) \cup f(A_1)$.

3. Let $a \in A_0 \cap A_1$ such that $f(a) \in f(A_0 \cap A_1)$. Then $a \in A_0$ and $a \in A_1$. Therefore $f(a) \in f(A_0)$ and $f(a) \in f(A_1)$. Therefore $f(A_0 \cap A_1) \subseteq f(A_0) \cap f(A_1)$.

4. Let $f(a) \in f(A_0) - f(A_1)$. Then $f(a) \in f(A_0)$ but $f(a) \notin f(A_1)$. Therefore $a \in A_0$ but $a \notin A_1$, so $a \in A_0 - A_1$. Accordingly, $f(a) \in f(A_0 - A_1)$. Therefore $f(A_0) - f(A_1) \subseteq f(A_0 - A_1)$.

5. Let $f : A \rightarrow B$ be a function, and let $B_0, B_1 \subseteq B$. Prove the following properties of preimages

1. Inclusions are preserved: $B_0 \subseteq B_1 \implies f^{-1}(B_0) \subseteq f^{-1}(B_1)$.

2. Unions are preserved: $f^{-1}(B_0 \cup B_1) = f^{-1}(B_0) \cup f^{-1}(B_1)$.

3. Intersections are preserved: $f^{-1}(B_0 \cap B_1) = f^{-1}(B_0) \cap f^{-1}(B_1)$.

4. Set differences are preserved: $f^{-1}(B_0 - B_1) = f^{-1}(B_0) - f^{-1}(B_1)$.

1. Let $a \in f^{-1}(B_0)$. Then $f(a) \in B_0$. By definition of subset, $f(a) \in B_1$. Therefore $a \in f^{-1}(B_1)$. As a result, $f^{-1}(B_0) \subseteq f^{-1}(B_1)$.

2. First we show that $f^{-1}(B_0 \cup B_1) \subseteq f^{-1}(B_0) \cup f^{-1}(B_1)$. Let $a \in f^{-1}(B_0 \cup B_1)$. Then $f(a) \in B_0 \cup B_1$. If $f(a) \in B_0$, then $a \in f^{-1}(B_0)$. Alternatively, if $f(a) \in B_1$, then $a \in f^{-1}(B_1)$. Therefore $f^{-1}(B_0 \cup B_1) \subseteq f^{-1}(B_0) \cup f^{-1}(B_1)$.

Next we show that $f^{-1}(B_0) \cup f^{-1}(B_1) \subseteq f^{-1}(B_0 \cup B_1)$. Let $a \in f^{-1}(B_0) \cup f^{-1}(B_1)$. If $a \in f^{-1}(B_0)$, then $a \in f^{-1}(B_0 \cup B_1)$. Likewise, if $a \in f^{-1}(B_1)$, then $a \in f^{-1}(B_0 \cup B_1)$. Therefore $f^{-1}(B_0) \cup f^{-1}(B_1) \subseteq f^{-1}(B_0 \cup B_1)$.

3. First we show that $f^{-1}(B_0 \cap B_1) \subseteq f^{-1}(B_0) \cap f^{-1}(B_1)$. Let $a \in f^{-1}(B_0 \cap B_1)$. Then $f(a) \in B_0 \cap B_1$. By definition of intersection, $f(a) \in B_0$ and $f(a) \in B_1$. Then $a \in f^{-1}(B_0)$ and $a \in f^{-1}(B_1)$. Therefore $a \in f^{-1}(B_0) \cap f^{-1}(B_1)$, so $f^{-1}(B_0 \cap B_1) \subseteq f^{-1}(B_0) \cap f^{-1}(B_1)$.

Net we show that $f^{-1}(B_0) \cap f^{-1}(B_1) \subseteq f^{-1}(B_0 \cap B_1)$. Let $a \in f^{-1}(B_0) \cap f^{-1}(B_1)$. Then $a \in f^{-1}(B_0)$ and $a \in f^{-1}(B_1)$. Therefore $f(a) \in B_0$ and $f(a) \in B_1$, so $f(a) \in B_0 \cap B_1$. As a result, $a \in f^{-1}(B_0 \cap B_1)$. Therefore $f^{-1}(B_0) \cap f^{-1}(B_1) \subseteq f^{-1}(B_0 \cap B_1)$.

4. Set differences are preserved: $f^{-1}(B_0 - B_1) = f^{-1}(B_0) - f^{-1}(B_1)$.

First we show that $f^{-1}(B_0 - B_1) \subseteq f^{-1}(B_0) - f^{-1}(B_1)$. Let $a \in f^{-1}(B_0 - B_1)$. Then $f(a) \in B_0 - B_1$. By definition of set difference, $f(a) \in B_0$ but $f(a) \notin B_1$. As a result, $a \in f^{-1}(B_0)$ but $a \notin f^{-1}(B_1)$, so $a \in f^{-1}(B_0) - f^{-1}(B_1)$. Therefore $f^{-1}(B_0 - B_1) \subseteq f^{-1}(B_0) - f^{-1}(B_1)$.

Next we show that $f^{-1}(B_0) - f^{-1}(B_1) \subseteq f^{-1}(B_0 - B_1)$. Let $a \in f^{-1}(B_0) - f^{-1}(B_1)$. Then $a \in f^{-1}(B_0)$ but $a \notin f^{-1}(B_1)$. Therefore $f(a) \in B_0$ but $f(a) \notin B_1$. As a result, $f(a) \in B_0 - B_1$, so $a \in f^{-1}(B_0 - B_1)$. Therefore $f^{-1}(B_0) - f^{-1}(B_1) \subseteq f^{-1}(B_0 - B_1)$.