Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
I think so. Consider X to be a one element set, and f the selfmap of X. I think f can be used to separate words in L and U. –  The Masked Avenger Jul 6 at 20:15
@TheMaskedAvenger: If I'm not mistaken, any bijection will completely fail to separate words (i.e., it will only separate those that are necessarily distinguished for reasons of degree or parity), whereas by my argument any non-bijection will separate all words. –  Eric Wofsey Jul 6 at 20:32
I was actually thinking of constant maps. However neither U nor L produce constant maps (after at most one iteration), so the idea above won't likely work. Also, I was musing and posting before seeing your answer. –  The Masked Avenger Jul 6 at 20:43
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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