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!

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