Collections of Sets, Problem 1

Basic hints

Note that the input and output of the function f are sets. So f(A) and f(B) are sets and therefore \(f(A \cap B)\) and \(f(A)\cap f(B)\) are sets.

Do you understand why the claim in (a) is true (or even plausible)? If not, build yourself a small concrete model for thinking about the claim.

• Sets X and Y containing some simple concrete values
• Sets A and B, overlapping subsets of X.
• A function f, e.g. draw a bubble diagram with arrows showing where f maps each input value.
• Calculate what the sets f(A) and f(B) contain. Similarly for the set \(f(A)\cap f(B)\).

Don't try to do the proof in (a) before you understand what's going on.

It's ok to do part (b) first, if you find (b) easier to think about.

Hints for the proof in part (a)

Remember the standard method for proving a subset inclusion: choose an element from the smaller set and show that it is also a member of the larger set.

We've seen images before, when discussing onto functions. This is a slightly different packaging of the same idea. Remember how we used the fact that a function was onto: if you pick any output value p, there must be a corresponding input value that maps onto p. You'll want to do something similar here.

Hints for part (b)

The instructions say you must use finite sets. So A could contain 200 elements. But, more likely, you can make a counterexample that uses only a small handful of elements.