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?

Thank you for your help.


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.