# Show that if $f:A\rightarrow B$ is surjective then...

1. Oct 3, 2015

### Potatochip911

1. The problem statement, all variables and given/known data
Show that if $f:A\rightarrow B$ is subjective and $H\subseteq B$ then $f(f^{-1}(H))=H$, give an example to show the equality need to hold if $f$ if not surjective.

2. Relevant equations
3. The attempt at a solution

I know that I want to show that an element $x\in H$ by starting from the LHS but I'm not really sure what to do. In a similar proof in my notes we had a step where we did something like this:

Let $x\in f(f^{-1}(H))=H$ then $\exists y\in f^{-1}(H)$ such that $x=f(y)$, I'm not really sure where to go from here or what the point of this step is. I'm also confused by $f^{-1}(H)$, if I'm understanding this question correctly $H$ is the domain of the function so what exactly is $f^{-1}(H)$ and why is letting a $y$ exist in this useful? And lastly I'm not sure how the definition of a surjective function is useful:
A function $f$ is said to be surjective (or map A onto B) if $f(A)=B$, that is if the range $R(f)=B$.

2. Oct 3, 2015

### Krylov

"subjective" should be "surjective" and "need to hold" should be "need not hold".

The equality is what you need to prove, so you cannot write it down yet.

$A$ is the domain of the function, $B$ is the codomain of the function and $H$ is nothing more than a subset of $B$. The notation $f^{-1}(H)$ simply means, by definition,
$$f^{-1}(H) := \{x \in A\,:\, f(x) \in H\}$$
With this in place, you are asked to prove that $f(f^{-1}(H)) = H$. For this you should prove two inclusions: $f(f^{-1}(H)) \subseteq H$ and $f(f^{-1}(H)) \supseteq H$. Why don't you start with the first inclusion?

3. Oct 3, 2015

### Potatochip911

Yea I'm not quite sure why I wrote subjective there since right after that I wrote surjective. I also accidentally tagged on the $=H$ to $x\in f(f^{-1}(H))$. Going back to the proof:

Let $x\in f(f^{-1}(H))$ then $\exists y\in f^{-1}(H)$ such that $x=f(y)$, now I want to show that $x\in H$ using the fact that $f:A\rightarrow B$ is surjective but I can't seem to figure it out. I'm not sure if this is useful or not but if $\exists y\in f^{-1}(H)$ then it seems logical that $f(y)\in H$ but still not sure where to go from here.

4. Oct 3, 2015

### vela

Staff Emeritus
You don't need to use the fact that f is surjective for this part.

5. Oct 4, 2015

### Potatochip911

Is $f(y)\in H$ going in the right direction or do I need to think of something else entirely?

6. Oct 4, 2015

### Fredrik

Staff Emeritus
Yes, it's the correct way to proceed. If x=f(y), and f(y) is an element of H, then x is...

Note that what you're using to justify that step is just the definition of the notation $f^{-1}(H)$.

7. Oct 4, 2015

### Potatochip911

Oh so since $x=f(y)$ and from $\exists y\in f^{-1}(H)$ such that $f(y)\in H$ then $\exists h\in H$ such that $x=h$ which implies $x\in H$?

8. Oct 5, 2015

### Fredrik

Staff Emeritus
Right, but it's a bit of a detour to bring in a new variable h. Also, (this is a bit of a nitpick) when you have mentioned that "there's a $y\in f^{-1}(H)$ such that...", then it's a bit weird to talk about the properties of y in the next sentence. The problem is that the "there exists" makes y a dummy variable; it can be replaced by any other variable without changing the meaning of the statement. So (very) strictly speaking, it's not clear what y the next sentence is referring to.

This is how I would write the part of the proof that you have completed so far:

Let $x\in f(f^{-1}(H))$. Let $y\in f^{-1}(H)$ be such that $f(y)=x$. (Such a $y$ exists because $x\in f(f^{-1}(H))$). Since $y\in f^{-1}(H)$, we have $f(y)\in H$. Since $x=f(y)$ and $f(y)\in H$, we have $x\in H$.

9. Oct 5, 2015

### Potatochip911

Yea I suppose it is quite odd what I did with $y$ there, I will definitely keep that in mind for future proofs. So now I want to show that $H\subseteq f(f^{-1}(H))$ given that $f:A\rightarrow B$ is subjective and that $H\subseteq B$:

I'm not too confident about this but it's all I could come up. Let $x\in H$, $f:A\rightarrow B$ is surjective so we will be using the inverse image definition of $f^{-1}$ i.e. $f^{-1}(H):=\{ x\in A : f(x)\in H\}$, Since $f$ is surjective there exists an element $a\in A$ for every $b\in B$ so $a\in f^{-1}(H)$ and $f(a)\in f(f^{-1}(H))$, since $f(a)\subseteq B$ and $H\subseteq B$ we have that $x\in f(f^{-1}(H))$

10. Oct 5, 2015

### Fredrik

Staff Emeritus
I can't really follow what you're doing there. The "there exists" makes $a$ a dummy variable in the first part of the sentence, and then you make a claim about $a$. That claim isn't true for every possible $a$ that corresponds to some $b\in B$.

I would start with this: You know that $x\in H\subseteq B$ and that $f:A\to B$ is surjective. This should tell you something about $x$ that will be useful.

11. Oct 5, 2015

### Potatochip911

What I'm trying to say (I think it's similar to your suggestion) is that $x\in H\subseteq B$ and since $f:A\rightarrow B$ is surjective then we know that for every $b\in B$ there exists $a\in A$ such that $f(a)=b$ and from the definition of the inverse image we have that $f^{-1}(H)\in A$. Therefore, there exists and element $h\in H$ such that $f^{-1}(h)=a\Rightarrow f(f^{-1}(h))=f(a)$. Since $f(a)=b\in B$, $H\subseteq B$ and using the fact that $h\in H$ we have that $H\in f(f^{-1}(H)$. Sorry if this is pretty much the exact same thing as I did before.

12. Oct 5, 2015

### Fredrik

Staff Emeritus
Right. And if something holds "for all b in B", and x is in B, then it holds for x.

Right.

Do you mean such that the first equality holds or such that the implication holds? I assume the former. The claim doesn't entirely make sense. You're saying something about $a$, but $a$ was a dummy variable in an earlier statement and is undefined now. If you're going to make a statement P(a) about a variable $a$, then you need to do one of the following three things:

1. Assign a value to $a$ first: Define $a=1$.
2. Make $a$ the target of a "for all": $\forall a~P(a)$
3. Make $a$ the target of a "there exists": $\exists a~P(a)$.

If you meant "for all $a\in A$ such that $f(a)=b$, there's an $h\in H$ such that $f^{-1}(\{h\})=\{a\}$", then the sentence is true for some choices of $b$ and false for others. (It's false for all b that are not in H).

The notation $f^{-1}(H)$ makes sense even when f is not invertible, but the notation $f^{-1}(h)$ doesn't.

13. Oct 6, 2015

### Potatochip911

Yea I meant that the first equality would hold. So it seems like saying there exists an $h\in H$ is a bad idea since h is a single variable? Is that why $f{^-1}(h)$ doesn't make sense?

14. Oct 6, 2015

### Fredrik

Staff Emeritus
$f^{-1}(h)$ denotes the output that you get when the function $f^{-1}$ takes $h$ as input. If $f$ isn't invertible, there is no $f^{-1}$ and therefore no $f^{-1}(h)$. There is however a $f^{-1}(\{h\})$, because this is a notation for the set $\{x\in X| f(x)\in\{h\}\}$, which is equal to $\{x\in X| f(x)=h\}$.

15. Oct 6, 2015

### Potatochip911

So if I go back to the definition of the inverse part where I say:

From the definition of the inverse we have that $f^{-1}(H)\in A$ so $\exists a\in A$ such that $\forall a\in f(a)$ the following implications hold $f^{-1}(H)=a \Rightarrow f(f^{-1}(H))=f(a)$ and then since $f:A\to B$ is surjective we know that $A$ will map to all elements of $B$ and since $H\subseteq B$ and $f(a)\subseteq B$ we have $f(a)\subseteq H\Rightarrow f(f^{-1}(H))\in H$

16. Oct 7, 2015

### Fredrik

Staff Emeritus
The definition of "inverse" isn't involved here. $f^{-1}(H)$ is the preimage of $H$ under $f$, not the image of $H$ under $f^{-1}$. So the definition you need to use is the definition of "preimage". It should tell you that $f^{-1}(H)$ isn't an element of $A$.

It doesn't make sense to have "there exists" and "for all" target the same variable in a single statement. It's impossible to tell which one of these statements is the one you meant to make
\begin{align*}
\exists x\in A\quad \forall y\in f(a)\quad f^{-1}(H)=x \Rightarrow f(f^{-1}(H))=f(x)\\
\exists x\in A\quad \forall y\in f(a)\quad f^{-1}(H)=x \Rightarrow f(f^{-1}(H))=f(y)\\
\exists x\in A\quad \forall y\in f(a)\quad f^{-1}(H)=y \Rightarrow f(f^{-1}(H))=f(x)\\
\exists x\in A\quad \forall y\in f(a)\quad f^{-1}(H)=y \Rightarrow f(f^{-1}(H))=f(y)\\
\end{align*}
Unfortunately none of them makes sense. $f(a)$ denotes an element of $B$, not a subset of $A$ or $B$. $f^{-1}(H)$ denotes a subset of $A$, not an element of $A$. $f(f^{-1}(H))$ is a subset of $B$ and $f(a)$ is an element of $B$.

17. Oct 10, 2015

### Potatochip911

Okay so I should just define the preimage as $f^{-1}(H)=\{x\in A: f(x)\in H\}$; $f:A\to B$ is surjective and we want to show that $H\subseteq f(f^{-1}(H))$, Let $x\in H$, then after applying the preimage we get $f^{-1}(x)\in f^{-1}(H)$, and then multiplying by the function we get $f(f^{-1}(H))\in f^{-1}(H)$, I reread the entire thread again and there's something I don't understand from the first proof.

Can you explain why such a $y$ exists because $x\in f(f^{-1}(H))$? Is it because if $y\in f^{-1}(H)$ can we write $x\in f(f^{-1}(H))\Rightarrow x\in f(y)$?

18. Oct 10, 2015

### Fredrik

Staff Emeritus
This isn't correct. $f^{-1}(x)$ exists only if $f$ is invertible. Since the problem doesn't tell you that $f$ is injective, the notation $f^{-1}(x)$ (where x is an element of B rather than a subset of B), shouldn't appear anywhere in the proof.

Is there a typo here? Did you mean $f(f^{-1}(x))\in H$? If $f$ is invertible and $f^{-1}(x)\in f^{-1}(H)$, then it's correct to conclude that $f(f^{-1}(x))\in H$, but the correct justification is that it follows immediately from the definition of $f^{-1}(H)$. You should make sure that you understand why.

$x$ is an arbitrary element of $f(f^{-1}(H))$. By definition of the image of a set under f, we have $f(f^{-1}(H))=\{f(y)|y\in A\}$. The right-hand side is an abbreviated notation for $\{z\in B|\exists y\in A~f(y)=z\}$.

If you prefer the abbreviated notation: Since $x\in\{f(y)|y\in A\}$, there's a $y\in A$ such that $f(y)=x$.

If you prefer the full notation: Since $x\in\{z\in B|\exists y\in A~f(y)=z\}$, there's a $y\in A$ such that $f(y)=x$.

19. Oct 10, 2015

### Potatochip911

Yep I accidentally put the $f^{-1}$ there.

Let $y\in H$, from the definition of the preimage we have that $f^{-1}(H):=\{a\in A: f(a)\in H\}$ and since the function is surjective we have that $\forall h\in H \exists a\in A$ such that $f(a)=h$. Therefore, there's an element $a\in A$ such that $f(a)=y$, so we have $a\in A$ and $f(a)\in H$ and from $f(a)=y\Rightarrow f(a)\in H$, so we have shown that $y\in f^{-1}(H)$, Is this correct? Obviously this isn't the entire proof since I have to show $y\in f(f^{-1}(H))$ but it seems to at least be getting me somewhere.

20. Oct 10, 2015

### Fredrik

Staff Emeritus
This part is excellent.

It is not. It looks like you used the result you found (there's an $a\in A$ such that $f(a)=y$) only to "prove" the assumption that you started with ($y\in H$), and then jumped to the conclusion that $y\in f^{-1}(H)$. Note that H is a subset of B, and $f^{-1}(H)$ is a subset of $A$.

Let $y\in H$. Let $a\in A$ be such that $f(a)=y$. (You have explained why such an $a$ must exist). To make progress from this point, you need to find a better way to use that $f(a)=y\in H$.