Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Function on sets and subsets

  1. Oct 26, 2008 #1
    Alright, 2+1/2 problems here:

    First:

    36. Let F be a function from the set A to the set B. Let S and T be subsets of A. Show that:

    a) f(S[tex]\cup[/tex]T)=f(S)[tex]\cup[/tex]f(T)
    b)f(S[tex]\cap[/tex]T)[tex]\subseteq[/tex] f(S)[tex]\cap[/tex]f(T)

    Note: This must be done using a membership proof. i.e. prove that f(S[tex]\cup[/tex]T)[tex]\subseteq[/tex]f(S)[tex]\cup[/tex]f(T) AND f(S)[tex]\cup[/tex]f(T)[tex]\subseteq[/tex]f(S[tex]\cup[/tex]T)


    40. Let f be a function from A to B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre images of all elements of S. We denote the inverse image of S by f[tex]^{-1}[/tex](S) so f[tex]^{-1}[/tex](S)={a[tex]\in[/tex]A| f(a)[tex]\in[/tex]S}

    Prove parts a and b of 36 substituting the inverse image for f, and an equality in both parts (rather than subset)

    1) (not a question from the text). This was not covered in the lecture or in the book, but how do most people go about proving that a function is surjective from the definition?


    2. Relevant equations
    f[tex]^{-1}[/tex](S)={a[tex]\in[/tex]A| f(a)[tex]\in[/tex]S}
    f(S)={f(s)|s[tex]\in[/tex]S}


    3. The attempt at a solution
    Alright, I only have an idea of how to do 36, 40 I am lost. The professor said to use proof by case for 36, so here is how I thought it would go:

    a) prove:f(S[tex]\cup[/tex]T)=f(S)[tex]\cup[/tex]f(T)

    Proof:

    1) assume x[tex]\in[/tex] f(SUT), then, by definition x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]SUT}

    2) If x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]SUT}, then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S or T} by definition of union.

    3) If x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}, then x[tex]\in[/tex]f(S), and since f(S)[tex]\subseteq[/tex]f(S)Uf(T), thus if x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S} then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}[tex]\cup[/tex]{f(s)|s[tex]\in[/tex]T}.

    4)If x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]T}, then x[tex]\in[/tex]f(T), and since f(T)[tex]\subseteq[/tex]f(S)Uf(T), thus if x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]T} then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}[tex]\cup[/tex]{f(s)|s[tex]\in[/tex]T}.

    4)Therefore if x[tex]\in[/tex]f(SUT) then x[tex]\in[/tex]f(S)Uf(T)

    5 Now we must prove that f(S)[tex]\cup[/tex]f(T)[tex]\subseteq[/tex]f(S[tex]\cup[/tex]T, to do this, just invert the steps of this proof (obviously I wouldn't put this on a test but to cut length, this is reasonable)

    b)f(S[tex]\cap[/tex]T)[tex]\subseteq[/tex] f(S)[tex]\cap[/tex]f(T)

    proof:

    1) assume x[tex]\in[/tex] f(S[tex]\cap[/tex]T), then, by definition x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S[tex]\cap[/tex]T}

    2) Then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S and T}.

    3) Thus s[tex]\in[/tex]S and s[tex]\in[/tex]T and so, through simplification, we can say:

    4) s[tex]\in[/tex]S, if s[tex]\in[/tex]S then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}

    5) We can also say s[tex]\in[/tex]T, and if s[tex]\in[/tex]T then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]T}.

    6) Therefore, if s[tex]\in[/tex]S and s[tex]\in[/tex]T, which are true, we have x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S} and x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]T} (we can say through addition).

    7) Note that by the definition of intersection, x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}[tex]\cap[/tex]{f(s)|s[tex]\in[/tex]T}.

    8) Therefore, if x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S[tex]\cap[/tex]T} then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}[tex]\cap[/tex]{f(s)|s[tex]\in[/tex]T}.

    9)if x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S[tex]\cap[/tex]T} then x[tex]\in[/tex]{f(s)|s[tex]\in[/tex]S}[tex]\cap[/tex]{f(s)|s[tex]\in[/tex]T}.


    10)This means f(S[tex]\cap[/tex]T)[tex]\subseteq[/tex]f(S)[tex]\cap[/tex]f(T).

    For Problem 40, I am wondering whether the proofs follow the same steps, or is there something else I have to worry about?
     
    Last edited: Oct 27, 2008
  2. jcsd
  3. Oct 27, 2008 #2
    Re: Sets

    To make this easier, forget problem 36, and 40, I can go in for help for that. Now my main question is on proving surjectivity: How is this done. I understand, you must pick a random member y0 of the codomain and prove that there is some value x0 from the domain such that f(x0)=y0, in practice however, this gives me trouble. For example, f(x)=x^2 isn't surjective on R-->R, however, it is surjective on R-->R+, how would one guarantee that the y0 value picked from the codomain reflects the restrictions put on it?
     
  4. Oct 27, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Re: Sets

    By saying so? If you want to prove that f(x)= x2:R-->R+ is surjective, you would start by saying "Let y be in R+." Then you are looking for x in R such that x2= y. Since y is in R+, x= y1/2 exists.
     
  5. Oct 27, 2008 #4
    Re: Sets

    Aha, thank you, why it couldn't be explained as clearly as that in my text is beyond me.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook