# 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.