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

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

4 Answers 4


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.


($\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)$.


($\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 $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .