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!

Proving a subset relation

  1. Apr 18, 2015 #1
    1. The problem statement, all variables and given/known data
    for functions f: X -> Y and g: Y ->Z
    show that for all subsets C in Z , (g°f)^-1(C) ⊆ f^-1(g^-1(C)) (or find a counterexample)

    3. The attempt at a solution
    let z ∈ (g°f)^-1(C) such that (g°f)^-1(z) = x for some x∈X
    then
    z = (g°f)(x)
    z = g(f(x))
    g^-1(z) = f(x)
    f^-1(g^-1(z) = x for some x ∈ X
    so z ∈f^-1(g^-1(C))

    These types of proofs are very subtle and technical to me and I am not sure If I am assuming anything or if I have sufficiently proven what needed to be proven. I would greatly appreciate some feedback :)
     
    Last edited: Apr 18, 2015
  2. jcsd
  3. Apr 18, 2015 #2
    I'm not sure I follow your first line. I didn't think it was necessary to use two variables (x & z) but if you want to I think it should be
    x ∈ (g°f)-1(C) such that (g°f)-1(z) = x for some x ∈ X & z ∈ C
     
  4. Apr 18, 2015 #3
    I am not sure how to do it with one variable. =\ I am a little confused... should I change the last line to
    x∈f^-1(g^-1(C)) ???
     
  5. Apr 18, 2015 #4

    Mark44

    Staff: Mentor

    I don't think the statement is true. What if ##g \circ f## is invertible (which would mean that ##(g \circ f)^{-1}## exists), but f or g is not invertible?
     
  6. Apr 19, 2015 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I'm pretty sure this is dealing with preimages (inverse images), not the images of inverse functions.
     
  7. Apr 19, 2015 #6
    I think I am lost lol
     
  8. Apr 19, 2015 #7

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    ##g^{-1}(C)## exists even when ##g^{-1}## doesn't. It's defined by ##g^{-1}(C)=\{y\in Y|g(y)\in C\}##.
     
  9. Apr 19, 2015 #8

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This sentence doesn't make sense. I assume you meant "...be such that...". You should just start "let ##z\in(g\circ f)^{-1}(C)##". No need to add a "such that". Note that the z defined this way is an element of X, not Z, so the expression ##(g\circ f)^{-1}(z)## doesn't make sense.

    You just need to use the definition of the preimage of a set correctly. Here's the definition: If ##f:X\to Y## and ##S\subseteq Y##, then ##f^{-1}(S)=\{x\in X|f(x)\in S\}##. Note that this means that the following equivalence holds for all ##x\in X##.
    $$x\in f^{-1}(S)~\Leftrightarrow~ f(x)\in S.$$ I like to do these proofs as a sequence of implications. I would start by saying that the following implications hold for all ##x\in X##.
    $$x\in(g\circ f)^{-1}(C)~\Rightarrow~(g\circ f)(x)\in C~\Rightarrow~g(f(x))\in C~\Rightarrow~\dots$$ If you find that the sequence of implications ends with ##x\in f^{-1}(g^{-1}(C))##, you will have proved that ##(g\circ f)^{-1}(C)\subseteq f^{-1}(g^{-1}(C))##.

    Use \circ to produce the ##\circ## symbol.
     
  10. Apr 19, 2015 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Right, but in his proof he seemed to use invertibility when he wrote ##(g\circ f)^{-1}(z)##.
     
  11. Apr 19, 2015 #10

    Mark44

    Staff: Mentor

    What I had in mind were a pair of functions f (f:X→Y) and g (g:Y → Z) where f was invertible and g wasn't, but ##g \circ f## was invertible.
     
  12. Apr 19, 2015 #11
    ok let me try again

    if x ∈ (g ο f)-1(C)
    then (g ο f)(x) ∈ C
    so g(f(x)) ∈ C
    and f(x) ∈ g-1(C)
    so x∈ f-1(g-1(C))

    if i understand what Mark44 is saying, then this proof will not work if g is not invertible (you cant get from the third to the fourth line) or if f is not invertible (you cant get from the fourth to the fifth line) . It seems that the way the problem is worded, the fact that (g ο f) is invertible is assumed?
     
  13. Apr 19, 2015 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Actually, the proof you just gave is perfect and works without assuming invertible.
     
  14. Apr 19, 2015 #13
    is that because of the second variable before?
     
  15. Apr 19, 2015 #14

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You seem to be asking if the new proof is perfect because the previous attempt involved a second variable. You probably meant to ask something else. But I agree that your proof is good. Since you didn't make any assumptions about x other than ##x\in(g\circ f)^{-1}(C)##, what you did proves that ##(f\circ g)^{-1}(C)\subseteq f^{-1}(g^{-1}(C))##. The proof of ##f^{-1}(g^{-1}(C))\subseteq (g\circ f)^{-1}(C)## is similar.
     
  16. Apr 19, 2015 #15
    edit: actually never mind. I didn't mean that it was wrong to use a second variable, just that I didn't bother.
     
  17. Apr 19, 2015 #16
    I think what I meant is... did the problem with invertibility arise because of the second variable?

    Btw thank you all for your time and help
     
  18. Apr 19, 2015 #17
    I had the same proof that you got in post #11 & I don't think the invertibility had anything to do with the second variable, I think it just made it a bit more complicated than necessary.
     
  19. Apr 19, 2015 #18

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The problem was that you wrote ##(f\circ g)^{-1}(z)##. The way you used it, is that it is one single element. But it's not, unless the function is invertible. In general, it is a set of elements, not just one.
     
  20. Apr 19, 2015 #19
    ahh ok I get it now. Thank you all.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving a subset relation
  1. Prove a subset (Replies: 15)

  2. Relations and Subsets (Replies: 1)

  3. Proving a subset (Replies: 4)

Loading...