Exercise 3.1.6
Prove Proposition 3.1.27. (Hint: one can use some of these claims to prove others. Some of the claims have also appeared previously in Lemma 3.1.12.)
Let's write out Proposition 3.1.27.
Proposition 3.1.27 (Sets form a boolean algebra). Let $A$, $B$, $C$ be sets, and let $X$ be a set containing $A$, $B$, $C$ as subsets.
(a) (Minimal element) We have $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.
(b) (Maximal element)We have $A \cup X = X$ and $A \cap X=A$.
(c) (Identity) We have $A \cap A=A$ and $A \cup A=A$.
(d) (Commutativity) We have $A \cup B=B \cup A$ and $A \cap B=B \cap A$.
(e) (Associativity) We have $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.
(f) (Distributivity) We have $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.
(g) (Partition) We have $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.
(h) (De Morgan laws) We have $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.
Let's prove each in turn.
(a) Minimal Element
We need to show $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.
Let's start with the first and use the definition of a pairwise union, Axiom 3.5.
$$x \in (A \cup \emptyset) \iff (x \in A) \lor (x \in \emptyset)$$
The definition of an empty set, Axiom 3.5, tells us that an empty set has no members. That is, $x \in \emptyset$ is never true. So the above simplifies to
$$x \in (A\cup \emptyset) \iff (x \in A)$$
Thus $A\cup \emptyset = A$. $\square$
Now let's consider $A \cap \emptyset = \emptyset$ and use the definition of intersection, Definition 3.1.22.
$$x \in (A \cap \emptyset) \iff (x \in A) \land (x \in \emptyset)$$
The definition of an empty set, Axiom 3.5, tell us that an empty set has no members. So the expression $(x \in A) \land (x \in \emptyset)$ is always false. That is, $x \in (A\cap \emptyset)$ is never true.
Thus $A\cap \emptyset = \emptyset$. $\square$
(b) Maximal Element
We need to show $A \cup X = X$ and $A \cap X=A$.
We have already shown in Exercise 3.1.5 that $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent. Here we have $A \subseteq X$ and so $A \cup X=X$, $A \cap X=A$ are true. $\square$
(c) Identity
We need to show $A \cap A=A$ and $A \cup A=A$.
Let's use the definition of a pairwise union, Axiom 3.5, and equate $A = B$.
$$\begin{align}x \in (A \cup A) &\iff (x \in A) \lor (x \in A) \\ \\ & \iff (x \in A) \end{align}$$
This gives us $A \cap A=A$. $\square$
Now let's use the definition of intersection, Definition 3.1.22, and equate $A=B$.
$$\begin{align}x \in (A \cap A) &\iff (x \in A) \land (x \in A) \\ \\ & \iff (x \in A) \end{align}$$
This gives us $A \cup A=A$. $\square$
(d) Commutativity
We need to show $A \cup B=B \cup A$ and $A \cap B=B \cap A$.
Let's use the definition of a pairwise union, Axiom 3.5.
$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ & \iff (x \in B) \lor (x \in A) \end{align}$$
The second line is justified because logical disjunction is commutative.
So we have $A \cup B=B \cup A$. $\square$
Now let's use the definition of intersection, Definition 3.1.22.
$$\begin{align}x \in (A \cup B) &\iff (x \in A) \land (x \in B) \\ \\ & \iff (x \in B) \land (x \in A) \end{align}$$
The second line is justified because logical conjunction is commutative.
So we have $A \cap B=B \cap A$. $\square$
(e) Associativity
We need to show $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.
The first identity that union is associative is Lemma 3.1.12 proven in the text.
Now we turn to the second identity $(A \cap B) \cap C = A \cap (B \cap C)$. Using Definition 3.1.22 of intersection,
$$x \in (A \cap B) \cap C \iff (x \in A \cap B) \land (x \in C)$$
This gives us $x \in C$.
Considering $(A \cap B)$,
$$x \in (A \cap B) \iff (x \in A ) \land (x \in B)$$
This gives us $x \in A$ and $x \in B$.
So in summary we have that all $x \in A$, $x \in B$ and $x \in C$ are true.
Using $x \in B$ and $x \in C$, and Definition 3.1.22 of intersection,
$$(x \in B) \land (x \in C) \iff x \in (B \cap C)$$
And using $x \in A$,
$$(x \in A) \land (x \in B \cap C) \iff x \in A \cap (B\cap C)$$
That is, $(A \cap B) \cap C = A \cap (B \cap C)$. $\square$
(f) Distributivity
We need to show $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.
Let's start with the first identity, and use Definition 3.1.22 of intersection,
$$x \in (A \cap (B \cup C)) \iff (x \in A) \land (x \in (B \cup C))$$
This gives us $x \in A$ as true, as well as $x \in (B \cup C)$.
Consider $(B \cup C)$ and use the definition of a pairwise union, Axiom 3.5,
$$x \in (B \cup C) \iff (x \in B) \lor (x \in C)$$
This gives us two combinations, at least one of which must be true
- $(x \in A) \land (x \in B)$
- $(x \in A) \land (x \in C)$
"At least one of which must be true" means a disjunction between the two statements.
$$x \in (A \cap (B \cup C)) \iff (x \in A \land x\in B) \lor (x \in A \land x\in C)$$
This proves the first identity $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$. $\square$.
Now let's consider the RHS of the second identity, and use Definition 3.1.22 of intersection,
$$x \in ((A \cup B) \cap (A \cup C)) \iff (x \in (A \cup B)) \land (x \in (A \cup C))$$
Applying the definition of union Axiom 3.5, we have two combinations, both of which must be true
- $x \in A \lor x \in B$
- $x \in A \lor x \in C$
If $x \in A$ then both of these statements are true. If $x \not \in A$, then both statements are only true if $x \in B$ and $x \in C$. That is, $(x \in A) \lor ((x \in B) \land (x \in C))$.
So we have shown, $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$. $\square$
(g) Partition
We need to show $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.
Let's start with the first identity $A \cup (X \setminus A) = X$, and use Axiom 3.5 which defines union,
$$x \in (A \cup (X \setminus A)) \iff (x \in A) \lor (x \in X \setminus A)$$
Since $A \subseteq X$, we have $x \in A \implies x \in X$, which gives us
$$\begin{align}x \in (A \cup (X \setminus A)) &\implies (x \in X) \lor (x \in X \setminus A) \\ \\ &\implies x \in X\end{align}$$
The last step is true because $x \in X$ is true, or $x \in X \setminus A$ is true, and in both cases $x \in X$.
So we have $A \cup (X \setminus A) \subseteq X$. We now need to show $X \subseteq A \cup (X \setminus A)$.
Consider $x \in X$. Since $A \subseteq X$, we have $(x \in A) \lor (x \not \in A)$. The case $(x \not \in A)$ combined with $x \in X$, which is true by hypothesis, gives us $(x \in X \setminus A)$. So we have
$$x \in X \implies (x \in A) \lor (x \in X \setminus A)$$
That is, $X \subseteq A \cup (X \setminus A)$.
Having shown both $A \cup (X \setminus A) \subseteq X$, and $X \subseteq A \cup (X \setminus A)$, we can conclude $A \cup (X \setminus A) = X$. $\square$
Now let's consider the second identity $A \cap (X \setminus A) = \emptyset$, and use Definition 3.1.22 of intersection,
$$x \in (A \cap (X \setminus A)) \iff (x \in A) \land (x \in X \setminus A)$$
So both $(x \in A)$ and $(x \in X \setminus A)$ must be true. However, Definition 3.1.26 for set difference tells us that $(x \in X \setminus A)$ means $(x \not \in A)$. The only solution to this apparent contradiction is if $x \in \emptyset$.
So we have $A \cap (X \setminus A) = \emptyset$. $\square$
(h) De Morgan's Laws
We need to show $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.
Let's start with the first identity $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$, and use the Definition 3.1.26 for set difference.
$$x \in (X \setminus (A \cup B)) \iff (x \in X) \land (x \not \in (A \cup B))$$
Both statements $(x \in X)$ and $(x \not \in (A \cup B))$ must be true. Let's consider the second statement.
$$\begin{align}(x \not \in (A \cup B)) &\iff \neg((x \in A) \lor (x \in B)) \\ &\iff (x \not \in A) \land (x \not \in B)\end{align}$$
This is because $\neg(P \lor Q) \equiv (\neg P) \land (\neg Q)$.
We can write these as two combined statements, both of which must be true.
- $(x \in X) \land (x \not \in A)$
- $(x \in X) \land (x \not \in B)$
Which is equivalent to $(X \setminus A) \cap (X \setminus B)$.
So we have shown $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$. $\square$
Now let's consider the second identity $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$, and use the Definition 3.1.26 for set difference.
$$x \in (X \setminus (A \cap B)) \iff (x \in X) \land (x \not \in (A \cap B))$$
Both statements $(x \in X)$ and $(x \not \in (A \cap B))$ must be true. Let's consider the second statement.
$$\begin{align}(x \not \in (A \cap B)) &\iff \neg((x \in A) \land (x \in B)) \\ &\iff (x \not \in A) \lor (x \not \in B)\end{align}$$
We can write these as two combined statements, at least one of which must be true.
- $(x \in X) \land (x \not \in A)$
- $(x \in X) \land (x \not \in B)$
Which is equivalent to $(X \setminus A) \cup (X \setminus B)$.
So we have shown $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$. $\square$
No comments:
Post a Comment