# Functions Sets

• Apr 22nd 2013, 11:07 AM
chrisgg1212
Functions Sets
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.
• Apr 22nd 2013, 11:55 AM
emakarov
Re: Functions Sets
Quote:

Originally Posted by chrisgg1212
If they're not the same size, which one must be larger?

Are both of them finite by assumption? If not, then larger in what sense? It seems to me that it may happen that neither of these sets is contained in the other one.
• Apr 22nd 2013, 03:50 PM
chrisgg1212
Re: Functions Sets
I don't know what you mean.

That is how the question was handed to me for practice...I don't know what to do.
• Apr 22nd 2013, 04:20 PM
HallsofIvy
Re: Functions Sets
practice for what class? Do you not know what "finite sets" are?
• Apr 22nd 2013, 04:45 PM
chrisgg1212
Re: Functions Sets
yes finite # of elements.
• Apr 22nd 2013, 05:00 PM
Plato
Re: Functions Sets
Quote:

Originally Posted by chrisgg1212
I don't know what you mean.
That is how the question was handed to me for practice...I don't know what to do.

If the sets are finite then $\|A\|=\|B\|$, that is they have the same cardinality.

If the sets are infinite the look for examples.
• Apr 23rd 2013, 07:42 AM
johng
Re: Functions Sets
Hi,
Here's the answer to your question. From your posting, I'm not sure you can understand anything except the example. So I think it was probably an unreasonable problem assignment.

Attachment 28106
• Apr 23rd 2013, 11:08 AM
emakarov
Re: Functions Sets
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 $|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]]|$.