# Prove these set statements

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

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

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

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

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

Here's what I've done? Did I do anything wrong?

http://s14.postimage.org/sz7ra5rdd/homew2.jpg

http://s11.postimage.org/pay0tu3oy/homew.jpg

-
Use latex to write your question.\cup = union and \cap = intersection. –  Reader Oct 29 '12 at 22:58
You should try to lear how to typeset using $\LaTeX$. People are more likely to help you then. See e.g. here. –  Fabian Oct 29 '12 at 23:00
When you think a set equality does not necessarily hold, you need to come up with an example, preferably a very concrete one, for which the said equality fails. For proving that an equality holds, use fewer logical symbols, and preferably deal separately with "any $x$ in the left set is in the right set" and "any $x$ in the right set $\dots$. –  André Nicolas Oct 29 '12 at 23:42
Is there any big mistake I've made? –  hjggh Oct 29 '12 at 23:43

There are some mistakes, and you’re going about some of them in a very awkward way (which may contribute to some of the mistakes). In the order in which I read your work:

You said of $(A\cap B)\cup(A\cap\overline B)=A$ that ‘the expressions are not equivalent’, but in fact they are:

\begin{align*} (A\cap B)\cup(A\cap\overline B)&\overset{(1)}=\Big((A\cap B)\cup A\Big)\cap\Big((A\cap B)\cup\overline{B}\Big)\\ &\overset{(2)}=A\cap\Big((A\cup\overline B)\cap(B\cup\overline B)\Big)\\ &=A\cap(A\cup\overline B)\cap U\\ &\overset{(3)}=A \end{align*}

In $(1)$ I used a distributive law; in $(2)$, an absorption law, since $A\cap B\subseteq A$; and in $(3)$ another absorption law, since $A\subseteq A\cup\overline B\subseteq U$.

In your work on the last one you omitted some essential parentheses: $A\cup B\cup C\cap A\cup A$ should be $(A\cup B\cup C)\cap(A\cup A)$, which simplifies to $(A\cup B\cup C)\cap A$, not $A\cup B\cup C\cap A$. From there you can proceed as follows:

\begin{align*} (A\cup B\cup C)\cap A&=(A\cap A)\cup(B\cap A)\cup(C\cap A)\\ &=\Big(A\cup(B\cap A)\Big)\cup(C\cap A)\\ &=A\cup(C\cap A)\\ &=A\;, \end{align*}

where the last two steps use absorption.

A shorter argument, by this way, is

\begin{align*} A\cup\Big((B\cup C)\cap A\Big)&=(U\cap A)\cup\Big((B\cup C)\cap A\Big)\\ &=\Big(U\cup(B\cup C)\Big)\cap A\\ &=U\cap A\\ &=A\;. \end{align*}

If you use the algebraic approach, as I’ve done here, your goal is a chain of equalities leading from one side of the original equation to the other. Your organization, transforming one side and carrying the other along so that you get a string of equations equivalent to the one that you’re trying to prove in hopes of reaching one that you know to be true, is okay when you’re feeling your way towards a solution, but it’s not a very good way to present a proof.

If you use the element-chasing approach, you can write the result as a chain of logical equivalences: for any $x\in U$,

\begin{align*} x\in A\cup\Big((B\cup C)\cap A\Big)&\leftrightarrow x\in A\lor x\in(B\cup C)\cap A\\ &\leftrightarrow x\in A\lor\Big(x\in B\cup C\land x\in A\Big)\\ &\leftrightarrow\Big(x\in A\lor x\in B\cup C\Big)\land\Big(x\in A\lor x\in A\Big)\\ &\leftrightarrow(x\in A\lor x\in B\lor x\in C)\land x\in A\\ &\leftrightarrow (x\in A\land x\in A)\lor(x\in B\land x\in A)\lor(x\in C\land x\in A)\\ &\leftrightarrow\Big(x\in A\lor(x\in A\land x\in B)\Big)\lor(x\in C\land x\in A)\\ &\leftrightarrow x\in A\lor(x\in A\land x\in C)\\ &\leftrightarrow x\in A\;, \end{align*}

so $A\cup\Big((B\cup C)\cap A\Big)=A$. Note that this is essentially the same as the algebraic proof.

You haven’t really answered the first question at all. Yes, $A\cap B$ is a subset of $A$, and that implies that $A\cup(A\cap B)=A$, but you’ve neither said so explicitly nor really demonstrated the fact. Here I’ll illustrate a style of argument that is usually easier to follow than either of the ones that I’ve used so far.

Suppose that $x\in A\cup(A\cap B)$; then $x\in A$, or $x\in A\cap B$, in which case $x\in A$ and $x\in B$. In either case $x\in A$, and since $x$ was an arbitrary element of $A\cup(A\cap B)$, it follows that $A\cup(A\cap B)\subseteq A$. Conversely, suppose that $x\in A$; then by definition $x\in A\cup(A\cap B)$, so $A\subseteq A\cup(A\cap B)$. Combining the two inclusions, we see that $A\cup(A\cap B)=A$.

You are correct in saying that $A\cup(B\cap C)=(A\cup B)\cap C$ is not an identity, but your counterexample is described very poorly. If $A$ really is the set of prime numbers, then $A\cup(B\cap C)$ is certainly not $\{3\}$. One very simple way to construct a counterexample is to let $A$ be any non-empty set, $B$ be any set at all, and $C=\varnothing$: then $A\cup(B\cap C)=A\cup\varnothing=A\ne\varnothing$, while $(A\cup B)\cap C=$ $(A\cup B)\cap\varnothing=\varnothing$.

Finally, it’s true that $(A\cap B)\cup(C\cap D)=(A\cap D)\cup(C\cap B)$ is not an identity, but you’ve not demonstrated this: for that you need a counterexample. Here’s a whole class of simple ones: let $A=B$ be any non-empty set, and let $C=D=\varnothing$. Then $(A\cap B)\cup(C\cap D)=A$, but $(A\cap D)\cup(C\cap B)=\varnothing$.

-
thanks for your hard work –  hjggh Oct 30 '12 at 18:29
@Mathilda: You’re welcome; I hope that it proves useful. –  Brian M. Scott Oct 30 '12 at 18:31

$$\begin{array}{|c|c|c|c|c|} \hline x\in A & x\in B & x\in C & x\in A\cup(B\cap C) & x\in (A\cup B)\cap C \\ \hline T & T & T & T & T \\ T & T & f & T & f \\ T & f & T & T & T \\ f & T & T & T & \cdots \\ T & f & f & T & \cdots \\ f & T & f & f & \\ f & f & T & f & \\ f & f & f & f & \\ \hline \end{array}$$ . . . . . and you can fill in the rest of the table. If there is just one line in which one of the truth values in the fourth and fifth columns is true and the other is false, then the proposed identity is not an identity. But if all eight rows agree, then it is. (In the latter case, you can also use algebraic methods to prove equality.)

-
can someone tell me if the steps i have taken make any sense? –  hjggh Oct 30 '12 at 11:40