\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}

\newtheorem{thm}{Theorem}

\title{Proofs about Sets}
\author{Doug Baldwin}
\date{Spring 2021}


\begin{document}

\maketitle

In the following, we juxtapose two proofs about sets, one that uses an element chasing proof style and the other using set algebra. We start with the element chasing proof\ldots.

\begin{thm}
If $A$ and $B$ are subsets of some universal set, then $A - B = A \cap B^\mathrm{C}$.
\end{thm}

\begin{proof}
We will show that if $A$ and $B$ are subsets of some universal set, then $A - B = A \cap B^\mathrm{C}$ by showing that every element of $A-B$ is also in $A \cap B^\mathrm{C}$ and vice versa.

To show that every element of $A-B$ is also in $A \cap B^\mathrm{C}$, let $x$ be an element of $A-B$. From the definition of set difference, $x$ must be in $A$ and not in $B$. Since $x$ is not in $B$, $x$ is in $B^\mathrm{C}$. Now, since $x$ is in $A$ and in $B^\mathrm{C}$, $x$ is in $A \cap B^\mathrm{C}$.

Next, to show that every element of $A \cap B^\mathrm{C}$ is also in $A-B$, let $y$ be an element of $A \cap B^\mathrm{C}$. From the definitions of intersection and complement, $y$ must be in $A$ and not in $B$. Therefore, by the definition of set difference, $y$ is in $A - B$.

We have now shown that every element of $A-B$ is also in $A \cap B^\mathrm{C}$ and vice versa, thereby establishing that the sets are equal. This completes the proof that  if $A$ and $B$ are subsets of some universal set, then $A - B = A \cap B^\mathrm{C}$.
\end{proof}


Next, we turn to an example of an algebraic proof about sets.

\begin{thm}
If $A$, $B$, and $C$ are subsets of some universal set, then $(A \cap B) - C = (A-C) \cap (B-C)$.
\end{thm}

\begin{proof}
We show that if $A$, $B$, and $C$ are subsets of some universal set, then $(A \cap B) - C = (A-C) \cap (B-C)$ by using set algebra. We begin by rewriting set difference in terms of intersection, and then regroup the resulting expression:
\begin{align*}
(A \cap B) - C &= (A \cap B) \cap C^\mathrm{C} \\
  &= A \cap B \cap C^\mathrm{C} \cap C^\mathrm{C} \\
  &= (A \cap C^\mathrm{C}) \cap (B \cap C^\mathrm{C}) \\
  &= (A - C) \cap (B - C)
\end{align*}
We have thus shown that if $A$, $B$, and $C$ are subsets of some universal set, then $(A \cap B) - C = (A-C) \cap (B-C)$.
\end{proof}

\end{document}
