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

hints

solution to (a)

solution to (b)

solution to (c)