\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{graphicx}
\usepackage{lipsum}       % for sample text
\usepackage{changepage}   % for the adjustwidth environment
\usepackage{venndiagram}
\usepackage{enumerate}

\newenvironment{tabparagraph}{\begin{adjustwidth}{1.5cm}{}}{\end{adjustwidth}}

\begin{document}
{\flushleft\underline{Homework 1 --- MATH 4590 Spring 2018}} \\
\begin{enumerate}
\item Chapter 1, \# 1: Prove that for all sets $A, B, C$, the formula 
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
is true. \\
\textit{Proof}: It suffices to show that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ and $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$. Assume that $x \in A \cup (B \cap C)$, thus either $x \in A$ or $x \in B\cap C$. If $x \in A$, then $x \in A \cup B$ and $x \in A \cup C$, therefore $x \in (A \cup B) \cap (A \cup C)$. Now suppose that $x \in B \cap C$. Then $x \in B$ and $x \in C$, and so both $x \in A \cup B$ and $x \in A \cup C$, hence $x \in (A \cup B) \cap (A \cup C)$. Therefore $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.

Now we show that $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$. Assume that $x \in (A \cup B) \cap (A \cup C)$. Then $x \in A \cup B$ and $x \in A \cup C$. If $x \in A$, then $x \in A \cup (B \cap C)$, so assume that $x \not\in A$. \\
\begin{tabparagraph}
\indent \underline{Claim}: $x \in B \cap C$ \\
\indent \underline{Proof of claim}: Suppose that $x \not\in B \cap C$. Then $x \not\in B$ and $x \not\in C$. Since $x \not\in A$, it follows that both $x \not\in A \cup B$ and $x \not\in A \cup C$, a contradiction. Therefore $x \in B \cap C$. 
\end{tabparagraph}
Since $x \in B \cap C$, it follows that $x \in A \cup (B \cap C)$. Therefore $A (A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$. Therefore we have shown that $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, completing the proof. $\blacksquare$
\item Chapter 1, \# 2: 
\begin{enumerate}
\item Prove that $(A^c)^c=A$. \\
\textit{Proof}: Let $A^c$ denote the complement of $A$ in $X$, i.e. $A^c = X \setminus A$.  We shall show that $(A^c)^c \subseteq A$ and $A \subseteq (A^c)^c$. Let $x \in (A^c)^c$. Then $x \in X \setminus A^c$. But $X \setminus A^c = X \setminus (X \setminus A)$. 
\begin{tabparagraph}
\underline{Claim}: $X \setminus (X \setminus A) = A$ \\
\underline{\textit{Proof of claim}}: If $z \in X \setminus (X \setminus A)$, then $z$ is in the set of elements that are not in $X \setminus A$. Those elements are exactly the ones in $A$, by definition. Conversely, if $z \in A$, then $z \not\in X \setminus A$, and so $z$ is not removed when forming $X \setminus (X \setminus A)$, showing that $A \subset X \setminus (X \setminus A)$. Thus $X \setminus (X \setminus A)=A$.
\end{tabparagraph}
Since $x \in X \setminus (X \setminus A)$, we see from the claim that $x \in A$. Thus we have shown that $(A^c)^c \subseteq A$. 

Now let $x \in A$. Then $x \not \in X \setminus A$. Therefore $x \in X \setminus (X \setminus A)$. Since $X \setminus (X\setminus A) = X \setminus A^c = (A^c)^c$, we see that $A \subseteq (A^c)^c$. Therefore $(A^c)^c = A$, completing the proof. $\blacksquare$
\item Prove \textbf{deMorgan's law}: Prove
\begin{equation} 
(A \cap B)^c = A^c \cup B^c \label{firstdemorgan}
\end{equation} and derive from it the law 
\begin{equation}
(A \cup B)^c = A^c \cap B^c.\label{seconddemorgan}
\end{equation}
\textit{Solution}: First let us prove \eqref{firstdemorgan}. Let $x \in (A \cap B)^c$. Then $x \in X \setminus (A \cap B)$. This means that $x \not\in A \cap B$. Without loss of generality, assume that $x \not\in A$. Then $x \in A^c$, and so $x \in A^c \cup B^c$.

Now let $x \in A^c \cup B^c$. Then $x \in A^c$ or $x \in B^c$. Without loss of generality, asusme that $x \in A^c$. Then $x \not\in A$, so $x \not\in A \cap B$. Thus $x \in (A \cap B)^c$. Completing the proof. $\blacksquare$

To derive \eqref{seconddemorgan} from \eqref{firstdemorgan}, replace $A$ with $A^c$ and $B$ with $B^c$ in \eqref{firstdemorgan} to get
\begin{equation}
(A^c \cap B^c)^c = (A^c)^c \cup (B^c)^c.\label{thirddemorgan}
\end{equation}
On the right-hand-side note that by part (a), we know $(A^c)^c = A$ and $(B^c)^c=B$, so we get
$$(A^c \cap B^c)^c = A \cup B.$$
Taking the complement of each side and applying part (a) to the left-hand side yields the desired result:
$$A^c \cap B^c = (A \cup B)^c.$$
\item Draw Venn diagrams to illustrate the two laws. \\
\textit{Solution}: \\
 
$A^c$: \begin{venndiagram2sets} \fillNotA  \end{venndiagram2sets}
$B^c$: \begin{venndiagram2sets} \fillNotB \end{venndiagram2sets} \\
\underline{First law}: \\
$A \cup B$: \begin{venndiagram2sets} \fillA \fillB \end{venndiagram2sets} \\
$(A\cup B)^c=A^c \cap B^c$: \begin{venndiagram2sets} \fillNotAorB \end{venndiagram2sets} \\
\underline{Second law}: \\
$A \cap B$: \begin{venndiagram2sets} \fillACapB \end{venndiagram2sets} \\
$(A\cap B)^c = A^c \cup B^c$: \begin{venndiagram2sets} \fillNotAorNotB \end{venndiagram2sets} \\

\item Generalize these laws to more than two sets. \\
\textit{Solution}: Suppose we have three sets $A, B, C$ and we want to look at $(A \cap B \cap C)^c$. Write $X=B \cap C$, and observe
$$(A \cap B \cap C)^c = (A \cap X)^c \stackrel{\eqref{firstdemorgan}}{=} A^c \cap X^c = A^c \cap (B \cap C)^c \stackrel{\eqref{firstdemorgan}}{=} A^c \cap B^c \cap C^c.$$
This leads us to a conjecture: \\
\underline{Conjecture}: The following formula holds for $n=1,2,3,\ldots$:
$$(A_1 \cap A_2 \cap \ldots \cap A_n)^c = A_1^c \cup A_2^c \cup \ldots \cup A_n^c.$$
\textit{Proof}: The case $n=1$ holds trivially. The case $n=2$ was proven in part (b). The case $n=3$ was proven in the beginning of part (d). Assume the formula holds for $n=N$. We now prove it holds for $n=N+1$:
\begin{tabparagraph}
\underline{Claim}: If for all sets, $A_1, \ldots, A_N$,
\[ (A_1 \cap \ldots \cap A_N)^c = A_1^c \cup \ldots \cup A_N^c,\]
then  for any additional set $A_{N+1}$,
\[(A_1 \cap \ldots \cap A_N \cap A_{N+1})^c= A_1^c \cup \ldots \cup A_N^c \cup A_{N+1}^c .\] \\
\underline{\textit{Proof of claim}}: Define $\tilde{A_N}=A_N \cap A_{N+1}$. Then we see using the hypothesis of this claim that
$$(A_1 \cap \ldots \cap \tilde{A_N})^c = A_1^c \cup \ldots \cup \tilde{A_N}^c=A_1^c \cup \ldots \cup (A_N \cup A_{N+1})^c,$$
and so from the $n=2$ case of the conjecture (proved earlier), we may conclude
$$(A_1 \cap \ldots \cap \tilde{A_N})^c = A_1^c \cup \ldots \cup A_N^c \cup A_{N+1}^c,$$
completing the proof of the claim.
\end{tabparagraph}
Since this claim holds and the base cases $n=1$, $n=2$, and $n=3$ hold, we have shown via induction that the conjecture holds. $\blacksquare$
\end{enumerate}
\item Chapter 1, \# 6: Why is the square of and odd integer odd and the square of an even integer even? What is the situation for higher powers? \\
\textit{Solution}: Recall that any positive natural number has a unique prime factorization $n=p_1^{e_1}p_2^{e_2}\ldots p_{i}^{e_i},$ where the $p_1, \ldots, p_i$ are prime numbers with exponents $e_1, \ldots, e_i \in \mathbb{N}$. Since $2$ is prime and being even means being divisible by $2$, a number is even if and only if one of its prime factors $p_1, \ldots, p_i$ is equal to $2$. 

If $n$ is an odd integer, then when writing $n=p_1^{e_1}p_2^{e_2}\ldots p_i^{e^i}$, we observe that $p_1 \neq 2$ and $p_2 \neq 2$ and $\ldots$ and $p_i \neq 2$ (otherwise $n$ would be even). Now consider the square of $n$:
\[ n^2 = \left( p_1^{e_1}p_2^{e_2}\ldots p_i^{e_i} \right)^2 = \left( p_1^{e_1} \right)^{2} \left( p_2^{e_2} \right)^2\ldots \left(p_i^{e_i} \right)^2=p_1^{2e_1}p_2^{2e_2}\ldots p_i^{2e_i}. \]
We see that the only prime factors of $n^2$ are the same ones that are factors of $n$. Since $2$ was not a factor of $n$, it follows that $2$ is not a factor of $n^2$.

A similar argument shows that the square of an even must be even. This same argument holds for higher powers because
\[ n^{\ell} = \left( p_1^{e_1}p_2^{e_2}\ldots p_i^{e_i} \right)^{\ell} =p_1^{\ell e_1}p_2^{\ell e_2}\ldots p_i^{\ell e_i}. \]
\item In this problem, there is a known subset of $\mathbb{R}$ called $\mathscr{C}$ which has an upper bound. The set $C$ is defined by
\[ C=\{ a \in \mathbb{Q} \colon \text{for some cut } A|B \in \mathscr{C}, a \in A\} \]
and the set $D$ is defined by
\[ D = \mathbb{Q} \setminus C. \]
\begin{enumerate}
\item Claim 1: $C|D$ is a cut. \\
\textit{Solution}: We must argue that 
\begin{enumerate}[a.)]
\item $C \cup D = \mathbb{Q}$, $C \neq \emptyset$, $D \neq \emptyset$, and $C \cap D = \emptyset$,
\item if $c \in C$ and $d \in D$, then $c<d$, and
\item $C$ contains no largest element.
\end{enumerate}
By definition, $C \subset \mathbb{Q}$ and $C \cap D = \emptyset$. To prove a.), it follows from the definition of $D$ that $C \cup D = \mathbb{Q}$. We know that $C \neq \emptyset$ and $D \neq \emptyset$ because $C$ is bounded above. 

To prove b.), suppose there is a $c \in C$ and a $d \in D$ with $d \leq c$. Let $c=C_1|C_2$ and $d=D_1|D_2$. Then we may conclude that $D_1 \subseteq C_1$. But we cannot have $D_1=C_1$, because it would follow that $D_2=C_2$ and hence $c=d$ which contradicts the fact that $C \cap D = \emptyset$. If $D_1 \subsetneq C_1$, then by the definition of $C$, $d \in C$. But this cannot happen because $D = \mathbb{Q} \setminus C$. Hence we have shown that $D_1 \not\subset C_1$ and thus it is not true that $d \leq c$. Therefore b.) holds.

To prove c.), suppose that $C$ does contain a largest element -- call it $\tilde{c}$. Since $\tilde{c} \in \mathbb{Q}$ we can express it as $\dfrac{p}{q}$ for $p, q \in \mathbb{Z}$ with $q \neq 0$.  By the definition of $C$, there is some cut $A|B \in \mathscr{C}$ for which $\dfrac{p}{q} \in A$.
\begin{tabparagraph}
\underline{Claim}: $A|B = \tilde{c}$ \\
\underline{\textit{Proof}}: Since $\dfrac{p}{q} \in A$, it follows that $\tilde{c} \leq A|B$. Now we show that $A|B \leq \tilde{c}$. Suppose that $A|B > \tilde{c}$. Then if we write $\tilde{c}=\tilde{C}|\tilde{D}$, it follows that $\tilde{C} \subsetneq A$. But this means there is some larger $\hat{c}=\hat{C}|\hat{D} \in A$ with $\tilde{C} \subsetneq \hat{C} \subseteq A$. But this means that $\hat{c} \in C$ is a larger element of $C$ than $\tilde{c}$, a contradiction to $\tilde{c}$ being the largest. Therefore $A|B \leq \tilde{c}$ and since we proved earlier that $\tilde{c} \leq A|B$, we may conclude that $A|B=\tilde{c}$.
\end{tabparagraph}

So we see that may write the real number $\tilde{c}$ as the cut 
\[\tilde{c}=A|B=\left(-\infty,\dfrac{p}{q} \right) \cap \mathbb{Q} \Bigg| \left[\dfrac{p}{q},\infty \right) \cap \mathbb{Q}.\]
From this we observe that $\tilde{c} \not\in A$, a contradiction. Therefore $\tilde{c}$ cannot exist, i.e. $C$ has no largest element.

Therefore a.), b.), and c.) hold and we may conclude that $C|D$ is a cut. $\blacksquare$
\end{enumerate}
\item Claim 2: $C|D$ is an upper bound for $\mathscr{C}$ \\
\textit{Proof}: Let $E|F \in \mathscr{C}$. We will show that $E|F \leq C|D$. Since $E|F \in \mathscr{C}$, we know by the definition of $C$ that for all $a \in E$, $a \in C$, hence $E \subseteq C$. Therefore $E|F \leq C|D$. $\blacksquare$
\end{enumerate}
\end{document}