Let S and T be sets Define a function f PS Times PT rightarr

Let S and T be sets. Define a function f: P(S) Times P(T) rightarrow P (S T) by f (A, B) = A B for all A S and all B T. Show that f is a surjection. Show f is an injection iff S and T are disjoint.

Solution

f(A,B) = AUB where A is a subset of S and B a subset of T

a) To prove that f is a surjection we must show that for any set C, we have an A and B such that C = AUB

Since codomain is P(SUT) , any set in P(SUT) will be of the form AUB with one set from S and another from T.

If any set C is in SUT, C is of the form AUB and hence has a preimage thus onto

------------------------------------

b) If S and T are not disjoint then consider two sets A and B, with common elements

A-BU B = AUB

and also AUB = AUB

Thus we see that it cannot be one to one if there are common elements between A and B

Hence only iff S and T are disjoint f will be one to one.