CS 390 Solutions to Unit 2 Exercises

p. 32 - 39

1.1 (a) { i$(-1)^{i} \mid i$ is a natural number}
(e) Let use call this set S. S can be defined recursively as follows:
Basis Clause: $\{0\} \in S$.
Inductive Clause: For any set $X$, if $X \in S$, then $X \cup \{\mid X \mid\} \in S$.
Extremal Clause: Nothing is in $S$ unless it is obtained by a finite number of applications of the Basis and Inductive Clauses.

$S$ can also be defined as $\{ \cup_{i=0}^{k} \{i\} \mid k \in N \}$, where $N$ is the set of natural numbers.

1.4 (b) $A - (A \cap B)$ = $A \cap (A \cap B)'$
= $A \cap (A' \cup B')$ by De Morgan
= $(A \cap A') \cup (A \cap B')$ by distribution
= $(A \cap B')$ since $(A \cap A') = \emptyset$.
(e) $(A' \cap B')' = A'' \cup B''$ by De Morgan
= $A \cup B$ because $A'' = A$ and $B'' = B$.

1.7 (a) $(A \cup B) - (A\cap B)$

1.8 (f) D₁ = {x | x < 1 and x is a real number}.
D₂ = {x | x < 1/2 and x is a real number}.
Hence $D_{2} \subset D_{1}$.
D₃ = {x | x < 1/3 and x is a real number}.
Hence $D_{3} \subset D_{2}$. Hence $D_{3} \subset D_{1}$.
...
In general $D_{n} \subset D_{1}$ for any natural number $n$ that is greater than 0.
Hence $\cup_{n=1}^{\infty} D_{n} = D_{1}$.

1.53 (a) $2^{A \cup B}$ is the set of subsets of $A \cup B$. If neither A nor B is empty and if they are not equal, then there are sets among them which consist of a mixture of elements of $A$ and elements of $B$. On the other hand $2^{A} \cup 2^{B}$ is the set of subsets of $A$ and subsets of $B$. Hence there are no sets in $2^{A} \cup 2^{B}$ which contain elements of $A$ as well as those of $B$ unless those elements are in $A \cap B$.
Since a subset of $A$($B$) is also a subset of $A \cup B$, $2^{A} \cup 2^{B}$ is a subset of $2^{A \cup B}$.