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

[Potatochip911]

Homework Statement

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.

Homework Equations

3. The Attempt at a Solution [/B]

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

 

[S.G. Janssens]

Homework Statement

Show that if f:A→Bf:A\rightarrow B is subjective and H⊆BH\subseteq B then f(f−1(H))=Hf(f^{-1}(H))=H, give an example to show the equality need to hold if ff if not surjective.

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

Let $x \in f(f^{-1}(H)) = H$

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

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

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

 

[Potatochip911]

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

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.

 

[vela]

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.

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

 

[Potatochip911]

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

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

 

[Fredrik]

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

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)$.

 

[Potatochip911]

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)$.

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

 

[Fredrik]

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

 

[Potatochip911]

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

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

 

[Fredrik]

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

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.

 

[Potatochip911]

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.

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.

 

[Fredrik]

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$

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

and from the definition of the inverse image we have that $f^{-1}(H)\in A$.

Right.

Therefore, there exists and element $h\in H$ such that $f^{-1}(h)=a\Rightarrow f(f^{-1}(h))=f(a)$.

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.

 

[Potatochip911]

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.

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?

 

[Fredrik]

$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\}$.

 

[Potatochip911]

$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\}$.

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$

 

[Fredrik]

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$

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

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

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

 

[Potatochip911]

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

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.

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

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

 

[Fredrik]

Let $x\in H$, then after applying the preimage we get $f^{-1}(x)\in f^{-1}(H)$,

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.

and then multiplying by the function we get $f(f^{-1}(H))\in f^{-1}(H)$

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.

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

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

 

[Potatochip911]

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

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.

 

[Fredrik]

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

This part is excellent.

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?

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

 

[Potatochip911]

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

So I am now thinking something like this. We have $a\in A$ and $f(a)\in H$, since $f(a)=y\in H$. There exists an element $h\in H$ such that $f^{-1}(\{h\})=a$. Therefore from $f(a)=y$ we have $f(a)=f(f^{-1}(\{h\}))=y\in H$

 

[Fredrik]

So I am now thinking something like this. We have $a\in A$ and $f(a)\in H$, since $f(a)=y\in H$. There exists an element $h\in H$ such that $f^{-1}(\{h\})=a$.

It's possible that there exists an $h\in H$ such that $f^{-1}(\{h\})=\{a\}$ (not $=a$), but you can't know that for sure, since we haven't assumed that $f$ is injective.

Keep in mind that the statement that you're trying to prove is $H\subseteq f(f^{-1}(H))$. This suggests that you should be looking for true statements that involve $f^{-1}(H)$.

 

[Potatochip911]

It's possible that there exists an $h\in H$ such that $f^{-1}(\{h\})=\{a\}$ (not $=a$), but you can't know that for sure, since we haven't assumed that $f$ is injective.

Keep in mind that the statement that you're trying to prove is $H\subseteq f(f^{-1}(H))$. This suggests that you should be looking for true statements that involve $f^{-1}(H)$.

Is it possible to assume that there's "$a\in A$ such that $\{a\}=f^{-1}(\{H\})$?" I feel like that's not possible since if the function is surjective then every single element in B could have more than one element in A mapping to it. I'm guessing I have to use the fact then that $f^{-1}(\{H\}):=\{x\in A:f(x)\in H\}$ so by the definition of the inverse image $f^{-1}(\{H\})\in A$. Now if there exists an element $x\in f^{-1}(\{H\})$ then from the definition of $f^{-1}(\{H\}\Rightarrow f(x)\in f(f^{-1}(\{H\})$ and we also have that $f(x)\in H$ from the definition. So we get the result that $f(x)\in H\in f(f^{-1}(\{H\})$.

 

[Fredrik]

Is it possible to assume that there's "$a\in A$ such that $\{a\}=f^{-1}(\{H\})$?" I feel like that's not possible since if the function is surjective then every single element in B could have more than one element in A mapping to it.

H is a subset of B, but $\{H\}$ isn't, so the notation $f^{-1}(\{H\})$ is undefined.

If you meant to write $f^{-1}(H)$, there's no reason to think that such an $a$ exists. Such an $a$ would exist e.g. if we had assumed that f is injective and that H is a singleton set (i.e. a set with only one element).

If you meant to write $f^{-1}(h)$, where h is some element of H, then there's still no reason to think that such an $a$ exists. Such an $a$ would exist e.g. if we had assumed that f is injective.

I'm guessing I have to use the fact then that $f^{-1}(\{H\}):=\{x\in A:f(x)\in H\}$

You will have to use that $f^{-1}(H)$ is equal to that right-hand side.

You will also have to use the definition of $f(E)$ for an arbitrary $E\subseteq A$.

so by the definition of the inverse image $f^{-1}(\{H\})\in A$.

The term is "preimage", and (regardless of whether you meant H or h) it's $\subseteq$, not $\in$.

Now if there exists an element $x\in f^{-1}(\{H\})$ then from the definition of $f^{-1}(\{H\}\Rightarrow f(x)\in f(f^{-1}(\{H\})$ and we also have that $f(x)\in H$ from the definition. So we get the result that $f(x)\in H\in f(f^{-1}(\{H\})$.

If you meant that $x\in f^{-1}(H)$ implies that $f(x)\in f(f^{-1}(H))$, then you're right.

 

[Potatochip911]

You will have to use that $f^{-1}(H)$ is equal to that right-hand side.

You will also have to use the definition of $f(E)$ for an arbitrary $E\subseteq A$.The term is "preimage", and (regardless of whether you meant H or h) it's $\subseteq$, not $\in$.If you meant that $x\in f^{-1}(H)$ implies that $f(x)\in f(f^{-1}(H))$, then you're right.

I'm quite lost as to what to do with the sets but I think I've found a way to prove it. Let $y\in H$, since $f:A\to B$ is surjective $\exists a\in A$ such that $f(a)=y$ therefore, $a\in f^{-1}(H)$ where $f^{-1}(H):=\{a\in A:f(a)\in H\}$. From this we get that $f(a)\in f(f^{-1}(H))$ and we know that $f(a)=y$ and that $y\in H$ so $H\subseteq f(f^{-1}(H))$