Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is as follows :

Let $f:A\rightarrow B$ be a surjective function and let $C$ be a subset of $B$. Prove $f(f^{-1}(C)) = C$.

I understand what the question is asking. It's basically saying that for some element in $C$, the inverse function points to an element in the domain, $A$, and then for the element in $A$, the function points back to the element in $C$.

Here's my attempt at the proof :

Let $c$ be contained in $C$, which is also contained in $B$ because $C$ is a subset of $B$. Let $b$ be contained in $B$, and let $a$ be contained in $A$. $f:A\rightarrow B$ gives $f(a) = b$. Assume that the $b$ in $f(a) = b$ is in the set $C$, which is possible because $C$ is a subset of $B$. Then, $c = b$, so we have $f(a) = c$. Then, for $f^{-1}(C)$, we would have $f^{-1}(b) = a$, and therefore $f^{-1}(c) = a$. Then for $f(a)$, we have $c$, which is again in the set $C$. Hence, $f(f^{-1}(C)) = C$.

If this is incorrect, I'd appreciate feedback and a starting point on where to go with this proof!

Also, I apologize for the poor formatting, I'm not familiar with how to format these types of problems with HTML commands and such.

share|improve this question
    
$f^{-1}(b)$ does not make sense, because $f$ not necessary bijective. –  Hamou Jul 22 at 23:29
1  
@Hamou $f^{-1}(b)$ is the set of all elements that map to $b$. –  Joe Johnson 126 Jul 22 at 23:32
1  
$f^{-1}(b)$ is an element, but the set is $f^{-1}(\{b\})$ –  Hamou Jul 22 at 23:35
1  
@Hamou Convention is to not use the brackets in this situation. –  Joe Johnson 126 Jul 22 at 23:36
    
what is the sense for $f^{-1}(b)=a$, as sets or elements. –  Hamou Jul 22 at 23:38

3 Answers 3

up vote 3 down vote accepted

You have a good start, but there are some issues here.

First, make sure you are clear on all definitions. Note $C$ and $f(f^{-1}(C))$ are sets, so to prove that they are equal you must show that they contain all the same elements. A typical way to do this is by showing $C \subset f(f^{-1}(C))$ and $f(f^{-1}(C)) \subset C$. In your proof, it looks like you only check that $C \subset f(f^{-1}(C))$.

Second, note that $f^{-1}$ is not defined as a function. Rather, $f^{-1}(C)$ for $C$ a subset of $B$ is defined to be the set of all $x \in A$ such that $f(x) \in C$. In particular, it does not make sense to write $f^{-1}(b)=a$ for a single element $b$. You can consider the inverse image of the subset $\{b\}$, which is typically written as $f^{-1}(b)$. However, in this case you would write $a \in f^{-1}(b)$, not that the two are equal -- there may be other elements in the set $f^{-1}(b)$.

Third, make sure that you use the fact that $f$ is surjective in your proof! When you write "f:A->B gives f(a) = b," how do you know that, for any $b\in B$, you can find an $a$ making this statement true? (In general, if you are given a hypothesis that you do not explicitly use in your solution, you should double check your proof very carefully to be sure you have not made a mistake and/or omitted an explanation. )

share|improve this answer
1  
I would also add that saying "Let $a\in A$ and $b\in B$. Then $f(a)=b$" is misleading. It is not true that for any $a\in A$ and $b\in B$ one has $f(a)=b$. Be more clear by saying, "Let $a\in A$. Then let $b=f(a)$." –  Joe Johnson 126 Jul 22 at 23:44
    
I'll attempt C is a subset of f(f^1(C) first: f^-1(C) is the set of all a in A such that f(a) is in C. Also, because f is surjective, we have f(a) = b, and because C is a subset of B, we have f(a) = c. If f(a) = c, then a is in the set f^-1(C) which implies f(a) is in f(f^-1(C)). Then, because f(a) = c, we have c is in f(f^-1(C)). Hence, C is a subset of f(f^-1(C)). Is this correct? I looked at a the below comments a bit, but I tried to go further in detail to explain some of the implied steps in order to show that I understand it now. Also, now I see the necessity of surjectivity! –  jonba Jul 23 at 1:20
    
When you say "Also, because f is surjective, we have f(a) = b, and because C is a subset of B, we have f(a) = c," it's a little ambiguous. What are $b$ and $c$? You have to be careful to specify where each element lives, so to speak. Let me try to modify this particular sentence of yours, to illustrate what I mean: "Also, because $f$ is surjective, given any $b \in B$ there exists an $a \in A$ so that $f(b)=a$. Because $C \subset B$, given $c\in C$ we have $f(a)=c$ for some $a \in A$." Beyond this, your proof looks good. You have the right idea, just be careful to phrase things precisely! –  Morgan O Jul 23 at 1:53
    
I see, thank you very much! I'll work on the phrasing - proofwriting is tough! –  jonba Jul 23 at 2:02
    
Yes, it's definitely something to get used to. Keep working at it, and it will get a lot easier. (And make sure you do the other containment as well -- i.e. show that $f(f^{-1}(C)) \subset C$). –  Morgan O Jul 23 at 2:05

$f^{-1}(C) =\{ a \in A | f(a)\in C \}$. So let $z\in f^{-1}(C)$. Then $f(z) \in C$ by definition. Therefore $f(f^{-1}(C)) \subset C$.

Let $c\in C$. Then $c \in B$, so by surjectivity there exists $a\in A$ such that $f(a)=c$. In other words, $a\in f^{-1}(C)$, and so $f(a) \in f(f^{-1}(C))$. Thus, $c\in f(f^{-1}(C))$. Therefore $C\subset f(f^{-1}(C))$. Together this gives $C= f(f^{-1}(C))$

share|improve this answer

At some point, you need to use the fact that $f$ is surjective. Each time you introduce a new variable, you should first think about why such a variable should even exist.

Let's start by showing that $f(f^{-1}(C)) \supseteq C$. To this end, choose any $c \in C$. Now since $C \subseteq B$, we know that $c \in B$. Hence, since $f$ is surjective, we know that there exists some $a \in A$ such that $f(a) = c$. But then since $f^{-1}(C) = \{x \in A \mid f(x) \in C\}$, we know that $a \in f^{-1}(C)$. But then since $f(D) = \{f(d) \mid d \in D\}$, we conclude that $c = f(a) \in f(f^{-1}(C))$, as desired.

Hopefully you can do the other direction yourself.

share|improve this answer

Your Answer

 
discard

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.