# How to prove $f(\bigcap_{\alpha \in A}U_{\alpha}) \subseteq \bigcap_{\alpha \in A}f(U_{\alpha})$?

$f(\bigcap_{\alpha \in A} U_{\alpha}) \subseteq \bigcap_{\alpha \in A}f(U_{\alpha})$

Suppose $y \in f(\bigcap_{\alpha \in A} U_{\alpha})$
$\implies f^{-1}(y) \in \bigcap_{\alpha \in A} U_{\alpha} \implies f^{-1}(y) \in U_{\alpha}$ for all $\alpha \in A$

$\implies y \in f (U_{\alpha})$ for all $\alpha \in A \implies y \in \bigcap_{\alpha \in A}f (U_{\alpha})$

$\bigcap_{\alpha \in A}f(U_{\alpha}) \subseteq f(\bigcap_{\alpha \in A} U_{\alpha})$

Suppose $y \in \bigcap_{\alpha \in A}f(U_{\alpha})\implies y \in f(U_{a})$ for all $\alpha \in A$
$\implies f^{-1}(y)\in U_{a}$ for all $a\in A$

$\implies f^{-1}(y)\in \bigcap_{a \in A}U_{a} \implies y \in f(\bigcap_{a \in A}(U_{a})$

Therefore

$f(\bigcap_{\alpha \in A} U_{\alpha}) \subseteq \bigcap_{\alpha \in A}f(U_{\alpha})$

Please let me know if my proof works, also I don’t fully know how to do the following. Please give me some help.

Give an example of proper containment. Find a condition on f that would ensure equality.

#### Solutions Collecting From Web of "How to prove $f(\bigcap_{\alpha \in A}U_{\alpha}) \subseteq \bigcap_{\alpha \in A}f(U_{\alpha})$?"

Let $y\in f(\cap_{\alpha\in A}U_{\alpha})$, be arbitrary.
Then there exists an $x\in\cap_{\alpha\in A}U_{\alpha}$, for which $y=f(x)$. Since $x\in\cap_{\alpha\in A}U_{\alpha}$, we know that $x\in U_{\alpha}$ for each $\alpha\in A$. $y=f(x)\in f(U_{\alpha})$ for each $\alpha\in A$, implies

$$y\in \cap_{\alpha\in A}f(U_{\alpha})$$
since $y$ was arbitrary we conclude

$$f(\cap_{\alpha\in U_{\alpha}})\subseteq \cap_{\alpha\in A}f(U_{\alpha})$$

There is no “$f^{-1}(y)$” in general. Although by definition $y$
is equal to $f(x)$ for some $x\in\bigcap U_\alpha$, that $x$ might
not be unique. So take an $x\in\bigcap U_\alpha$ and repeat your
argument with $x$ replacing “$f^{-1}(y)$”.

You then attempt to prove the reverse inclusion: $\bigcap f(U_\alpha) \subseteq f(\bigcap U_\alpha)$. But this is false. Consider just two $U_\alpha$, call them $U$ and $V$. They may be disjoint, yet there
are $x\in U$, $y\in V$ with $f(x)=f(y)$ so that $f(U)\cap f(V)\ne\emptyset$.

You are probably misled by the similar relation holding for $f^{-1}$:
$$\bigcap_\alpha f^{-1}(U_\alpha)= f^{-1}\Bigl(\bigcap_\alpha U_\alpha\Bigr)$$
which is true and whose proof goes essentially like yours, with $f$ and $f^{-1}$ interchanged.

However, your assignment asks you to find an example of proper containment, which should make you suspect equality doesn’t generally hold.

Indeed, it doesn’t hold in general; it does when $f$ is injective.

If $f\colon X\to Y$ and $V\subseteq Y$, then
$$f^{-1}(V)=\{x\in X:f(x)\in V\}$$
In other words, saying $x\in f^{-1}(U)$ is the same as saying $f(x)\in V$.

To the contrary, if $U\subseteq X$,
$$f(U)=\{y\in Y:\text{there exists x\in U with y=f(x)}\}$$
You cannot say $y\in f(U)$ if and only if $f^{-1}(y)\in U$; what you can say, when you take $y\in f(U)$, is that there is $x\in U$ with $f(x)=y$.

Now try and fix your proof.

May I propose a ‘logical’ approach? Here is what happens if you expand the definitions, to go from the level of set theory to that of logic, and then reason on the logic level.

But first, what are the definitions?% \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\subcalch}[1]{\\ \quad & \quad #1 \\ \quad &} \newcommand{\subcalc}{\quad \begin{aligned} \quad & \\ \bullet \quad & } \newcommand{\endsubcalc}{\end{aligned} \\ \\ \cdot \quad &} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} % The simplest formulations I know are $$\tag{0} y \in f\left[X\right] \;\equiv\; \langle \exists x : f(x) = y : x \in X \rangle$$ and $$\tag{1} z \in \cap_{\alpha \in A} U_{\alpha} \;\equiv\; \langle \forall \alpha : \alpha \in A : z \in U_\alpha \rangle$$ Here I’m using notations from Dijkstra et al. (see, e.g., EWD1300), and I’ve changed your notation slightly, to allow us to distinguish $\;f\left[X\right]\;$ from $\;f(x)\;$. Using this notation, your statement is $$\tag{2} f\left[\cap_{\alpha \in A} U_{\alpha}\right] \;\subseteq\; \cap_{\alpha \in A}f\left[U_{\alpha}\right]$$

Let’s first calculate which elements $\;y\;$ are in the left hand side of $\Ref{2}$:
$$\calc y \in f\left[\cap_{\alpha \in A} U_{\alpha}\right] \op=\hint{definition \Ref{0}} \langle \exists x : f(x) = y : x \in \cap_{\alpha \in A} U_{\alpha} \rangle \op=\hint{definition \Ref{1}} \langle \exists x : f(x) = y : \langle \forall \alpha : \alpha \in A : x \in U_\alpha \rangle \rangle \tag{L} \endcalc$$

And then the same for the right hand side:
$$\calc y \in \cap_{\alpha \in A}f\left[U_{\alpha}\right] \op=\hint{definition \Ref{1}} \langle \forall \alpha : \alpha \in A : y \in f\left[U_{\alpha}\right] \rangle \op=\hint{definition \Ref{0}} \langle \forall \alpha : \alpha \in A : \langle \exists x : f(x) = y : x \in U_{\alpha} \rangle \rangle \tag{R} \endcalc$$

Now, comparing $\Ref{L}$ and $\Ref{R}$, we immediately see that we can apply the logic rule $\;\exists\forall \then \forall\exists\;$, and conclude that $\;\Ref{L} \then\Ref{R}\;$ for all $\;y\;$. And by the definition of $\;\subseteq\;$ that proves $\Ref{2}$.

Finally, note how this proof also clearly shows why not (in general) the $\;\supseteq\;$ inclusion direction is true: this is because we need to appeal to the fundamentally unidirectional rule $\;\exists\forall \then \forall\exists\;$.