Homework 2 Solutions

Prove the following statements, assuming that all the named sets are subsets of a fixed universe E:
1. A and B are disjoint iff A < B'.
```
A and B are disjoint iff A ^ B = Ø
                     iff x in A & x in B <=> false, for all x in E
                     iff x in A => ¬(x in B), for all x in E
                     iff x in A => x in B', for all x in E
                     iff A is a subset of B
```
  Sorry, at this point it would take a lot of effort to continue converting this LaTeX code to HTML by hand. I've tried LaTeX2HTML, but it really is not satisfactory at this time. If you really use this form of the course handouts, please let me know and I will put more effort into getting them into a web-readable form; otherwise, I will concentrate on putting up only the homework questions rather than the solutions.
2. A = Ø iff (A ^ B') U (A' ^ B) = B. If $A=\emptyset$, then $A\cap B'=\emptyset$ and $A'\cap B=E\cap B=B$, so $(A\cap B')\cup(A'\cap B)=B$, as required. For the other direction, if $(A\cap B')\cup(A'\cap B)=B$, then we must have $A\cap B'=\emptyset$ and $A'\cap B=B$, because there can be no elements of $B$ in $A\cap B'$. By the previous problem, if $A$ and $B'$ are disjoint, then $A\subset B''=B$. Also, if the common elements of $A'$ and $B$ are all the elements of $B$, then it must be the case that $B\subset A'$; therefore by transitivity we may conclude $A\subset A'$. That is, if there were any element of $A$ it would also have to be an element of $A'$, which is a contradiction, so $A$ must be $\emptyset$.
3. (A - B) U (A - C) = A - (B ^ C). An object $x$ is an element of $(A-B)\cup(A-C)$ iff either $x$ is in $A-B$ or $x$ is in $A-C$. Saying $x\in A-B$ is equivalent to saying $x\in A\land x\not\in B$ (and hence is equivalent to $x\in A\cap B'$, when $A$ and $B$ belong to a fixed universe), so this becomes $(x\in A\land x\not\in B)\lor(x\in A\land x\not\in C)$. By the distributive law for propositions this is equivalent to $x\in A\land(x\not\in B\lor x\not\in C)$; one of the De Morgan laws shows that this is the same as $x\in A\land\lnot(x\in B\land x\in C)$. Using the definition of $B\cap C$ and the above observation about the difference operation, this is equivalent to $x\in A-(B\cap C)$, as desired.
4. (B - A) U (C - A) = (B U C) - A. \[\begin{array}{rclr} (B-A)\cup(C-A) & = & (B\cap A')\cup(C\cap A') & \textrm{see above}\\ & = & (B\cup C)\cap A' & \textrm{distributivity}\\ & = & (B\cup C)-A & \textrm{see above.} \end{array}\]
5. ^ P(A) = Ø. The intersection of all of the sets in $\P(A)$ is the collection of all the elements common to every subset of $A$; since the empty set is a subset of any set $A$, there can be no such common elements, therefore the intersection is $\emptyset$.
6. P(A) ^ P(B) = P(A ^ B). \[\begin{array}{rcl} \P(A)\cap\P(B) & = & \{X:X\in\P(A)\land X\in\P(B)\}\\ & = & \{X:X\subset A\land X\subset B\}\\ & = & \{X:X\subset A\cap B\}\\ & = & \P(A\cap B). \end{array}\] The third line depends on the fact that $X$ is a subset of both $A$ and $B$ iff it is a subset of their intersection---this follows in the forward direction by noting that if all the elements of $X$ are in $A$ and also in $B$, then certainly they will be in $A\cap B$; the reverse direction follows simply by observing that $A\cap B\subset A$ and $A\cap B\subset B$, and using transitivity of $\subset$.
7. P(A) U P(B) < P(A U B). If $X\in\P(A)\cup\P(B)$, then either $X\in\P(A)$ or $X\in\P(B)$, \textit{i.e.}, either $X\subset A$ or $X\subset B$. Since both $A$ and $B$ are subsets of $A\cup B$, this means that $X$ must be a subset of $A\cup B$, hence $X\in\P(A\cup B)$.
When is it the case that P(A) U P(B) = P(A U B)? If $A\subset B$ (or, symmetrically, $B\subset A$) then we have $A\cup B=B$ and $\P(A)\cup\P(B)=\P(B)$, hence the two sides are equal when one of $A$ and $B$ is a subset of the other. To show that this is the most general case, suppose that $A$ and $B$ are incomparable, that is, that neither $A\subset B$ nor $B\subset A$. This means there must be elements $a\in A-B$ and $b\in B-A$, so consider the pair $\{a,b\}$: it is certainly a subset of $A\cup B$, hence it is an element of $\P(A\cup B)$, but it is not a subset of either $A$ or $B$ alone, so it does not occur in $\P(A)\cup\P(B)$, therefore the sets are not equal.

(Note that I am using < for subset, Ø for the empty set, and ^ for both unary and binary intersection. Also, U is union and P is powerset.)