Proving that f(A ∩ B) = f(A) ∩ f(B) - Science, Math and Philosophy Forum

Two Plus Two Forums Other Topics Science, Math, and Philosophy

Proving that f(A ∩ B) = f(A) ∩ f(B)

Post Reply Subscribe

...

10-27-2011 , 01:51 PM

Borg7

old hand

Join Date: Mar 2009 Posts: 1,333

If f : X → Y is injective and A and B are both subsets of X, then f(A ∩ B) = f(A) ∩ f(B).

Does anybody know how I can prove the above? I've been searching for the solution for hours now, but I can't come up with it.

Quote

10-27-2011 , 01:59 PM

mSed84

journeyman

Join Date: Jan 2010 Posts: 251

Quote:

Originally Posted by Borg7

Let y be in f(AB). Then, there exists x in X such that x is in AB and f(x)=y. Since x is in AB it is in both A and B. So, f(x)=y is in f(A) and f(x)=y is in f(B). Thus, y is in f(A)f(B) by definition.

Conversely, suppose y is in f(A)f(B). Then, y is in f(A) and y is in f(B). So there exists, w in A, z in B such that f(w)=y and f(z)=y. But, f is injective so it is the case that w=z. Therefore, w is in A and w is in B, so w is in AB. Thus, f(w)=y is in f(AB).

This completes the proof.

Quote

10-27-2011 , 02:01 PM

uke_master

Carpal \'Tunnel

Join Date: May 2008 Posts: 15,913

There are two sides to proving set equalities. First let y be in f(A int B). As f is invective, this means there exists a unique x in X s.t. F(x) = y and x is in A int B. So x is in A and x is in B. therefore f(x) is in f(A) and in f(B) respectively. So it is in the intersection f(A) int f(B).

I will leave the other side which starts with a y in f(A) int f(B) and shows it is in f(A int B) for you to do because I can't do all your homework for you

Quote

10-27-2011 , 02:04 PM

mSed84

journeyman

Join Date: Jan 2010 Posts: 251

Quote:

Originally Posted by uke_master

You don't need to use the fact that f is injective for that half of the proof, though what you said is correct.

Quote

10-27-2011 , 03:26 PM

uke_master

Carpal \'Tunnel

Join Date: May 2008 Posts: 15,913

true.

Quote

10-27-2011 , 03:27 PM

Borg7

old hand

Join Date: Mar 2009 Posts: 1,333

Quote:

Originally Posted by mSed84

Let y be in f(AB). Then, there exists x in X such that x is in AB and f(x)=y. Since x is in AB it is in both A and B. So, f(x)=y is in f(A) and f(x)=y is in f(B). Thus, y is in f(A)f(B) by definition.

Conversely, suppose y is in f(A)f(B). Then, y is in f(A) and y is in f(B). So there exists, w in A, z in B such that f(w)=y and f(z)=y. But, f is injective so it is the case that w=z. Therefore, w is in A and w is in B, so w is in AB. Thus, f(w)=y is in f(AB).

This completes the proof.

Thanks a ton!

Can you please elaborate on the highlighted part?

-Borg7

Quote

10-27-2011 , 03:32 PM

uke_master

Carpal \'Tunnel

Join Date: May 2008 Posts: 15,913

An element y in f(A) has some element in A, call it w, such that f(w) = y. As in, elements in f(A) come from things from A (and possibly other things if not injective). so for anything in f(A) you can find a corresponding element in A that it came from, that is our w. likewise for B.

Quote

10-27-2011 , 08:28 PM

Alex Wice

aka Double Ice

Join Date: Jun 2007 Posts: 5,951

For x in X, suppose x is in A ∩ B. Then f(x) is in f(A) and f(B), so it is in f(A) ∩ f(B). Suppose x isnt in A ∩ B. Then x is either not in A or not in B. Wlog suppose A; then f(x) is not in f(A) [by injectiveness of f], so it isnt in f(A) ∩ f(B).

Quote

10-27-2011 , 09:13 PM

muttiah

Carpal \'Tunnel

Join Date: Aug 2004 Posts: 25,021

obviously true if you know intuitively what injective means.

Quote

10-28-2011 , 12:39 AM

#10

Alex Wice

aka Double Ice

Join Date: Jun 2007 Posts: 5,951

Quote:

Originally Posted by Isura

obviously true if you know intuitively what injective means.

Ya, another way to state the problem is, its true iff its true for bijections. Which makes it suuuuuper obvious

Quote

Post Reply Subscribe

...