# Elementary Set theory proofs

1.) If $A$ and $B$ are any sets, show that $A \cap B = A -(A-B)$.

2.) Let $E$ be a set and $\{A_1,...,A_n\}$ be a collection of sets. Establish the De Morgran Laws: $$E- \cap^n_{j=1} A_j = \cup^n_{j=1} (E-A_j)$$ $$E-\cup^n_{j=1}A_j = \cap^n_{j=1}(E-A_j)$$

3.) If $B_1$ and $B_2$ are subsets of $B$ and if $B=B_1 \cup B_2$, then $$A \times B = (A\times B_1) \cup (A \times B_2)$$.

My attempt:

1.) Let $b\subset B$ and $x\in A-B$ which we will denote as C. Thus $C\subset A$. Now if we take $A-C$ then we have elements of $b\in A$ that were not in $A-B$, therefore $A-C \in A\cap B$ thus $A\cap B = A-(A-B)$. I know this proof is sloppy, hopefully someone can help me improve it.

2.) I know that the De Morgan Laws state that $A-(B\cup C) =(A-B)\cap (A-C)$. I also know that there must be a common element $A$ in $\cup^n_{j=1}A_j$ but I do not know how to proceed in completing the proof.

3.) Since $B\subset B_1 \cup B_2$ then $A \times (B_1 \cup B_2) = A \times B$ and since by the distributive property we have that $(A\times B_1) \cup (A \times B_2) = A \times (B_1 \cup B_2)$

-

(1) To show that two sets are equal, show that each is a subset of the other. Here that means showing that $A\cap B\subseteq A\setminus(A\setminus B)$ and that $A\setminus(A\setminus B)\subseteq A\cap B$. (I use $A\setminus B$ for set difference instead of the rather old-fashioned $A-B$.)

• To show that $A\cap B\subseteq A\setminus(A\setminus B)$, let $x$ be an arbitrary element of $A\cap B$, and show that $x\in A\setminus(A\setminus B)$. Since $x\in A\cap B$, we know that $x\in A$ and $x\in B$. In order to show that $x\in A\setminus(A\setminus B)$, we have to show that $x\in A$ and $x\notin A\setminus B$. We know that $x\in A$, so that part’s no problem. And since $x\in B$, $x\notin A\setminus B$, and we’re done: $x\in A$ and $x\notin A\setminus B$, so $x\in A\setminus(A\setminus B)$. We’ve just shown that every element of $A\cap B$ also belongs to $A\setminus(A\setminus B)$, which is exactly what it means to say that $A\cap B\subseteq A\setminus(A\setminus B)$.

• To show that $A\setminus(A\setminus B)\subseteq A\cap B$, let $x\in A\setminus(A\setminus B)$ be arbitrary, and show that $x\in A\cap B$. Since $x\in A\setminus(A\setminus B)$, we know that $x\in A$ and $x\notin A\setminus B$. To finish showing that $x\in A\cap B$, we just have to show that $x\in B$. But since $x\in A$ and $x\notin A\setminus B$, it must be the case that $x\in B$: if $x$ weren’t an element of $B$, it would be in $A\setminus B$, and it isn’t. Thus, $x\in A\cap B$, and $A\setminus(A\setminus B)\subseteq A\cap B$.

Putting the two pieces together, we see that $A\cap B=A\setminus(A\setminus B)$.

(2) Approach these in the same way. To show that

$$E\setminus\bigcap_{j=1}^nA_j=\bigcup_{j=1}^n(E\setminus A_j)\;,$$

prove that

$$E\setminus\bigcap_{j=1}^nA_j\subseteq\bigcup_{j=1}^n(E\setminus A_j)\quad\text{and}\quad\bigcup_{j=1}^n(E\setminus A_j)\subseteq E\setminus\bigcap_{j=1}^nA_j\;.$$

I’ll get you started.

• Suppose that $x\in E\setminus\bigcap_{j=1}^nA_j$. Then $x\in E$, and $x\notin\bigcap_{j=1}^nA_j$. The latter means that there is at least one $k$ such that $1\le k\le n$ and $x\notin A_k$. But then $x\in E\setminus A_k\subseteq\bigcup_{j=1}^nA_j$, and it follows that $E\setminus\bigcap_{j=1}^nA_j\subseteq\bigcup_{j=1}^n(E\setminus A_j)$.

• Now suppose that $x\in\bigcup_{j=1}^n(E\setminus A_j)$. Then there is some $k$, $1\le k\le n$, such that $x\in E\setminus A_k$. In other words, $x\in E$ and $x\notin A_k$. $A_k\supseteq\bigcap_{j=1}^nA_j$, so if $x\notin A_k$, then certainly $x\notin\bigcap_{j=1}^nA_j$, and since $x\in E$, we have $x\in E\setminus\bigcap_{j=1}^nA_j$. It follows that $\bigcup_{j=1}^n(E\setminus A_j)\subseteq E\setminus\bigcap_{j=1}^nA_j$.

Putting the pieces together yields the first of the two De Morgan’s laws. I’ll leave the second one for you; you should take the same basic approach, though of course the details will be different.

(3) And you want the same approach here: show that $A\times B\subseteq(A\times B_1)\cup(A\times B_2)$ and $(A\times B_1)\cup(A\times B_2)\subseteq A\times B$. The second of these is very easy. If $\langle a,b\rangle\in(A\times B_1)\cup(A\times B_2)$, then $\langle a,b\rangle\in A\times B_1$, or $\langle a,b\rangle\in A\times B_2$. Suppose that $\langle a,b\rangle\in A\times B_1$. Then $a\in A$ and $b\in B_1\subseteq B$, so $\langle a,b\rangle\in A\times B$. A similar argument shows that if $\langle a,b\rangle\in A\times B_2$, then $\langle a,b\rangle\in A\times B$, and it follows that $(A\times B_1)\cup(A\times B_2)\subseteq A\times B$.

The other direction is just as straightforward; I’ll leave it to you.

-
Thanks a million , Brian! Very helpful! – Q.matin Feb 2 '13 at 3:19
@Q.matin: You’re welcome. – Brian M. Scott Feb 2 '13 at 3:20