Is the monoid of taking iterated images and inverse images freely generated by the image and inverse image operation?

Question

Let $\mathcal{F}$ denote the class of all functions. Let $U,L:\mathcal{F}\rightarrow\mathcal{F}$ denote the mappings where if $f:X\rightarrow Y$, then $U(f):P(X)\rightarrow P(Y),L(f):P(Y)\rightarrow P(X)$ are the mappings where $U(f)(R)=f[R]$ and $L(f)(R)=f^{-1}[R]$ are the image and inverse image functions. Let $\mathcal{M}$ be the submonoid of the monoid of all functions from $\mathcal{F}$ to $\mathcal{F}$ generated by $U$ and $L$. Therefore if $M\in\mathcal{M}$, then there is some $n$ where if $f:X\rightarrow Y$, then $M(f):P^{n}(X)\rightarrow P^{n}(Y)$ or $M(f):P^{n}(Y)\rightarrow P^{n}(X)$ where $P^{n}(X)$ is the iterated power set of $X$. Is $\mathcal{M}$ freely generated by $U$ and $L$?

Answer 1

Yes, it is. The idea is that given an element of $\mathcal{M}$, you can detect whether the last step of it was $L$ or $U$, and then undo the steps one by one to recover a unique expression for it.

First, note that $U$ and $L$ are injective: we can recover any function $f$ from either $U(f)$ or $L(f)$. Now let $M\in\mathcal{M}$ have degree $n$ (i.e., it is a composition of $n$ copies of $U$ or $L$; clearly there is only one such $n$). By induction on $n$, we show that $M$ has a unique expression as a composition of $U$s and $L$s. Since $U$ is injective, if we can write $M=UN$ for $N\in\mathcal{M}$, then such an $N$ is unique, and similarly for $L$. By induction, we know that such an $N$ has a unique expression as a composition of $U$s and $L$s. Thus there are at most two expressions for $M$: one starting with $U$, and one starting with $L$. It suffices to show that we can't have both.

If $M=UN$, then note that for any $f$, $M(f)$ must map singletons to singletons. I claim that this is not true for any operator of the form $LN$. Indeed, if $LN(f)$ maps singletons to singletons for every $f$, then $N(f)$ must be a bijection for every $f$. But this is impossible, since we can choose $X$ and $Y$ to be finite sets of different cardinality. Thus no element of $\mathcal{M}$ can be both of the form $UN$ and the form $LN$, as desired.