• Support PF! Buy your school textbooks, materials and every day products Here!

Set Theory| Proof if A subset B then f(A) subset f(B)

  • Thread starter Berrius
  • Start date
  • #1
19
0

Homework Statement


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)

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!
 

Answers and Replies

  • #2
106
0
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.
 
  • #3
19
0
(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?
 
  • #4
106
0
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:
  • #5
19
0
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)

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)
 
  • #6
106
0
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.
 

Related Threads for: Set Theory| Proof if A subset B then f(A) subset f(B)

Top