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: Subsets and functions math help

  1. Jan 24, 2006 #1
    Suppose f:A--->B and S and T are subsets of A. Prove or give a counter example.

    (a) if S[tex]\subseteq[/tex]T, then f(S)[tex]\subseteq[/tex]f(T)
    (b) if f(S)[tex]\subseteq[/tex]f(T), then S[tex]\subseteq[/tex]T

    I know for a fact that (a) is true. The reason I say this is because if S[tex]\subseteq[/tex]T ... then for example: Let S be the set of all Real numbers and let T be the set {-3 -2 -1 0 1 2 3} and let f be the funtion defined by f(x)=x-1. If you apply all the elements in S and T to this function, then f(S)[tex]\subseteq[/tex]f(T). I don't think their is a counterexample out their.

    I could use the same reasoning to argue that (b) is true as well.

    So ive spent an hour on this and i thought perhaps i could use the contrapositve to proove this.

    Does this statements exist?

    "if f(S) is NOT contained in f(T), then S is NOT contained in T"

    I mean, NOT contained can have different meanings.

    For example: S = {1 2 3 4} and T = {2 3 4 5 6}. Here, S is NOT contained in T, but it does have an intersetion.

    Or S = {1 2 3} and T = {4 5 6} are disjoint.

    So is their such thing as NOT contained in?
    Last edited by a moderator: Jan 24, 2006
  2. jcsd
  3. Jan 25, 2006 #2


    User Avatar
    Homework Helper

    For a, You can think this way:
    If an element x0 is in S, is it also in T?
    So if f(x0) is in f(S), is it also in f(T)?
    From there, is a true? And can you prove that a is true?
    For b, What if you have a function:
    f: R ---> R+
    [itex]{ } \quad x \mapsto x ^ 2[/itex], and S := ]0, 1[, T := ]-0.5, 0[ ??
    Can you go from here?
  4. Jan 25, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You are allowed to make counter examples as trivial as you want. What's the easiest way to deal with functions? Think of finite sets. What are the easiest things to deal with for b)? How about a really small A with two distinct subsets S and T (from 'a' we know anything in SnT must be sent to f(T) so we may as well assume that not only are we looking for S not contained in T but S in fact disjoint from T). Further we won't care about bits of S mapped outside f(T), so we may as well assume that f maps S into f(T).

    So let A be the set {0,1} S={0) T={1}, now can you find a really trivial function to a set even smaller than A? (I am using trivial not as a derisory comment on you but in its mathematical context.)
  5. Jan 25, 2006 #4
    Suppose f:A--->B and S and T are subsets of A. Prove or give a counter example.

    (b) if f(S)[tex]\subseteq[/tex]f(T), then S[tex]\subseteq[/tex]T

    Let A = {0,1} S={0} T={1}
    Let f:R---->R defined by f(x) = 3

    Thus, f(S)=3 and f(T)=3 and therefore; f(S)[tex]\subseteq[/tex]f(T), which shows that S[tex]\subseteq[/tex]T does not have to occur.

    Is this a legit counterexample? It seems that i did it backwards (something i would not usually do.) since i started by assuming S and T are disjoint and shoing that f(S)[tex]\subseteq[/tex]f(T).

    i would think that you would start by assuming f(S)[tex]\subseteq[/tex]f(T) and showing that S does not have to contain T
  6. Jan 25, 2006 #5


    User Avatar
    Science Advisor

    That's right except f(S) = {3} not 3. (the image of a set is a set) Also f should be A-->R (or else let A = R) because of what you're trying to prove.
  7. Jan 25, 2006 #6
    Thanks for checking!

    You see, im having a lot of difficulties starting proofs that have [tex]\subseteq[/tex] symbols in them. Perhaps someone can help explain to me how to start off/begin writing proofs for them.

    For example: With a question like this:

    Suppose that f:A---->B and suppose that C[tex]\subseteq[/tex]A and D[tex]\subseteq[/tex]B

    (a) Prove or give a counterexample: f(C)[tex]\subseteq[/tex]D iff C[tex]\subseteq[/tex]f^-1(D).
    (b) What condition on f will ensure that f(C)[tex]\subseteq[/tex]D iff C[tex]\subseteq[/tex]f^-1(D)? Prove your answer.

    My problem here is how do i know if i should prove or look for a counterexample? I mean, i spent hours on (a) and eventually drew out a diagram for it, i still don't know if their is a counterexample (well, by looking at what (b) is asking, im sure i need a counterexample - but thats not helping me unfortunatly.)

    I mean, its not only the [tex]\subseteq[/tex] symbolls that are getting me, its also that functions are involved - i read the text book over and over and did the practise examples, so i know that i understand everything, its just getting a start. I came accros many different ways to start proofs... but does anybody know any easy way (or rule) on starting a proof like this?

    For the above, I know you have to start by proving f(C)[tex]\subseteq[/tex]D [tex]\subseteq[/tex] C[tex]\subseteq[/tex]f^-1(D) ... and then do the opposit.

    So i would start by saying let y[tex]\in[/tex]f(C)[tex]\subseteq[/tex]D ... then there exists a point x in f(C)[tex]\subseteq[/tex]D such that f(x) =y ... etc...??
    Last edited by a moderator: Jan 25, 2006
  8. Jan 26, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Experience is what you need. Think about your favourite functions if you must, like sin, it takes all multiples of pi to 0, so functions can be many to one, that is allowed. That is all I used for the counter example. I just gave a simple counter example by construction. And no I didn't work backwards, I just used the simple notion that the range set of a function does not in depend upon the domain at all. If I tell you that two function lands in the set {0,1} then you cannot tell me what the domains are, whether they are even the same set or completely different.

    As it happens, I think a) is true.

    What is f^{-1}(D)? It is the set of all points that map to D, if C is in that set then f(C) is contained in D. Conversely if C is mapped into D, it lies in the inverse image of D (the set of all points mapped into D).
  9. Jan 26, 2006 #8


    User Avatar
    Science Advisor

    Well, by the way the question is asked a) is probably not true, because in part b) they ask what additional condition you can impose to make it true. Maybe they mean you can't assume f is invertible, so a counterexample would be a non-invertible function and the condition for part b) would be that the function must be invertible.

    I think that the best way to think about these things is with the domain-codomain diagrams and just thinking of all the possible ways the function could be set up. To prove it you don't say y is an element of "f(C) is a subset of D"... you say y is an element of f(C). And that means there's an x in C, not f(C), such that f(x) = y. Anyway, I think that's the wrong way to approach it: instead, suppose x is an element of C, so f(x) = y is an element of D, and show that x is an element of f^(-1)(D) according to how Matt Grime did it.
    Last edited: Jan 26, 2006
  10. Jan 26, 2006 #9
    Okay, i tried to disprove this by doing specific fuctions which are injective, surjective, bijective, or neither ... unfortunatly, i failed to find a counter example, so i set out to prove it. (Matt Grimm was right)

    f(C)[tex]\subseteq[/tex]D iff C[tex]\subseteq[/tex]f^-1(D).

    You want to show it both ways:

    1) If f(C)[tex]\subseteq[/tex]D then C[tex]\subseteq[/tex]f^-1(D).

    Thank you Orthodontist and Matt Grimm for your help. I tried what you said, but it was difficult because im trying to show "If f(C)[tex]\subseteq[/tex]D then C[tex]\subseteq[/tex]f^-1(D)." This means that i have to start off with f(C)[tex]\subseteq[/tex]D and show that it arrives to C[tex]\subseteq[/tex]f^-1(D).

    Suppose that y[tex]\in[/tex]f(C). Then f^-1(y)=x[tex]\in[/tex]c. Also, f(C)y[tex]\in[/tex]D and thus, y[tex]\in[/tex]D which implies that f^-1(y)y[tex]\in[/tex]f^-(D). But f^-1(y)=x and therefor, x[tex]\in[/tex]f-1(D). Since x[tex]\in[/tex]C this means that C[tex]\in[/tex]f^-1(D)

    Boy that looks messy :grumpy: :frown:

    2) If C[tex]\subseteq[/tex]f^-1(D) then f(C)[tex]\subseteq[/tex]D

    Suppose that x[tex]\in[/tex]C, then x[tex]\in[/tex]f^-1(D). Therefore, f(x)=y[tex]\in[/tex]D. Therefore, y[tex]\in[/tex]D and thus... f^-1(y)[tex]\in[/tex]f^-1(D). But, f^-1(y)=x ... thefroe, x[tex]\in[/tex]f^-1(D). But, x[tex]\in[/tex]C and so, f(C) lies in D.

    this second part looks like i went in a circle.. so thats not much of proof :(
    Last edited by a moderator: Jan 26, 2006
  11. Jan 26, 2006 #10


    User Avatar
    Science Advisor

    If the function is f: {1, 2, 3} --> {1, 2, 3} defined as {(1, 1), (2, 1) (3, 2)}, then f^(-1) does not exist so the equivalence of a) cannot be true without an added condition.

    But assuming that f is invertible, your first proof does not make any sense.

    I'll rewrite what I think you mean:

    "Suppose that y[tex]\in[/tex]f(C). Then f^-1(y)[tex]\in[/tex]C. Also, y[tex]\in[/tex]D which implies that f^-1(y)[tex]\in[/tex]f^-1(D). Since f^-1(y)[tex]\in[/tex]C this means that C[tex]\subseteq[/tex]f^-1(D)"

    The conclusion doesn't follow. What you've shown is there is an element of C that is also an element of f^-1(D). Specifically, this element is f^-1(y) for some y in f(C). What you need to show is that if _anything_ is an element of C, then it _must_ be an element of f^-1(D). Start by saying "Suppose that x[tex]\in[/tex]C."

    The notation on your second proof is better:

    Yes, that is circular. You started by supposing x[tex]\in[/tex]C, proved by supposition that x[tex]\in[/tex]f^-1(D), and then did some convolutions to prove it again. What you need to prove in this case is that if anything is an element of f(C), then it is an element of D.
  12. Jan 26, 2006 #11
    Notice that my part (b) above changed from )[tex]\subseteq[/tex] to = signs. I didn't notice that untill now. I guess i have to pay very close attention when doing these problems... i feel so....dumb

    Check it both ways:

    1) If f(C)[tex]\subseteq[/tex]D, then C[tex]\subseteq[/tex]f^-1(D)

    Suppose x[tex]\in[/tex]C. then f(x)[tex]\in[/tex]f(C). Since f(x)=y, then y[tex]\in[/tex]f(C). Since f(c)[tex]\subseteq[/tex]D, y[tex]\in[/tex]D. Thus, f^-1(y)[tex]\in[/tex]f^-1(D). But f^-1(y)=x. Therefore, x[tex]\in[/tex]f^-1(D). But, x[tex]\in[/tex]C. Therefore, C[tex]\subseteq[/tex]f^-1(D).

    2) If C[tex]\subseteq[/tex]f^-1(D), then f(C)[tex]\subseteq[/tex]D

    Suppose that y[tex]\in[/tex]f(C). Then f^-1(y)[tex]\in[/tex]C. But f^-1(y)=x. Therefor, x[tex]\in[/tex]C. But C[tex]\subseteq[/tex]f^-1(D). Therefore, x[tex]\in[/tex]f^-1(D). this means that f(x)[tex]\in[/tex]D. But f(x)=y... and therefore y[tex]\in[/tex]D. But y[tex]\in[/tex]f(C). this implies that f(C)[tex]\subseteq[/tex]D
    Last edited by a moderator: Jan 26, 2006
  13. Jan 27, 2006 #12


    User Avatar
    Science Advisor

    Those look right.

    I don't see how the change in part b) alters anything. If f is invertible, it should satisfy those properties with no additional condition.
    Last edited: Jan 27, 2006
  14. Jan 27, 2006 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It is perfectly possible to use f^{-1} without f being invertible, as this question does. It is defined on subsets of the image. f^{-1}(D) is the set of elements mapped to D.

    Now, playboy, this means that when you write y=f(x) this does not allow you to use f^{-1}(y)=x since that is not true, f^{-1}(y) is the set of points mapped to y, of which x is *just one*.

    I already gave you the proof, of a). It was two lines:

    What is f^{-1}(D)? It is the set of all points that map to D, if C is in that set then f(C) is contained in D. Conversely if C is mapped into D, it lies in the inverse image of D (the set of all points mapped into D).

    You do not have to use long proofs, proofs with lots of notation, a mere simple explanation wil do.
    Last edited: Jan 27, 2006
  15. Jan 27, 2006 #14
    Matt Grime, when they say "Prove," it seems that an explanation is just not what they mean... it seems like you need to do it algebraically. The examples in the textbook use x's and functions etc... in their proof's. Not that im aruging with you, i allways thought algebra has to be involved.

    Like this question in the book: Let f:A--->B and suppose that there exists a function g:B---->A such that (g of f) =Ia and (f of g)=Ib
    Prove that f is bijective.
    Prove that g=f^-1

    Like this proof, you would simply state that it is indeed byjective since the function f has an inverse (and that is by definition.)

    and g=f^-1 since (g of f) and (f of g) gives the identity. (and that too is by defintion.)

    No algebra was used in the above, just definitions.

    Oh and you know how you explained how if f(x)=y, you cannot say that f^-1(y)=x. I suppose f^-1(y)=y would work... that makes more sense to me.
    Last edited by a moderator: Jan 27, 2006
  16. Jan 27, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    erm, definitely not. a proof is a series of logical arguments that, well, prove something. there is no need to use symbols alone if that is unnecessary and confusing. picking the correct way to describe something is half the difficulty in maths.

    no, not at all, as long as your argument is cogent. that is where symbols have an advantage, it is harder to miscommunicate in symbols, but it is harder to understand when written. besides, you're asking how you're supposed to think of these things. and how i think of f^{-1}(D) is as the set of elements mapped to D, not {x in A: f(x)=y for some y in D}. there is a definite over emphasis on manipulation of strings of symbols in too many maths courses, when there are better ways to think of these things to aid understanding.

    i think it would depend upon your precise definitions of inverse since there are two equivalent ways of doing it (at least).

    well, that makes no sense to me, at all. since it implies f(y)=y, where did you get that from? the f^{-1} thing in the question acts on *subsets* not elements, it gives the preimage of a subset, possibly a subset with only one element but subset nonetheless.
  17. Jan 27, 2006 #16


    User Avatar
    Science Advisor

    Oh, I see. I didn't know.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook