Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Proof.

The first part of this theorem was included in Exercise 7 from Section 5.2. The second part of the theorem was Exercise 12 from Section 5.2.

Proof.

We will prove that $A\cap B=B\cap A\text{.}$ Let $x\in U\text{.}$ Then

However, we know that if $P$ and $Q$ are statements, then $P\wedge Q$ is logically equivalent to $Q\wedge P\text{.}$ Consequently, we can conclude that

Now we know that

This means that we can use (40), (41), and (42) to conclude that

and, hence, we have proved that $A\cap B=B\cap A\text{.}$

Proof.

Let $A\text{,}$ $B\text{,}$ and $C$ be subsets of some universal set $U\text{.}$ We will prove that $A\cup \left(B\cap C\right)=\left(A\cup B\right)\cap \left(A\cup C\right)$ by proving that each set is a subset of the other set.

We will first prove that $A\cup \left(B\cap C\right)\subseteq \left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$ We let $x\in A\cup \left(B\cap C\right)\text{.}$ Then $x\in A\text{ or }x\in B\cap C\text{.}$

So in one case, if $x\in A\text{,}$ then $x\in A\cup B$ and $x\in A\cup C\text{.}$ This means that $x\in \left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$

On the other hand, if $x\in B\cap C\text{,}$ then $x\in B$ and $x\in C\text{.}$ But $x\in B$ implies that $x\in A\cup B\text{,}$ and $x\in C$ implies that $x\in A\cup C\text{.}$ Since $x$ is in both sets, we conclude that $x\in \left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$ So in both cases, we see that $x\in \left(A\cup B\right)\cap \left(A\cup C\right)\text{,}$ and this proves that $A\cup \left(B\cap C\right)\subseteq \left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$

We next prove that $\left(A\cup B\right)\cap \left(A\cup C\right)\subseteq A\cup \left(B\cap C\right)\text{.}$ So let $y\in \left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$ Then, $y\in A\cup B\text{ and }y\in A\cup C\text{.}$ We must prove that $y\in A\cup \left(B\cap C\right)\text{.}$ We will consider the two cases where $y\in A$ or $y\notin A\text{.}$ In the case where $y\in A\text{,}$ we see that $y\in A\cup \left(B\cap C\right)\text{.}$

So we consider the case that $y\notin A\text{.}$ It has been established that $y\in A\cup B$ and $y\in A\cup C\text{.}$ Since $y\notin A$ and $y\in A\cup B\text{,}$ $y$ must be an element of $B\text{.}$ Similarly, since $y\notin A$ and $y\in A\cup C\text{,}$ $y$ must be an element of $C\text{.}$ Thus, $y\in B\cap C$ and, hence, $y\in A\cup \left(B\cap C\right)\text{.}$

In both cases, we have proved that $y\in A\cup \left(B\cap C\right)\text{.}$ This proves that $\left(A\cup B\right)\cap \left(A\cup C\right)\subseteq A\cup \left(B\cap C\right)\text{.}$ The two subset relations establish the equality of the two sets. Thus, $A\cup \left(B\cap C\right)=\left(A\cup B\right)\cap \left(A\cup C\right)\text{.}$

Proof.

We will only prove one of De Morgan's Laws, namely, the one that was explored in Beginning Activty 1. The proofs of the other parts are left as exercises. Let $A$ and $B$ be subsets of some universal set $U\text{.}$ We will prove that ${\left(A\cup B\right)}^c=A^c\cap B^c$ by proving that an element is in ${\left(A\cup B\right)}^c$ if and only if it is in $A^c\cap B^c\text{.}$ So let $x$ be in the universal set $U\text{.}$ Then

and

Combining (43) and (44), we see that

In addition, we know that

and this is true if and only if $x\in A^c\cap B^c\text{.}$ So we can use equation (45) and equation (46) to conclude that

and, hence, that ${\left(A\cup B\right)}^c=A^c\cap B^c\text{.}$

Proof.

To prove that these are equivalent conditions, we will prove that Item 1 implies Item 2, that Item 2 implies Item 3, and that Item 3 implies Item 1.

Let $A$ and $B$ be subsets of some universal set $U\text{.}$ We have proved that Item 1 implies Item 2 in Proposition 5.20.

To prove that Item 2 implies Item 3, we will assume that $A\cap B^c=\mathrm{\varnothing }$ and use the fact that ${\mathrm{\varnothing }}^c=U\text{.}$ We then see that

Then, using one of De Morgan's Laws, we obtain

This completes the proof that Item 2 implies Item 3.

We now need to prove that Item 3 implies Item 1. We assume that $A^c\cup B=U$ and will prove that $A\subseteq B$ by proving that every element of $A$ must be in $B\text{.}$

So let $x\in A\text{.}$ Then we know that $x\notin A^c\text{.}$ However, $x\in U$ and since $A^c\cup B=U\text{,}$ we can conclude that $x\in A^c\cup B\text{.}$ Since $x\notin A^c\text{,}$ we conclude that $x\in B\text{.}$ This proves that $A\subseteq B$ and hence that Item 3 implies Item 1.

Since we have now proved that Item 1 implies Item 2, that Item 2 implies Item 3, and that Item 3 implies Item 1, we have proved that the three conditions are equivalent.