# Prove that $f[f^{-1} f[X]]] = f[X]$

I'm trying to prove that $f[f^{-1} f[X]]] = f[X]$, where $f: A\to B$ and $X \subset A$. I have already proved that $X \subset f^{-1}[f[X]]$.

My thoughts: First, I know that $f[X] = \{f(x):x \in X\} =\{f(x) : x \in f^{-1}[f[X]]\}$ (because $X \subset f^{-1}[f[X]]$). This is the set of the functions of the form $f[f^{-1} f[X]]]$, so we see that $f[f^{-1} f[X]]] = f[X]$. Or can I just say that $f[X] = \{f(x):x \in X\}$ implies that $f(x) \in f[X]$ and, as $X \subset f^{-1}[f[X]]$, we conclude that $f[X] =f[f^{-1} f[X]]]$.

Is this right? If so, is it a sufficient proof?

Let $S$ and $T$ be partially ordered sets, where the order relations are both denoted with $\le$. If $\varphi\colon S\to T$ and $\psi\colon T\to S$ are order preserving maps such that $s\le\psi(\varphi(s))$ and $\varphi(\psi(t))\le t$, for all $s\in S$ and $t\in T$, then $$\varphi(s)=\varphi(\psi(\varphi(s))),\quad \psi(t)=\psi(\varphi(\psi(t)))$$ for all $s\in S$ and $t\in T$.

Proof: obvious. ;-) Well, from $s\le\psi(\varphi(s))$ we deduce $\varphi(s)\le\varphi(\psi(\varphi(s)))$ because $\varphi$ is order preserving. On the other hand, setting $t=\varphi(s)$, we know that $\varphi(\psi(t))\le t$, which is the same as saying that $\varphi(\psi(\varphi(s)))\le\varphi(s)$.

The verification for the other equality is just the same.

Now, let $S=P(A)$ and $T=P(B)$ be the power sets, with the order relation on them being the inclusion. We set $\varphi(X)=f[X]$ and $\psi(Y)=f^{-1}[X]$, for $X\in P(A)$ and $Y\in P(B)$. These maps are order preserving and $$X\subseteq\psi(\varphi(X))=f^{-1}[f[X]]$$ while $$\varphi(\psi(Y))=f[f^{-1}[Y]]\subseteq Y$$

Note that idea can be vastly generalized: if $F$ is a left adjoint of the functor $G$, then $FGF$ and $GFG$ are naturally equivalent to $F$ and $G$ respectively.

In the setting above, considering $S$ and $T$ as categories in the usual way, $\varphi$ and $\psi$ are functors because they are order preserving; the inequalities $s\le\psi(\varphi(s))$ and $\varphi(\psi(t))\le t$ are just the statement that $\varphi$ is a left adjoint of $\psi$.

The ordered set case is an example of a (monotone) Galois connection; in fact from the inequalities we can easily prove that, for $s\in S$ and $t\in T$, we have $$\varphi(s)\le t\quad\text{if and only if}\quad s\le \psi(t)$$ Indeed, suppose $\varphi(s)\le t$; then $\psi(\varphi(s))\le\psi(t)$, so $s\le\psi(t)$. The converse is similar.

I have already proved that $X \subset f^{-1}[f[X]]$

Then yes, applying $f$ to both sides yields $f(X) \subset f(f^{-1}[f[X]])$.

But to prove equality you also need the reverse inclusion $f(f^{-1}[f[X]])\subset f(X)$. This is best done as a separate lemma:

For every $Y\subset B$ it holds that $f(f^{-1}(Y)) \subset Y$.

(Which is basically a tautology, once you recall that $f^{-1}(Y)$ means.) Then use this lemma with $Y=f(X)$.