Tao Analysis I - 3.4.3

Exercise 3.4.3

Let $A$, $B$ be two subsets of a set $X$, and let $f:X \to Y$ be a function. Show that $f(A \cap B) \subseteq f(A) \cap f(B)$, that $f(A) \setminus f(B) \subseteq f(A \setminus B)$, $f(A∪B)= f(A) \cup f(B)$. For the first two statements, is it true that the $\subseteq$ relation can be improved to $=$?

Before we dive into the exercise, let's draw a picture to aid our thinking.

Show that $f(A \cap B) \subseteq f(A) \cap f(B)$

We need to show that

$$y \in f(A \cap B) \implies y \in f(A) \cap f(B)$$

If $y \in f(A \cap B)$ then there exists an $x \in (A \cap B)$ such that $y = f(x)$. 

Now, 

$$x \in (A \cap B) \iff (x \in A) \land (x \in B)$$

So,

$$ y \in f(A \cap B) \implies (y \in f(A)) \land (y \in f(B))$$

Note, this is a one-way implication because for a function, given an element of the domain, we can only say there is only one element in the co-domain. For an element in the co-domain, we can't say there is only one corresponding element of the domain.

Thus, we have shown that if $y \in f(A \cap B)$ then $y \in f(A) \cap f(B)$. 

This is equivalent to $f(A \cap B) \subseteq f(A) \cap f(B)$. $\square$

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A \cap B) = f(\emptyset) = \emptyset$, the empty set.
• $f(A) \cap f(B) = \{1\} \cap \{1\} = \{1\}$.

Here $f(A) \cap f(B) \nsubseteq f(A \cap B)$, a counter-example showing that equality is not possible for general $f$. $\square$

As an extra exercise, let's ask if $f$ injective would enable equality? If $f$ is injective, by definition that means $f(s) = f(t) \implies s=t$.

So if $y \in f(A) \cap f(B)$ then $y \in f(A) \land y \in f(B)$. So both of the following must be true:

• There exists an $a \in A$ such that $y=f(a) \in f(A)$.
• There exists a $b \in B$ such that $y=f(b) \in f(B)$.

We have $y=f(a)=f(b)$, which, if $f$ is injective, means $a=b$. Now this $x=a=b$ is in both $A$ and $B$, that is $x \in (A \cap B)$. This gives us $y=f(x) \in f(A \cap B)$. 

So we have shown that if $f$ is injective, $f(A) \cap f(B) \subseteq f(A \cap B)$. This, combined with the previous result that $f(A \cap B) \subseteq f(A) \cap f(B)$, gives us equality $f(A \cap B) = f(A) \cap f(B)$. $\square$

Show that $f(A) \setminus f(B) \subseteq f(A \setminus B)$

We need to show that $y \in f(A) \setminus f(B) \implies y \in f(A \setminus B)$.

The meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. 

This means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. (see note at bottom)

This, $x \in A \land x \notin B$. That is, $x \in (A \setminus B)$. This implies $f(x) = y \in f(A \setminus B)$. 

Thus we have shown that $f(A) \setminus f(B) \subseteq f(A \setminus B)$.

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A) \setminus f(B) = \{1\} \setminus \{1\} = \emptyset$, the empty set.
• $f(A \setminus B) = f(\{-1\} \setminus\{1\}) = f(\{-1\}) = \{1\}$.

Here $f(A \setminus B) \nsubseteq f(A) \setminus f(B)$, a counter-example showing that equality is not possible for general $f$. $\square$

Show that $f(A∪B)= f(A) \cup f(B)$

We need to show both:

• $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$
• $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$

If $y \in f(A \cup B)$ then there exists an $x \in A \cup B$ such that $y = f(x) \in f(A \cup B)$. That $x$ could be in $A$ or it could be in $B$, or both. That means $(x \in A) \lor (x \in B)$. Let's consider both cases:

• $x \in A \implies y = f(x) \in f(A) \in f(A) \cup f(B)$
• $x \in B \implies y = f(x) \in f(B) \in f(A) \cup f(B)$

This means $y = f(x) \in f(A) \cup f(B)$. 

We have shown $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$.

If $y \in f(A) \cup f(B)$ that means $y \in f(A)$ or $y \in f(B)$, or both. Let's consider both cases.

• If $y \in f(A)$ then there exists an $x \in A$ such that $y = f(x) \in f(A) \in f(A) \cup f(B)$.
• If $y \in f(B)$ then there exists an $x \in B$ such that $y = f(x) \in f(B) \in f(A) \cup f(B)$.

This $x$ is in $A$ or $B$, or both. And both cases imply $y = f(x) \in f(A \cup B)$.

We have shown $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$.

By showing both implications, we have shown $f(A∪B)= f(A) \cup f(B)$. $\square$

Note: Negation of Quantifiers

Above we said that the meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. We then said this means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. 

For the second bullet point we used negation of quantifiers - we "swap the quantifiers and negate the predicate".

$$ \neg [\exists x: f(x)=y] \quad \iff \quad \forall x [f(x) \neq y]$$

You can read more here: (pdf) and (pdf).