$f(X \cap Y) \subset f(X) \cap f(Y) $

Question

In class we had the following function which I intend to prove for my own peace of mind.

Let $M$ and $N$ be sets and $f: M \longrightarrow N$ a function: \begin{align}f: P(M) &\longrightarrow P(N) \tag{P denotes Powerset} \\ X & \longmapsto \lbrace f(x) \mid x \in X \rbrace \end{align} Let $X,Y \subset M$ then: \begin{align} f(X \cap Y) \subset f(X) \cap f(Y) \end{align} Note: In our book (Zorich Analysis) $\subset$ denotes a subset, not necessarily a real subset.

Question: Is $f(X \cap Y) \subset f(X) \cap f(Y)$ a correct statement?

So I know that I need to show $A \subset B \iff x \in A \longrightarrow x \in B$. I tried as follows: \begin{align}f (X \cap Y) = \lbrace f(x) \mid x \in (X \cap Y)\rbrace \end{align} I guess for the proof to be correct I should mention here that $X \cap Y \neq \emptyset$ because $x \in \emptyset$ would be a contradiction to start with. I continued like this: \begin{align} x \in \lbrace f(x) \mid x \in X \wedge x \in Y\rbrace \longrightarrow x \in \lbrace f(x) \mid x \in X\rbrace \wedge x \in \lbrace f(x) \mid x \in Y\rbrace \end{align} I don't know if this step is correct or not, but it seemed like it to me, I could conclude from there that: \begin{align}x \in \lbrace f(x) \mid x \in X \wedge x \in Y\rbrace &\longrightarrow x \in \lbrace f(x) \mid x \in X\rbrace \wedge x \in \lbrace f(x) \mid x \in Y\rbrace \\ & \longrightarrow x \in f(X) \wedge x \in f(Y) \\ &\longrightarrow x \in ( f(X) \cap f(Y)) \end{align} Would this complete the proof? Or do I also need to show that $f(X) \cap f(Y) \not \subset f(X \cap Y)$ ?

Answer 1

The simple way of doing this is to show $f(X \cap Y) \subset f(X)$ and $f(X \cap Y) \subset f(Y)$, because a subset of $f(X) \cap f(Y)$ is the same as a subset of $f(X)$ and $f(Y)$. (More generally, a subset of $A \cap B$ is the same as a subset of $A$ and of $B$.)

But both follow from the more general statement that if $A \subset B$, then $f(A) \subset f(B)$. Indeed, any element of $f(A)$ is of the form $f(a)$ for some $a \in A$, whence $a \in B$, whence $f(a) \in f(B)$, i.e., any element of $f(A)$ is an element of $f(B)$. Now apply this statement to $A = X \cap Y$ and $B = X$ or $B= Y$.

Answer 2

Here is an alternative proof. The simplest way I see here is to use the definitions and predicate logic.

Using a slightly different notation, the definition of $\;f[A]\;$ is that $$ b \in f[A] \;\equiv\; \langle \exists a : a \in A : f(a) = b \rangle $$ for all $\;b\;$. So the elements in the left hand side are those for which \begin{align} & b \in f[X \cap Y] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$"} \\ & \langle \exists a : a \in X \cap Y : f(a) = b \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$"} \\ (*)\;\phantom{\equiv} & \langle \exists a : a \in X \land a \in Y : f(a) = b \rangle \\ \end{align} And similarly for the right hand side, we have \begin{align} & b \in f[X] \cap f[Y] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$"} \\ & b \in f[X] \land b \in f[Y] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$, twice"} \\ (**)\;\phantom{\equiv} & \langle \exists a : a \in X : f(a) = b \rangle \land \langle \exists a : a \in Y : f(a) = b \rangle \\ \end{align} Now predicate logic teaches us that the former $(*)$ implies the latter $(**)$ (since $\;\exists\;$ distributes over $\;\land\;$ in one direction), which proves $\;f[X \cap Y] \subseteq f[X] \cap f[Y]\;$ by the definition of $\;\subseteq\;$.