# Proof of two theorems in elementary set theory

I have been self-studying elementary set theory, but the answer in the textbook i am using seems rather conversational and brief. Can any one provide a rigorous proof for the following two questions?

Prove that $$A=(A \cap B)\cup (A \cap B^c)$$ and $$A \cup B= B \cup (A \cap B^c)$$

• Is $B^c$ the complement of $B$? – Laertes Jun 5 '15 at 15:08
• Which axioms and/or definitions do you have that the proofs should start from? – Henning Makholm Jun 5 '15 at 15:08
• @laertes yes, @ henning makholm just indicate the theorem you have used is fine by me! – chuck Jun 5 '15 at 15:10
• @Cheuk: Then I declare those two formulas to be axioms. Proof complete! – Henning Makholm Jun 5 '15 at 15:14

It is straightforward using Algebra of sets.

$$(A\cap B)\cup (A\cap \overline{B})\stackrel{\text{Distr}}=((A\cap B)\cup A)\cap((A\cap B)\cup \overline{B})$$

$$\stackrel{\text{Absorp}}=A\cap((A\cap B)\cup\overline{B})\stackrel{\text{Distr}}=A\cap((A\cup \overline{B})\cap (B\cup\overline{B}))$$

$$=A\cap((A\cup \overline{B})\cap U)=A\cap(A\cup \overline{B})\stackrel{\text{Absorp}}=A$$

Distr - distributive law, Absorp - absorption law. Distr is simply proved using logic laws, which in turn are proved using truth tables. E.g.:

$$(x\in ((X\cup Y)\cap Z))\iff ((x\in (X\cup Y))\wedge (x\in Z))$$

$$\iff (((x\in X)\lor (x\in Y))\wedge (x\in Z))$$ $$\iff (((x\in X)\wedge (x\in Z))\lor ((x\in Y)\wedge (x\in Z)))$$

$$\iff ((x\in X\cap Z)\lor (x\in Y\cap Z))\iff (x\in ((X\cap Z)\cup (Y\cap Z)))$$

To prove Absorp, you prove $x\in A\,\Leftrightarrow\, x\in ((A\cap B)\cup A)$ and $x\in A\,\Leftrightarrow\, x\in (A\cap (A\cup \overline{B}))$, which is very simple.

$$B\cup(A\cap\overline{B})\stackrel{\text{Distr}}=(B\cup A)\cap (B\cup\overline{B})=(B\cup A)\cap U=A\cup B$$

I'll do the first one to illustrate the flavor. Then see if you can do something similar for the second.

(1)

($\subseteq$): Let $x \in A$. Then $x \in B$ or $x \not \in B$.

Case 1: $x \in B$.

Then $x \in A \cap B$.

Case 2: $x \not \in B$.

Then $x \in B^c$, and so $x \in A \cap B^c$.

Hence, $x \in (A \cap B) \cup (A \cap B^c)$. Therefore $A \subseteq (A \cap B) \cup (A \cap B^c)$.

($\supseteq$): Now, $A \cap B \subseteq A$ and $A \cap B^c \subseteq A$, and so $(A \cap B) \cup (A \cap B^c) \subseteq A$.

Thus, $A = (A \cap B) \cup (A \cap B^c)$.

(2)

($\subseteq$): Let $x \in A \cup B$. Then $x \in A$ or $x \in B$.

Case 1: $x \in B$.

Then $x \in B \cup (A \cap B^c)$.

Case 2: $x \in A$.

Then $x \in B$ or $x \not \in B$.

[Break this into subcases and follow each one.]

($\supseteq$): Let $x \in B \cup (A \cap B^c)$. Then $x \in B$ or $x \in A \cap B^c$.

[Run down each case.]

These are quite obvious if you just draw the Euler diagram. But a totally formal proof is like this.

Let $x \in A$ let's see that x belongs also to the right hand side. This is true because there are only two possibilities: $x \in B$ so that $x \in A \cap B$, or $x \in B^c$ so that $x \in A \cap B^c$. In any case $x$ belongs also to the set on the right hand side. Vice versa, let $x$ belongs to the set on the right hand side, then $x \in A\cap B$ or $x \in A \cap B^c$, in any case $x \in A$

Algebraic proofs can be very efficient once you're used to them.

Here, we can use distributivity:

$$A = A \cap U = A \cap (B \cup B^c) = (A \cap B) \cup (A \cap B^c)$$

where $U$ is the universe. Reading this from left to right demonstrates a common and useful trick for splitting a problem up into pieces (and is the way this proof first enters my mind). It may be more evident to you, though, if you read it right to left.

As it turns out, the formula for $A \cup B$ can be obtained by starting with

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