# Collections of sets study problems

### Problem 1

Let $$f : X \rightarrow Y$$ be any function, and let A and B be subsets of X. For any subset S of X define its image f(S) by $$f(S) = \{ f(s) \in Y \ | \ s \in S \}$$.

(a) Prove that $$f(A \cap B) \subseteq f(A)\cap f(B)$$.

(b) Prove that it's not necessarily the case that $$f(A)\cap f(B) \subseteq f(A \cap B)$$ by giving specific finite sets and a specific function for which this inclusion does not hold.

Stuck? Here are some hints.

Here is the solution to (a) and the solution to (b).

### Problem 2

Graph G with set of nodes V is shown below. Recall that the distance d(x,y) between nodes x and y is the number of edges on the shortest path from x to y.

Now let's define:

$$\begin{eqnarray*} M &=& \{1,2,3\} \\ f(k) &=& \{n \in V\ :\ d(n,X) = k\} \\ P &=& \{f(k) \mid k \in M \} \end{eqnarray*}$$

(a) Fill in the following values:

f(1) =

f(3) =

(b) Is P a partition of V? For each of the three conditions required to be a partition, explain why P does or doesn't satisfy that condition.

Stuck? Here are some hints.

Here are the solutions.

### Problem 3

Recall that the symmetric difference of two sets A and B written $$A \oplus B$$ contains all the elements that are in one of the two sets but not the other. That is $$A \oplus B = (A - B) \cup (B - A)$$. Let $$S = \mathbb{P}(\mathbb{Z})$$. Define a relation $$\sim$$ on S by:
$$X \sim Y$$ if and only if $$X \oplus Y$$ is finite.

(a) First, figure out what the relation does:

• What is in $$[\emptyset]$$?
• What's in $$[\mathbb{Z}]$$?
• Name one specific infinite subset of the integers that is not in $$[\mathbb{Z}]$$.

(b) Warm-up problem for part (c): prove that $$(A - C) \subseteq (A-B) \cup (B - C)$$ for all sets A, B, and C.

(c) Prove that $$\sim$$ is an equivalence relation.