Level: first-year undergraduate learning proof writing.
Questions:
- Is my proof of the amended claim correct?
- How is the style of my proof? Have I provided enough scaffolding for the assumed level? Or is it too verbose?
Context:
Section 5.4 of How to Prove It by Velleman asks the reader to verify whether certain statements are true, and if not, come up with conjectures, and justify the answers with counterexamples and proofs. The section concerns images of sets and inverse images that are defined as follows:
Definition 5.4.1. Suppose $f: A \rightarrow B$ and $X \subseteq A$. Then the image of $X$ under $f$ is the set $f(X)$ defined as follows. $$ f(X) = \{ f(x) \mid x \in X \} = \{ b \in B \mid \exists x \in X (f(x) = b) \}$$
If $Y \subseteq B$, then the inverse image of $Y$ under $f$ is the set $f^{-1}(Y)$ defined as follows: $$ f^{-1}(Y) = \{a \in A \mid f(a) \in Y \}$$
(Note that the function $f$ in Definition 5.4.1. may fail to be one-to-one or onto, and as a result $f^{-1}$ may fail to be a function from $B$ to $A$, and for $y \in B$, the notation "$f^{-1}(y)$" may be meaningless. However, even in this case Definition 5.4.1 still assigns a meaning to the notation "$f^{-1}(Y)$" for $Y \subseteq B$.)
Exercise 5.4.2/(d). Let $f: A \rightarrow B$. Suppose $Y$ and $Z$ are subsets of $B$. Will it always be true that $Y \subseteq Z \leftrightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$?
My solution:
No. As a counterexample, let $A = \{1\}$, $B=\{2,3\}$, and $f=\{(1,2)\}$. Suppose $Y = \{2,3\}$ and $Z=\{2\}$. Then $f^{-1}(Y) \subseteq f^{-1}(Z)$, but not $Y \subseteq Z$.
However, we may amend the question to arrive at the following theorem.
Theorem. Let $f:A \rightarrow B$. Suppose $Y$ and $Z$ and subsets of $B$. Then $Y \subseteq Z \rightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$. Furthermore, if $f$ is onto, then $Y \subseteq Z \leftrightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$.
Proof. Suppose $Y \subseteq Z$. Let $x \in A$ such that $x \in f^{-1}(Y)$. Then $f(x) \in Y$. Since $Y \subseteq Z$, it follows that $f(x) \in Z$. Since $x \in A$ and $f(x) \in Z$, we have $x \in f^{-1}(Z)$. Since $x$ was an arbitrary element of $f^{-1}(Y)$, we conclude that $f^{-1}(Y) \subseteq f^{-1}(Z)$. Therefore, $Y \subseteq Z \rightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$.
Now suppose that $f$ is onto. Suppose $f^{-1}(Y) \subseteq f^{-1}(Z)$. Let $y \in Y$. Since $f$ is onto, we can choose some $x \in A$ such that $f(x)=y$. Then $x \in f^{-1}(Y)$. Since $f^{-1}(Y) \subseteq f^{-1}(Z)$, it follows that $x \in f^{-1}(Z)$, so $f(x) \in Z$. Or in other words, $y \in Z$. Since $y$ was an arbitrary element of $Y$, we have $Y \subseteq Z$. Hence $Y \subseteq Z \leftarrow f^{-1}(Y) \subseteq f^{-1}(Z)$, and since $Y \subseteq Z \rightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$, we conclude that $Y \subseteq Z \leftrightarrow f^{-1}(Y) \subseteq f^{-1}(Z)$. $\square$
