Expert: Paul Klarreich - 12/11/2008

Question
Let f: X is onto Y. Prove that f is a one-to-one function if and only if f(A)intersection f(B)= f(A intersection B) forall pairs of subsets X. I do not even know how to begin this one, so if you could explain it, I would greatly appreciate it.

Answer
Questioner:   Pete
Category:  Advanced Math
Private:  No
 
Subject:  Math Foundations Proofs
Question:  Let f: X is onto Y. Prove that f is a one-to-one function if and only if f(A)intersection f(B)= f(A intersection B) forall pairs of subsets X. I do not even know how to begin this one, so if you could explain it, I would greatly appreciate it.
.......................
Hi, Pete,

These are tricky, and the key is to focus on SINGLE elements.  (I mean one at a time, not un-married.)

NOTATION:  For sets A,B, to simplify my typing:

A + B is union.
AB is intersection.
A <= B is 'subset of'
x in A means 'x is an element of A'.
........................
Your 'theorem':

f is 1-1 iff  f(A) f(B) = f(AB) for all A,B <= X.

When you have to prove  P iff Q, you can do it in two ways:

One way:

Assume P, prove Q.
Assume Q, prove P.

Another way:

Assume P, prove Q.
Assume not P, prove not Q.

When you have to prove  set X = set Y, you do this:

Prove  X <= Y.
Prove  Y <= X.

and to do those:

if a in X, prove a in Y.
if a in Y, prove a in X.
(see? focusing on ONE element.)

.......................................

OK, let's do it.


Assume that f IS 1-1.  

Let A,B be any subsets.  

Claim:  f(AB) <= f(A) f(B)

1. If y in f(AB), then y = f(x), where x in AB.
2. If x in AB, then x in A and x in B.
3. If x in A and x in B, then f(x)=y in f(A) and f(x)=y in f(B)
4. If y in f(A) and y in f(B) then y in f(A) f(B).

Done:

Second claim:

f(A) f(B) <= f(AB)

1. If y in f(A) f(B) then y in f(A) and y in f(B).
2. If y in f(A), then y = f(x1), where x1 in A.
3. If y in f(B), then y = f(x2), where x2 in B.

>>>>>>>> Correction; y in f(B), in line 3.

4. But if f(x1) = y = f(x2), then x1 = x2, because f is 1-1.
===== SEE? THE 1-1 STUFF HAD TO COME IN HERE SOMEPLACE =====
  So y = f(x), where x in A and x in B.
5. So x in AB, and f(x) = y in f(AB)

Done.

So f(AB) <= f(A) f(B)  AND  f(A) f(B) <= f(AB)
Therefore f(AB) = f(A) f(B)
...........................
Now assume f is not 1-1.  Then we can find x1 /= x2 such that:

f(x1) = f(x2) = c

Let A = {x1}, B = {x2}.  Now

f(A) f(B) = {c}{c} = {c}
AB = { }, f(AB) = { } /= f(A) f(B)

Cute?