Suppose that
f : A->B is onto and g : A->B is 1-to-1. Let S be a
subset of A. Consider the sets g^-1[f[S]] and f^-1[g[S]]. If they're not the
same size, which one must be larger?
Need alittle help on this problem.
Intuitively, there are the following four principles.
(1) The image of a set with respect to any function is no larger than the original set because multiple elements can be mapped into one.
(2) The image of a set with respect to a 1-1 function has the same size as the original set because each element is mapped into exactly one element.
(3) The preimage of a set with respect to an onto function is no smaller then the original set because every element has at least one preimage and possible more.
(4) The preimage of a set with respect to a 1-1 function is no larger than the original set because not every element may have a preimage (unless the function is also onto), and if there is a preimage, it is unique.
Using these principles, we have $\displaystyle |g^{-1}[f[S]]| \stackrel{(4)}{\le} |f[S]| \stackrel{(1)}{\le} |S| \stackrel{(2)}{=\vphantom{\le}} |g[S]| \stackrel{(3)}{\le} |f^{-1}[g[S]]|$.