CMSC 250 Fall 2004 -- Homework 9 Answer

Due Wed., Nov. 3 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.
Denote $A'$ the complement of $A$ and $P(A)$ the power set of $A$.

1. Find $P(\emptyset)$ and $P(P(P(\emptyset)))$.
   ANSWER: $P(\emptyset) = \{\emptyset\}$, $P(P(P(\emptyset))) = \{ \emptyset,\{\emptyset\},\{\{\emptyset\}\}, \{\emptyset,\{\emptyset\}\} \}$
   
   
2. Prove or disprove the followings:
   1. For all sets $A$ and $B$, $(A-B)\cup(A\cap B) \subseteq A$. ANSWER:
      Show: $(A-B)\cup(A\cap B) \subseteq A$
      Proof:
      Let A and B be arbitrary sets.
      Let x be arbitrary in U.
      $\vert$Assume $x \in (A-B)\cup(A\cap B)$
      $\vert$ $[x \in (A-B)] \vee [x \in (A \cap B)]$ by deff of union
      
      $\vert$Case 1: $x \in (A-B)$
      $\vert$ $\vert x \in A \wedge x \not\in B$ by def of set diff.
      $\vert$ $\vert x\in A$ by conjunctive simplification
      
      $\vert$Case 2: $x \in (A\cap B)$
      $\vert$ $\vert x \in A \wedge x \in B$
      $\vert$ $\vert x\in A$ by conjunctive simplification
      
      $\vert$ Therefore by dilemma $x \in A$
      $x \in (A-B) \cup (A \cap B) \rightarrow x \in A$ by CCW
      $\forall x \in U, x \in (A-B) \cup (A \cap B) \rightarrow x \in A$ by gen from GP
      Therefore, $(A-B)\cup(A\cap B) \subseteq A$ by def of subset
   2. For all sets $A$ and $B$, if $A \subseteq B$ then $B' \subseteq A'$. ANSWER:
      Proof:
      Let A and B be arbitrary sets.
      $\vert$ Assume $A \subseteq B$
      $\vert$ Let x be arbitrary in the U
      $\vert$ $\vert$Assume $x \in B'$
      $\vert$ $\vert$ $\vert$ Assume $x \not\in A'$
      $\vert$ $\vert$ $\vert$ $x \in A$ by def of set comp.
      $\vert$ $\vert$ $\vert$ $x \in B$ by def of subset
      $\vert$ $\vert$ $\vert$ $x \in B \wedge x \in B'$ conj add
      $\vert$ $\vert$ $\vert$ This is a contradition
      $\vert$ $\vert$Assume $x \in A'$ by CCW
      $\vert$ $x \in B' \rightarrow x \in A'$ by CCW
      $\vert$ $\forall x \in U, x \in B' \rightarrow x \in A'$ by gen from GP
      $\vert$ $B' \subseteq A'$ by def of subset
      
      $A \subseteq B \rightarrow B' \subseteq A'$ by CCW
      $\forall A,B \in \{sets\}, A \subseteq B \rightarrow B' \subseteq A'$ by gen from GP
      
      OR
      
      Let A and B be arbitrary Sets.
      $\vert$Assume $A \subseteq B$, which means
      $\vert$ $\forall x \in U, x\in A \rightarrow x\in B$ by def of subset.
      $\vert$The contrapositive is:
      $\vert\forall x \in U, x\not\in B \rightarrow x\not\in A$.
      $\vert$That means $\forall x \in U, x \in B' \rightarrow x \in A'$ by def of set comp.
      $\vert$which means $B' \subseteq A'$ by def of subset
      $A \subseteq B \rightarrow B' \subseteq A'$ by CCW
      Therefore, $\forall A,B \in \{sets\}, A \subseteq B \rightarrow B' \subseteq A'$ by generalizing from the GP.
   3. For all sets $A$,$B$ and $C$, $A\times(B\cap C) = (A\times B)\cap(A\times C)$. Show: $A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$
      Proof:
      Let A, B and C be arbitrary Sets.
      Let $(m,n)$ be arbitrary in U.
      $\vert$ Assume $(m,n) \in A \times (B \cap C)$.
      $\vert$ $m \in A \wedge n \in (B \cap C)$ by def of Cartesian Product.
      $\vert$ $m \in A \wedge n \in B \wedge n \in C$ by def of intersection.
      $\vert$ $(m \in A \wedge n \in B) \wedge (m \in A \wedge n \in C)$ by comm, assoc and idempotent
      $\vert$ $((m,n) \in A \times B) \wedge ((m,n) \in A \times C)$ by def of Cartesian Product.
      $\vert$ $(m,n) \in (A \times B) \cap (A \times C)$ by def of intersection
      $(m,n) \in A \times (B \cap C) \rightarrow (m,n) \in (A \times B) \cap (A \times C)$ by CCW.
      $\forall (m,n) \in U, (m,n) \in A \times (B \cap C) \rightarrow (m,n) \in (A \times B) \cap (A \times C)$ by gen from GP.
      $A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$ by def of subset.
      
      AND
      show: $(A \times B) \cap (A \times C) \subseteq A \times (B \cap C)$
      proof:
      Let A, B and C be arbitrary Sets.
      Let $(m,n)$ be arbitrary in U.
      $\vert$ Assume $(m,n) \in (A \times B) \cap (A \times C)$
      $\vert$ $(m,n) \in (A \times B) \wedge (m,n) \in (A \times C)$ by def of intersect
      $\vert$ $(m \in A \wedge n \in B) \wedge (m \in A \wedge n \in C)$ by def of cartesian product
      $\vert$ $m \in A \wedge (n \in B \wedge n \in C)$ by comm, assoc and idempotent
      $\vert$ $m \in A \wedge (n \in B \cap C)$ by def of intersection
      $\vert$ $(m,n) \in A \times (B \cap C)$ by def of cartesian product.
      $(m,n) \in (A \times B)\cap (A \times C) \rightarrow (m,n) \in A \times (B \cap C)$ by CCW
      $\forall (m,n) \in U, (m,n) \in (A \times B) \cap (A \times C) \rightarrow (m,n) \in A \times (B \cap C)$ by gen from GP
      $(A \times B) \cap (A \times C) \subseteq A \times (B \cap C)$ by def of subset
      
      Since from part 1 we know $A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$
      and from part 2 we know $(A \times B) \cap (A \times C) \subseteq A \times (B \cap C)$
      We know that $A\times(B\cap C) = (A\times B)\cap(A\times C)$ by definition of set equality.
   4. For all sets $A$,$B$ and $C$, if $B\cap C \subseteq A$ then $(C-A)\cap(B-A)=\emptyset$. Let A, B and C be arbitrary sets.
      $\vert$ Assume $B\cap C \subseteq A$
      $\vert$ $\vert$Assume $(C-A) \cap (B-A) \neq \emptyset$
      $\vert$ $\vert\exists m \in Z, m \in (C-A)\cap (B-A)$ by def of non-empty set
      $\vert$ $\vert m \in C-A \wedge m \in B-A)$ by def of intersect
      $\vert$ $\vert m \in C \wedge m \sim \in A \wedge m \in B \wedge m \not\in A$ by def of set diff.
      $\vert$ $\vert m \in C \wedge m \in B$ by conj simplification.
      $\vert$ $\vert m \in C \cap B$ by def of intersection
      $\vert$ $\vert m \in A$ by def of subset
      $\vert$ $\vert m \not\in A$ by conjunctive simplification
      $\vert$ $\vert$ This is a contradiction since m can't be both in A and not in A
      $\vert$ $(C-A)\cap(B-A)=\emptyset$ by CCW
      $B \cap C \subseteq A \rightarrow (C-A) \cap (B-A) = \emptyset$ by CCW
      $\forall A,B,C \in \{sets\},B \cap C \subseteq A \rightarrow (C-A) \cap (B-A) = \emptyset$ by gen from GP
      QED
   5. For all sets $A$,$B$ and $C$, $A - (B - C) = (A - B) \cup C$. Counterexample: $A=\{1\}$, $B=\emptyset$ and $C=\{2\}$.
   6. For all sets $A$ and $B$, $P(A\cap B) = P(A) \cap P(B)$. Show: $P(A\cap B) \subseteq P(A) \cap P(B)$.
      proof:
      let x be arbitrary in U.
      $\vert$Assume $x \in P(A\cap B)$
      $\vert$ $x \subseteq (A\cap B)$ by def of powerset.
      $\vert$ $x \subseteq A$ and $x \subseteq B$ by def of intersection
      $\vert$ $x \in P(A)$ and $x \in P(B)$ by def of powerset
      $\vert$ $x \in P(A)\cap P(B)$ by def of intersection
      $x \in P(A \cap B) \rightarrow x \in P(A) \cap P(B)$ by CCW
      $\forall x \in U, x \in P(A \cap B) \rightarrow x \in P(A) \cap P(B)$ by gen from GP.
      $P(A\cap B) \subseteq P(A) \cap P(B)$ by def of subset.
      
      Show: $P(A) \cap P(B) \subseteq P(A\cap B)$.
      Proof:
      Let x be arbitrary in U.
      $\vert$Assume $x \in P(A)\cap P(B)$
      $\vert x \in P(A) \wedge x \in P(B)$ by def of intersection
      $\vert x \subseteq A \wedge x \subseteq B$ by def of powerset
      $\vert$ Let g be arbitrary in U
      $\vert$ $\vert$Assume $g \in x$.
      $\vert$ $\vert g \in A$ by def of subset
      $\vert$ $\vert g \in B$ by def of subset
      $\vert$ $\vert g \in A \wedge g \in B$ by conj add
      $\vert$ $\vert g \in A \cap B$ by def of intersect
      $\vert$ $g \in X \rightarrow g \in A \cap B$ by CCW
      $\vert$ $\forall x \in U, g \in X \rightarrow g \in A \cap B$ by gen from GP
      $\vert$ $x \subseteq A \cap B$ by def of subset
      $\vert$ $x \in P(A\cap B)$ by def of powerset
      $x \in P(A) \cap P(B) \rightarrow x \in P(A \cap B)$ by CCW
      $\forall x \in U, x \in P(A) \cap P(B) \rightarrow x \in P(A \cap B)$ by gen from GP
      $P(A) \cap P(B) \subseteq P(A\cap B)$ by def of subset
      Since $P(A\cap B) \subseteq P(A) \cap P(B)$ and $P(A) \cap P(B) \subseteq P(A\cap B)$ we have $P(A\cap B) = P(A) \cap P(B)$ by def of set equality.
3. Prove, by induction:
   1. If $A\subseteq B_i$ for all $i$, then $A \subseteq (B_1\cap B_2\cap ...)$.
      Answer: Lemma 1: $A \subseteq B$ and $A\subseteq C$ implies $A \subseteq B\cap C$.
      Proof: $A \subseteq B$ and $A\subseteq C$
      $\Rightarrow$ $(x\in A \Rightarrow x\in B)$ and $(x\in A \Rightarrow x\in C)$
      $\Rightarrow$ $(x\in A \Rightarrow x\in B$ and $x\in C)$
      $\Rightarrow$ $(x\in A \Rightarrow x\in B\cap C)$
      $\Rightarrow$ $A \subseteq B\cap C$.
      Show: If $A\subseteq B_i$ for all $1\leq i\leq n$, then $A \subseteq (B_1\cap B_2\cap ... \cap B_n)$.
      Proof: by induction on $n\geq 2$.
      Base ($n=2$): If $A\subseteq B_1$ and $A\subseteq B_2$ then $A \subseteq (B_1\cap B_2)$ by lemme 1 above
      Induction hypothesis ($n=k$): If $A\subseteq B_i$ for all $1\leq i\leq k$, then $A \subseteq (B_1\cap B_2\cap ... \cap B_k)$
      Induction step ($n=k+1$):
      Show: If $A\subseteq B_i$ for all $1\leq i\leq k+1$, then $A \subseteq (B_1\cap B_2\cap ... \cap B_{k+1})$
      Proof:
      $A\subseteq B_i$ for all $1\leq i\leq k+1$
      $\Rightarrow$ $A\subseteq B_i$ for all $1\leq i\leq k$ and $A\subseteq B_{k+1}$
      $\Rightarrow$ $A \subseteq (B_1\cap B_2\cap ... \cap B_k)$ and $A\subseteq B_{k+1}$ (By IH)
      $\Rightarrow$ $A \subseteq (B_1\cap B_2\cap ... \cap B_k \cap B_{k+1})$ (by lemma 1 above)
      
   2. If $A_i \subseteq B$ for all $i$, then $(A_1 \cup A_2 \cup ...) \subseteq B$.
      Answer: Lemma 2: $A\subseteq C$ and $B\subseteq C$ implies $A\cup B \subseteq C$.
      Proof: $A\subseteq C$ and $B\subseteq C$
      $\Rightarrow$ $(x\in A \Rightarrow x\in C)$ and $(x\in B \Rightarrow x\in C)$ by def of subset
      $\Rightarrow$ $(x\not\in C \Rightarrow x\not\in A$ and $x\not\in B)$ by by contrapositive and distributive
      $\Rightarrow$ $(x\not\in C \Rightarrow x\in A'\cap B')$ by def of intersection
      $\Rightarrow$ $(x\not\in A'\cap B' \Rightarrow x\in C)$ by contrapositive
      $\Rightarrow$ $(x\in A\cup B \Rightarrow x\in C)$ by DeMorgan's
      $\Rightarrow$ $A\cup B \subseteq C$ by def of subset
      Show: If $A_i \subseteq B$ for all $1\leq i\leq n$, then $(A_1\cup A_2\cup ... \cup A_n) \subseteq B$.
      Proof: by induction on $n\geq 2$.
      Base ($n=2$): If $A_1\subseteq B$ and $A_2\subseteq B$ then $(A_1 \cup A_2) \subseteq B$ by Lemma 2 above
      Induction hypothesis ($n=k$): If $A_i \subseteq B$ for all $1\leq i\leq k$, then $(A_1\cup A_2\cup ... \cup A_k) \subseteq B$.
      Induction step ($n=k+1$):
      Show: If $A_i \subseteq B$ for all $1\leq i\leq k+1$, then $(A_1\cup A_2\cup ... \cup A_{k+1}) \subseteq B$.
      Proof:
      $A_i \subseteq B$ for all $1\leq i\leq k+1$
      $\Rightarrow$ $A_i \subseteq B$ for all $1\leq i\leq k$ and $A_{k+1} \subseteq B$
      $\Rightarrow$ $(A_1\cup A_2\cup ... \cup A_k) \subseteq B$ and $A_{k+1} \subseteq B$ (by IH)
      $\Rightarrow$ $(A_1\cup A_2\cup ... \cup A_{k+1}) \subseteq B$ (by Lemma 2 above

Web Accessibility