Tao Analysis I - 3.1.8

Exercise 3.1.8

Let $A$, $B$ be sets. Prove the absorption laws $A \cap (A \cup B)=A$ and $A \cup (A \cap B)= A$.

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

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

$$x \in (A \cap (A \cup B)) \iff (x \in A) \land ((x \in A) \lor (x \in B))$$

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true when $(x \in A)$. So we can say $A \cap (A \cup B) \implies A$.

We now need to show $A \implies A \cap (A \cup B)$. 

$$x \in A \implies x \in A \cup B$$

This is because, by definition, $A \subseteq A \cup X$ for any $X$. 

Furthermore, since $x \in A$ is true, we have

$$x \in A \implies (x \in A) \land (x \in A \cup B)$$

This is equivalent to $A \implies A \cap (A \cup B)$.

Having shown both  $A \cap (A \cup B) \implies A$ and $A \implies A \cap (A \cup B)$, we can conclude $A \cap (A \cup B) = A$. $\square$

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

Let's write out the LHS using the definitions of union and intersection.

$$x \in (A \cup (A \cap B)) \iff (x \in A) \lor ((x \in A) \land (x \in B))$$

This tells us that either, or both, of the following two statements are true:

• $(x \in A)$
• $(x \in A) \land (x \in B)$

These become two cases to consider. 

In the first case, $(x \in A)$, so $A \cup (A \cap B) \implies A$.

In the second case, $(x \in A) \land (x \in B) \implies $(x \in A)$, so again  $A \cup (A \cap B) \implies A$.

Both cases gives us $A \cup (A \cap B) \implies A$.

We now need to show $A \implies A \cup (A \cap B)$. This is straight forward, because $A \implies A \cup X$ for any $X$, by definition. So we have  $A \implies A \cup (A \cap B)$.

So having shown both $A \cup (A \cap B) \implies A$ and $A \implies A \cup (A \cap B)$, we can conclude $A \cup (A \cap B) = A$. $\square$

Note

The proof of the first identity can be shorted as follows:

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

$$x \in (A \cap (A \cup B)) \iff (x \in A) \land ((x \in A) \lor (x \in B))$$

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true if and only if $(x \in A)$. That is,

$$(x \in A) \land ((x \in A) \lor (x \in B)) \iff (x \in A)$$

So we can say $A \cap (A \cup B) = A$. $\square$