Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question

1 Answer 1

up vote 1 down vote accepted

(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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.