Building Blocks
for
Theoretical Computer Science

Margaret M. Fleck and the CS 173 course staff

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

This problem assumes that you've studied relations.

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: