Asking for feedback on correctness and style (Velleman. How to Prove it. Exercise 5.4.1.b)

Question

Level: first-year undergraduate learning proof writing.

Questions:

• Is my proof of the amended claim correct?
• How is the style? 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 justify the answers with counterexamples and proofs. The section concerns images of sets and they are defined as:

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) \}$$

---

Exercise 5.4.1/(b). Suppose $f: A \rightarrow B$. Suppose $W$ and $X$ are subsets of $A$. Will it always be true that $f(W \setminus X) = f(W) \setminus f(X)$?

My solution:

No. Let $A = \{ 1,2 \}$ and $B=\{ 3 \}$. Let $f=\{ (1,3), (2,3) \}$. Suppose $W=A$ and $X= \{ 2 \}$. Then $f(W \setminus X) = \{ 3 \}$ while $f(W) \setminus f(X) = \varnothing$.

However, we can amend the false statement to create the following theorem.

Theorem. Suppose $f: A \rightarrow B$, and $W$ and $X$ are subsets of $A$. Then $f(W) \setminus f(X) \subseteq f(W \setminus X)$. Furthermore, if $f$ is one-to-one, then $f(W \setminus X) = f(W) \setminus f(X)$.

Proof. Suppose $y \in f(W) \setminus f(X)$. Then $y \in f(W)$ and $y \notin f(X)$. Then we can choose some $x \in W$ such that $f(x) = y$, and since $y \notin f(X)$, it follows that $x \notin X$. In other words, $x \in W \setminus X$. Hence $y \in f(W \setminus X)$. Since $y$ was an arbitrary element of $f(W) \setminus f(X)$, we conclude that $f(W) \setminus f(X) \subseteq f(W \setminus X)$.

Now suppose $f$ is one-to-one and $y \in f(W \setminus X)$. Then there is some $x \in W \setminus X$ such that $f(x) = y$. In other words, $x \in W$ and $x \notin X$. Thus $y \in f(W)$, and we prove by contradiction that $y \notin f(X)$. Suppose $y \in f(X)$. Then there is some $x' \in X$, such that $y = f(x')$. But $y=f(x)$, and since $f$ is one-to-one, $x = x'$. Since $x \in W \setminus X$ and $x' \in X$, we have a contradiction. Hence $y \in f(W) \setminus f(X)$. Since $y$ was an arbitrary element of $f(W \setminus X)$, it follows that $f(W \setminus X) \subseteq f(W) \setminus f(X)$. Combining with the previous result, we have $f(W \setminus X) = f(W) \setminus f(X)$. $\square$

Answer 1

Firstly, I think that this question is well structured. On the style and veracity of your proofs:

Since $y$ was an arbitrary element of $f(W \setminus X)$, it follows that $f(W \setminus X) \subseteq f(W) \setminus f(X)$. Combining with the previous result, we have $f(W \setminus X) = f(W) \setminus f(X)$. $\square$

I would perhaps replace "Combining with the previous result $f(W \setminus X) = f(W) \setminus f(X)$" with, "Since $f(W) \setminus f(X) \subseteq f(W \setminus X)$ also, we have $f(W \setminus X) = f(W) \setminus f(X)$." This is a minor and contrived point but may remove ambiguity ("what result?").

Have I provided enough scaffolding for the assumed level?

I am a high-school student and did not need any more glossing. being too explicit may convolute the argument. Overall I think that the proof is friendly, well-written and correct.

Next is my own disproof of the first false proposition. I have defined membership for $f(W\setminus X)$ and $f(W)\setminus f(X)$ to make matters clearer.

Proposition. Suppose $f:A\rightarrow B$ and $W\subset A$ and $X\subset A$. Then $f(W\setminus X)=f(W)\setminus f(X)$.

Disproof. Let $b\in B$ throughout.

$b\in f(W\setminus X)$ iff there exists $y\in W$ such that $y\notin X$ and $f(y)=b$, and $b\in f(W)\setminus f(X)$ iff there exists $y\in W$ such that $f(y)=b$ and for all $x\in X$, $f(x)\neq b$.

Suppose $f$ is not injective. If there exists $ y\in X $ such that $y\notin W$ and $f(y)=b$ and there exists $z\in W$ such that $z\notin X$ and $f(z)=b$ then $b\in f(W\setminus X)$ and $b\notin f(W)\setminus f(X)$.

It follows that it is not true that $b\in f(W\setminus X)$ iff $b\in f(W)\setminus f(X)$ in complete generality. Then, using the definition of set equality, nor is $f(W\setminus X)=f(W)\setminus f(X)$. $\square$

I suppose a criticism of the style in my proof is that I started a sentence with a mathematical symbol, however I do not see a problem with that in this case. See this answer.

I base my style somewhat on the structure of symbolic logical sentences, and sometimes when one is stuck it is useful to work out proofs or parts of proofs in symbolic logic. Of course, some linguistic variation improves readability: e.g. "then," "it follows that," and so forth.