7
$\begingroup$

I have to resit a calculus exam and for some reason set proofs were never my best friend...

Anyway, on a practice exam I encountered the following proof:

$$A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$$

When I draw a Venn-diagram it seems quite obvious but I couldn't manage to write the proof down properly.

If someone could help me, that'd be great!

$\endgroup$
  • $\begingroup$ This question is closely related and the answer is very similar. $\endgroup$ – MJD Jul 3 '13 at 16:31
  • $\begingroup$ For proofs like this, using the definition of set operations (which are mostly) and using rules of inference always worked for me. $\endgroup$ – user1002327 Jul 3 '13 at 19:30
  • $\begingroup$ See also: math.stackexchange.com/questions/435433/… $\endgroup$ – Martin Sleziak Mar 4 '15 at 14:36
10
$\begingroup$

If $x\in A\cap(B\cup C)$, then $x\in A$ and $x\in B\cup C$.

$x\in B\cup C\implies (x\in B$ or $x\in C)$.

So, $x\in A\cap(B\cup C)\implies x\in (A\cap B)$ or $ x\in (A\cap C)$

$\implies x\in (A\cap B)\cup(A\cap C)$

$\implies A\cap(B\cup C)\subseteq (A\cap B)\cup(A\cap C)$.

Similarly,

if $y\in (A\cap B)\cup(A\cap C),$

$\implies y\in (A\cap B)$ or $y\in (A\cap C),$

$\implies y\in A$ and $y\in (B$ or $C)$

$\implies y\in A$ and $y\in (B \cup C)$

$\implies y\in A\cap (B \cup C)$.

Now, $A \subseteq B$ and $B \subseteq A \implies A=B$.

$\endgroup$
  • $\begingroup$ The inclusion you proved is not what the OP wanted. And then the reverse inclusion $A\cap(B\cup C)\supseteq (A\cup B)\cap(A\cup C)$ is false. $\endgroup$ – Ink Jul 4 '13 at 4:30
  • $\begingroup$ @Ink, can you please substantiate the last statement? $\endgroup$ – Sumit Bhowmick Jul 4 '13 at 4:52
  • $\begingroup$ @SumitBhowmick Consider $A = \{1, 2\}$, $B = C = \{1\}$. Then $A \cap (B \cup C) = \{1\}$, while $(A \cup B) \cap (A \cup C) = \{1, 2\}$. $\endgroup$ – Ink Jul 4 '13 at 5:00
  • $\begingroup$ @Ink, please have a look into the edited answer $\endgroup$ – lab bhattacharjee Jul 4 '13 at 8:03
  • $\begingroup$ It's correct now. $\endgroup$ – Ink Jul 4 '13 at 17:59
8
$\begingroup$

This can be done by algebra or by a truth table. In some cases there might be reasons why it would be necessary to use algebra. But not in all. Here's a truth table: $$ \begin{array}{|c|c|c|c|c|} \hline x\in A & x\in B & x\in C & x\in A\cap(B\cup C) & x\in (A\cap B)\cup(A\cap C) \\ \hline T & T & T & ? & ? \\ T & T & f & ? & ? \\ T & f & T & ? & ? \\ f & T & T & ? & ? \\ T & f & f & ? & ? \\ f & T & f & ? & ? \\ f & f & T & ? & ? \\ f & f & f & ? & ? \\ \hline \end{array} $$ You need (1) to make sure all eight possible rows are there, (2) to fill in the blanks, and (3) to check carefully that the last two columns are identical.

$\endgroup$
4
$\begingroup$

Hint: proofs by characteristic function :

for any $A \subset X$ define $1_A : X \to \{ 0,1\}$ by

$$1_A(x) = \left\{ \begin{eqnarray} \begin{split} 1 & \mbox{if } x \in A \\ 0 & \mbox{if } x \notin A \\ \end{split} \end{eqnarray}\right.$$ then we have

  • $A= B \Leftrightarrow 1_A = 1_B$
  • $1_{A \cap B}=1_A \cdot 1_B$
  • $1_{A \cup B}=1_A+1_B-1_A \cdot 1_B$

here we want prove$$ A\cap(B\cup C) = (A\cap B)\cup(A\cap C) \iff 1_{A\cap(B\cup C)} = 1_{(A\cap B)\cup(A\cap C)}$$ $\color{red}{proof:}$

1.$$ \large{1_{A\cap(B\cup C)}= 1_{A} 1_{B\cup C}=(1_{A} (1_B+1_C-1_B \cdot 1_C))=1_{A} 1_B+1_{A} 1_C-1_{A} \cdot1_B \cdot 1_C}$$ 2.$$\large{1_{(A\cap B)\cup(A\cap C)}=1_{(A\cap B)}+1_{(A\cap C)}-1_{(A\cap B)}\cdot1_{(A\cap C)}=1_{A} 1_B+1_{A} 1_C-1_{A} \cdot1_B \cdot 1_C}$$

$\endgroup$
3
$\begingroup$

First of all, two sets $A$ and $B$ are equal if and only if $A\subset B$ and $B\subset A$.

So, just use the fact that $x\in B\cup C$ if and only if $x\in B$ or $x\in C$ (or both).

Also, just use the fact that $x\in B\cap C$ if and only if $x\in B$ and $x\in C$.

Then, show that those two inclusions hold.

$\endgroup$
  • 3
    $\begingroup$ @Sigue, use $\subseteq$ instead of $\subset$ $\endgroup$ – lab bhattacharjee Jul 3 '13 at 16:35
  • 1
    $\begingroup$ @labbhattacharjee, why? $\endgroup$ – Sigur Jul 3 '13 at 16:37
  • 2
    $\begingroup$ But $\subset$ is not a symbol for proper subset, in my opinion. $A\subset B$ means $\forall x(x\in A\to x\in B)$. $\endgroup$ – Sigur Jul 3 '13 at 16:41
  • 3
    $\begingroup$ @labbhattacharjee: $\subset$ is also valid and popular notation of subset(not necessarily proper) $\endgroup$ – Aang Jul 3 '13 at 16:44
  • 3
    $\begingroup$ For reasons such as this silly argument, I use $\subsetneq$ to denote a proper subset. $\endgroup$ – Ted Shifrin Jul 3 '13 at 16:54
3
$\begingroup$

You have to show that a point is in the left side if and only if it is in the right side.

Take $x\in A\cap(B\cup C)$. It means that $$ x\in A\wedge(x\in B\vee x\in C)$$ To show that it is contained in the right side, assume that $x$ is not in $A\cap B$, so it is not in both $A$ and $B$. But we know that it is in $A$, so what does this imply for $B$?. Can you show that in this case $x$ must be in $A\cap C$?

For the reverse inclusion you can use the equivalences $$X\cup Y\subseteq Z \text{ if and only if }X\subseteq Z\text{ and }Y\subseteq Z$$ as well as $$X\subseteq Y\cap Z \text{ if and only if } X\subseteq Y\text{ and }X\subseteq Z$$ for aarbitrary sets $X,Y,Z$. It would be a good exercise to try the reverse inclusion only using these equivalences and the properties $X\cap Y\subseteq Y$ and $X\subseteq X\cup Y$ and without considering elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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