1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 3, 2015 #1
    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. jcsd
  3. Oct 3, 2015 #2

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    "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?
     
  4. Oct 3, 2015 #3
    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.
     
  5. Oct 3, 2015 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You don't need to use the fact that f is surjective for this part.
     
  6. Oct 4, 2015 #5
    Is ##f(y)\in H## going in the right direction or do I need to think of something else entirely?
     
  7. Oct 4, 2015 #6

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)##.
     
  8. Oct 4, 2015 #7
    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##?
     
  9. Oct 5, 2015 #8

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
  10. Oct 5, 2015 #9
    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))##
     
  11. Oct 5, 2015 #10

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  12. Oct 5, 2015 #11
    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.
     
  13. Oct 5, 2015 #12

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  14. Oct 6, 2015 #13
    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?
     
  15. Oct 6, 2015 #14

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    ##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\}##.
     
  16. Oct 6, 2015 #15
    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##
     
  17. Oct 7, 2015 #16

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
  18. Oct 10, 2015 #17
    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)##?
     
  19. Oct 10, 2015 #18

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
  20. Oct 10, 2015 #19
    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.
     
  21. Oct 10, 2015 #20

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted