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: Set Theory| Proof if A subset B then f(A) subset f(B)

  1. Sep 4, 2011 #1
    1. The problem statement, all variables and given/known data
    f: X -> Y is a map from X to Y. And A, B subset X are random subsets of X. Proof the following:
    a) if A subset B then f(A) subset f(B)

    3. The attempt at a solution
    (1)Take an arbitrary element x in f(A).
    (2)For every x there has to be a y in A so that f(y)=x
    (3)From A subset B: for every y in A, y in B
    (4)So for every x in f(A) there has to be a y in f(B)
    (5)So f(A) subset f(B)

    I'm terrible at this, I came up with this proof but I'm wondering if my reasoning from step 3 to 4 is correct. Can someone help me?
    Thanx in advance!
     
  2. jcsd
  3. Sep 4, 2011 #2
    Looks pretty good, except for what seems like a typo/misunderstanding in step 4. You have that there has to be a y in f(B), but y is in A and B, not f(B).

    Also, the quantifiers in your proof are a little confusing. For instance, you've already said that x is an arbitrary element in f(A) in step 1, but then in step 2 you say "For every x...". You don't need to do that; since x is arbitrary, if you prove something about x then you prove it about every x as a consequence.

    I think you have the right idea, try to think it through a little more. The way step 4 is currently written, it does not follow from step 3 nor does it imply step 5, and moreover it is false. Again, I think this is just a typo though.
     
  4. Sep 4, 2011 #3
    (1)Take an arbitrary element x in f(A).
    (2)For this x there has to be a y in A so that f(y)=x
    (3)From A subset B: for every y in A, y in B: so (this) y in A and in B
    (4)So for x in f(A), x is also in f(B)
    (5)So f(A) subset f(B)

    Is this better? I'm still not sure if (4) follows from (3). If it is correct though, can you tell me how I can see that clearly?
     
  5. Sep 4, 2011 #4
    Yes that's better. To be more explicit, and maybe convince yourself further of the proof, you could insert a step or two between 3 and 4, such as

    (3.4) y is in B, so f(y) is in f(B)
    (3.6) Since f(y)=x, x is in f(B)

    Hence what we have shown in steps 1 to 3.6 is that if x is in f(A), x is in f(B).

    Any further modifications are really just style though.
     
    Last edited: Sep 4, 2011
  6. Sep 4, 2011 #5
    Another one to check if I'm getting it right now:

    f: X -> Y is a map from X to Y. And A, B subset X are random subsets of X. Proof the following:
    a) f(A union B) = f(A) union f(B)

    3. The attempt at a solution
    (1)Take an arbitrary element x in f(A union B).
    (2)For this x there has to be a y in (A union B) so that f(y)=x
    (3)y in (A union B) so y in A or y in B
    (4)y in A so f(y) in f(A) and since f(y)=x: x in f(A)
    (5)y in B so f(y) in f(B) and since f(y)=x: x in f(B)
    (6)So x in f(A) or in f(B)
    (7)So f(A union B) => f(A) union f(B)

    (8)Take an arbitrary element x in f(A) union f(B).
    (9)So x in f(A) or in f(B)
    (10)There has to be a y in A or in B so that f(y)=x
    (11)So y in (A union B)
    (12)So x in f(A union B)
    (13)So f(A) union f(B) => f(A union B)

    (14)So f(A union B) = f(A) union f(B)
     
  7. Sep 4, 2011 #6
    Looks good, just a few comments. The notation => normally means implies, which doesn't make sense in the context of sets. I assume that you mean subset, and that you have written proper notation for it.

    Also, in steps 4 and 5, you may want to more explicitly indicate that you are splitting into cases.

    Everything else looks good.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook