Exercise 3.1.6 (Sets form a boolean algebra)

Proof.

(a)

• ($A\cup \varnothing =A$) This was already proven in Exercise 3.1.3.
• ($A\cap \varnothing =\varnothing$) By Definition 3.1.23, $x$ is an element of $A\cap \varnothing$ means that $x$ is an element of $A$ and $x$ is an element of $\varnothing .$ But $x$ can not be an element of $\varnothing$, and therefore, $x\in A\cap \varnothing$ is false and therefore, equivalent to $x\in \varnothing .$ By Definition 3.1.4 this means that $A\cap \varnothing =\varnothing .$

(b)

By the theorem assumption we have $A\subseteq X.$ By Exercise 3.1.5, this implies that $A\cup X=X$ and $A\cap X=X$.

(c)

We have $$\forall <!--\; FUNCTION\; APPLICATION\; -->x:(x\in A\text{and}x\in A)⟺x\in A,$$

which means that every element of $A\cap A$ is an element of $A$ and vice versa. By Definition 3.1.4, we therefore have $A\cap A=A.$
We have

$$\forall <!--\; FUNCTION\; APPLICATION\; -->x:(x\in A\text{or}x\in A)⟺x\in A,$$

which means that every element of $A\cup A$ is an element of $A$ and vice versa. By Definition 3.1.4, we, therefore, have $A\cup A=A.$

(d)

• ($A\cup B=B\cup A$) This was already proven in Exercise 3.1.3.
• ($A\cap B=B\cap A$) Let $x\in A\cap B$ be arbitrary. Then, $x$ is contained in $A$ and $x$ is contained in $B.$ But this is equivalent to the fact that $x$ is contained in $B$ and $x$ is contained in $A.$ But the last statement is equivalent to $x\in B\cap A$ by Definition 3.1.23. Since our choice of $x$ was arbitrary, $A\cap B=B\cap A.$

(e)

• ($(A\cup B)\cup C=A\cup (B\cup C)$) This was already proven in Exercise 3.1.3.

• ($(A\cap B)\cap C=A\cap (B\cap C)$) By Exercise 3.1.4, it suffices to show that $(A\cap B)\cap C\subseteq A\cap (B\cap C)$ and vice versa.

  $(A\cap B)\cap C)\subseteq (A\cap (B\cap C)$

  Let $x\in (A\cap B)\cap C$ be arbitrary. By Definition 3.1.23, we have $x\in (A\cap B)$ and $x\in C$. By Definition 3.1.23 again, $x\in (A\cap B)$ means that $x\in A$ and $x\in B$ both hold. Since $x\in A,x\in B,$ and $x\in C$ all hold, $x\in (B\cap C)$ is true, and therefore, since $x\in A$ is true as well, $x\in A\cap (B\cap C)$ holds, as desired.

  $A\cap (B\cap C)\subseteq ((A\cap B)\cap C)$

  Let $x\in A\cap (B\cap C)$ be arbitrary. By Definition 3.1.23, we have $x\in (B\cap C)$ and $x\in A$. By Definition 3.1.23 again, $x\in (B\cap C)$ means that both $x\in B$ and $x\in C$ hold. Since $x\in A,x\in B,$ and $x\in C$ are all true, $x\in (B\cap C)$ is true, and therefore, since $x\in A$ is true, $x\in A\cap (B\cap C)$ is also true, as desired.

(f)

$\text{(∗)}$

$[A\cap (B\cup C)=(A\cap B)\cup (A\cap C)]$ By Exercise 3.1.4 it suffices to show that $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ and vice versa.

• Let $x\in A\cap (B\cup C)$ be arbitrary. By Definition 3.1.23, we have $x\in A$ and $x\in B\cup C.$ By Axiom 3.4, $x\in B\cup C$ means that $x\in B$ or $x\in C.$ We now look at these cases.

  $x\in B$

  Since $x\in B,$ we have $x\in A\cap B$. Therefore, by Axiom 3.4, we have $x\in (A\cap B)\cup (A\cap C).$

  $x\in C$

  Since $x\in C,$ we have $x\in A\cap C$. Therefore, by Axiom 3.4, we have $x\in (A\cap B)\cup (A\cap C).$

  Since our choice of $x$ was arbitrary, we have $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C).$

• Let $x\in (A\cap B)\cup (A\cap C)$ be arbitrary. By Axiom 3.4, we now have $x\in A\cap B$ or $x\in A\cap C.$ We now look at both of these cases.

  $x\in A\cap B$

  In this case, we have $x\in A$ and $x\in B$ by Definition 3.1.23. Since $x\in B,$ we have $x\in B\cup C$ by Axiom 3.4. Since $x\in A$ as well, by the definition of intersection we have $x\in A\cap (B\cup C).$ Therefore, since $x$ is contained also in $A\cap (B\cup C)$.

  $x\in A\cap C$

  In this case, we have $x\in A$ and $x\in C.$ Since $x\in C,$ we have by Axiom 3.4, $x\in B\cup C.$ Since $x\in A,$ by Definition 3.1.23, we have $x\in A\cap (B\cup C).$

Since our choice of $x$ was arbitrary, $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ and $(A\cap B)\cup (A\cap C)\subseteq A\cap (B\cup C)$ both hold.

$\text{(∗)}$

By Exercise 3.1.4 it suffices to show that $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$ and vice versa.

• ($A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C))$ Let $x\in A\cup (B\cap C)$ be arbitrary. By Axiom 3.4, we have $x\in A$ or $x\in B\cap C.$ We now look at these cases.

  $x\in A$

  Since $x\in A$, we have $x\in A\cup B$ and $x\in A\cup C.$ Hence, we have $x\in (A\cup B)\cap (A\cup C)$ by Definition 3.1.23.

  $x\in B\cap C$

  Since $x\in B\cap C,$ we have $x\in B$ and $x\in C$ by Definition 3.1.23. Since $x\in B$, we have $x\in A\cup B$ by Axiom 3.4. Similarly, since $x\in C,$ $x\in A\cup C.$ Since $x\in A\cup B$ and $x\in A\cup C$, we have $x\in (A\cup B)\cap (A\cup C).$

• $((A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C))$ Let $x\in (A\cup B)\cap (A\cup C)$ be arbitrary. By Definition 3.1.23, we have $x\in A\cup B$ and $x\in A\cup C.$ We now look at these cases. By Axiom 3.4, we have $(x\in A$ or $x\in B)$ and $(x\in A$ or $x\in C).$ For this statement to be true, at least one of the conditions $x\in A$, $x\in B$ of the first part and at least one of the conditions $x\in A$, $x\in C$ of the second part must be true. We end up with four cases: $x\in A$ and $x\in A$; $x\in A$ and $x\in C;$ $x\in B$ and $x\in A;$ $x\in B$ and $x\in C.$

  $(x\in A$ and $x\in A)$

  $x\in A$ and $x\in A$ is the same as $x\in A$; since $x\in A,$ by Axiom 3.4 we have $x\in A\cup (B\cap C).$

  $(x\in A$ and $x\in C)$

  Since $x\in A,$ we have $x\in A\cup (B\cap C).$

  $(x\in B$ and $x\in A)$

  Since $x\in A,$ we have $x\in A\cup (B\cap C).$

  $(x\in B$ and $x\in C)$

  Since $x\in B$ and $x\in C,$ we have $x\in B\cap C.$ Therefore, $x\in A\cup (B\cap C).$

(g)

($\text{∗)}$

$[A\cup (X\setminus A)=X]$ By Exercise 3.1.4, it suffices to show that $A\cup (X\setminus A)\subseteq X$ and vice versa.

• ($A\cup (X\setminus A)\subseteq X$) Let $x\in A\cup (X\setminus A)$ be arbitrary. By Axiom 3.4, $x\in A$ or $x\in X\setminus A$. In the first case $x\in X$ since $A\subseteq X$ by the theorem assumption. In the latter case, $x\in X$ and $x\notin A$ in particular implies that $x\in X$. Thus, $x\in X$ in both cases, and we are done.
• ($X\subseteq A\cup (X\setminus A)$) Let $x\in X$ be arbitrary. Since by theorem assumption $A\subseteq X,$ $x\in X$ means that $x\in A$ or $x\notin A$. We now look at these cases. In the first case, we have $x\in A\cup (X\setminus A)$ by Axiom 3.4. In the latter case, $x\in X$ combined with $x\notin A$ implies that $x\in X\setminus A$ by Definition 3.1.27. Therefore, $x\in A\cup (X\setminus A)$ holds by Axiom 3.4.

($\text{∗)}$

($A\cap (X\setminus A)=\varnothing$) Let $x\in A\cap (X\setminus A)$ be arbitrary. We have $x\in A$ and $x\in X\setminus A.$ By definition of set difference $x\in X\setminus A$ is equivalent to $x\in X$ and $x\notin A.$ Therefore, $x\in A\cap (X\setminus A)$ is equivalent to $x\in A$ and $x\in X$ and $x\notin A.$ But $x\in A$ and $x\notin A$ cannot hold at once, therefore, we have $A\cap (X\setminus A)=\varnothing .$

(h)

(De Morgan’s laws)

($\text{∗)}$

$(X\setminus (A\cup B)=(X\setminus A)\cap (X\setminus B))$ By Exercise 3.1.4 it suffices to show that $X\setminus (A\cup B)\subseteq (X\setminus A)\cap (X\setminus B)$ and vice versa.

• ($X\setminus (A\cup B)\subseteq (X\setminus A)\cap (X\setminus B)$) Let $x\in X\setminus (A\cup B)$ be arbitrary. Therefore, we have $x\in X$ and $x\notin A\cup B.$ $x\notin A\cup B$ means that $x\notin A$ and $x\notin B$¹ . Thus, $x\in X\setminus (A\cup B)$ means that $x\in X$ and $x\notin A$ and $x\notin B$. Therefore, $x\in X\setminus A$, $x\in X\setminus B$ hold by Definition 3.1.27, and therefore, $x\in (X\setminus A)\cap (X\setminus B)$ by Definition 3.1.23.
• ($(X\setminus A)\cap (X\setminus B)\subseteq X\setminus (A\cup B)$) Let $x$ in $(X\setminus A)\cap (X\setminus B)$ be arbitrary. We have $x\in X\setminus A$ and $x\in X\setminus B.$ By the definition of set difference we have $x\in X$ and $x\notin A$ and $x\notin B.$ Thus, we have $x\notin A\cup B$ (see the footnote). Since $x$ is also contained in $X,$ we have $x\in X\setminus (A\cup B).$

($\text{∗)}$

($X\setminus (A\cap B)=(X\setminus A)\cup (X\setminus B)$) By Exercise 3.1.4 it suffices to show that $X\setminus (A\cap B)\subseteq (X\setminus A)\cup (X\setminus B)$ and vice versa.

• ($X\setminus (A\cap B)\subseteq (X\setminus A)\cup (X\setminus B)$) Let $x\in X\setminus (A\cap B)$ be arbitrary. Then, by the definition of set difference, we have $x\in X$ and $x\notin A\cap B.$ $x\notin A\cap B$ means that $x\notin A$ or $x\notin B$ ² . We now look at these cases.

  $x\notin A$

  Since $x\in X$ and $x\notin A,$ we have $x\in X\setminus A.$ Therefore, $x\in (X\setminus A)\cup (X\setminus B)$ is also true.

  $x\notin B$

  Since $x\in X$ and $x\notin B,$ we have $x\in X\setminus B.$ Therefore, $x\in (X\setminus A)\cup (X\setminus B)$ is also true.

• ($(X\setminus A)\cup (X\setminus B)\subseteq X\setminus (A\cap B)$) Let $x\in (X\setminus A)\cup (X\setminus B)$ be arbitrary. Then, $x\in X\setminus A$ or $x\in X\setminus B.$ We now look at these cases.

  $x\in X\setminus A$

  We have $x\in X$ and $x\notin A$ by definition of set difference. Since $x\notin A,$ $x\notin A\cap B$. Since $x\in X\text{ and }x\notin A\cap B$ we can conclude that $x\in X\setminus (A\cap B).$

  $x\in X\setminus B$

  We have $x\in X$ and $x\notin B$ by definition of set difference. Since $x\notin B,$ $x\notin A\cap B$. Since $x\in X\text{ and }x\notin A\cap B$ we can conclude that $x\in X\setminus (A\cap B).$