\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}
\usepackage{hyperref}

% for the smiley face
\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.75in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}

\newcommand{\bproof}{\noindent {\bf Proof:} \quad}
\newcommand{\eproof}{$\blacksquare$}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2.25in}{\bf Math 2110}
\hfill {\Large \bf Homework \#8} \hfill
\parbox{2.25in}{\bf \hfill Due: Fri., Oct. $23^\mathrm{rd}$, 2020}

\vspace{0.1in}

%\noindent {\large\bf Name:} \underline{\Large\quad My Name Goes Here \quad} \hfill 

\force \hfill Handwritten solutions are fine. \smiley  % uses wasysym package. :)
\hfill \force

\vspace{0.2in}

\noindent
{\it Note:} In this homework we will let $\emptyset = \{ \}$ denote the empty set. Also, recall that $A-B = \{ a \in A \;|\; a \not\in B\}$ is the {\it relative complement} of $B$ in $A$ (or the {\it set difference} between $A$ and $B$).

\vspace{0.01in}

\begin{description}
\item[\#1] Short proof. Let $\mathbb{Z}$ be the integers, $\mathbb{E}$ the even integers, and $\mathbb{O}$ the odd integers.

Use set builder notation to define $\mathbb{E}$ and $\mathbb{O}$. Then prove that $\mathbb{Z} = \mathbb{E} \cup \mathbb{O}$. Then explain why $\mathbb{E} \cap \mathbb{O} = \emptyset$.

\item[\#2] Let $A$ and $B$ be sets. Prove that $A = (A-B) \cup (A \cap B)$.  

Include a Venn diagram picture to help illustrate why this is true (this picture is {\it not} sufficient as a proof).

\item[\#3] Let $A = \{ 8n \;|\; n \in \mathbb{Z} \}$, $B = \{ 8n+4 \in \mathbb{Z} \;|\; n \in \mathbb{Z} \}$, and $C= \{ x \in \mathbb{Z} \;|\; x \text{ is divisible by } 4\}$. Prove that $A \cup B = C$.

\item[\#4] Prove that $\bigcup \{ [n,n+1] \;|\; n \in \mathbb{Z}\} = \mathbb{R}$. \qquad Alternate notation: $\bigcup\limits_{n \in \mathbb{Z}} [n,n+1] = \mathbb{R}$.

{\it Notes:} The set $[n,n+1] = \{ x \in \mathbb{R} \;|\; n \leq x \leq n+1 \}$ is the closed interval from $n$ to $n+1$. Also, you probably will want to recall that $\lfloor r \rfloor \leq r < \lfloor r \rfloor +1$ for any real number $r$ where the floor function of $r$, $\lfloor r \rfloor$, just rounds down to the nearest integer.

\item[\#5] Prove that given a set $A$ with $m$ elements and a set $B$ with $n$ elements that $A \times B$ has $m\cdot n$ elements.

{\it Hint/Recommendation:} Use induction on the size of $B$.
\end{description}


\vspace{0.2in}

\noindent
An an example, I will carefully prove, given a set $X$ with $n$ elements, we have that $\mathcal{P}(X)$ has $2^n$ elements.

\vspace{0.2in}

\noindent \fbox{\large\bf Prop:} Let $X$ be a set of $n$ elements (for some natural number $n$), then $\mathcal{P}(X)$, the power set of $X$, has $2^n$ elements.

\vspace{0.1in}

\bproof
We will proceed by induction on the size of our sets.
\begin{description}
\item[Base case:] Let $X$ be a set of $0$ elements. Then $X =\emptyset$ and so $\mathcal{P}(X)=\mathcal{P}(\emptyset)=\{\emptyset\}$. Thus $\mathcal{P}(X)$ has $1=2^0$ elements. Therefore, the result holds for sets of size $0$.
\item[Inductive step:] Fix some natural number $n$ and assume that if $X$ has $n$ elements, we have that $\mathcal{P}(X)$ has $2^n$ elements (this is our inductive hypothesis).

Consider some set $X$ with $n+1$ elements. In particular, suppose $X = \{x_1,x_2,\dots,x_n,x_{n+1}\}$. 
\begin{itemize}
\item Case 1: Consider subsets of $X$, $A \subseteq X$, such that $x_{n+1} \not\in A$. These subsets are precisely the elements of $\mathcal{P}(\{x_1,\dots,x_n\})$. By induction, we have that $\mathcal{P}(\{x_1,\dots,x_n\})$ has size $2^n$ since $\{x_1,\dots,x_n\}$ has size $n$. Thus there are exactly $2^n$ subsets of $X$ that do not include the element $x_{n+1}$.
\item Case 2: Consider subsets of $X$, $A \subseteq X$, such that $x_{n+1} \in A$. Given any such subset $A$, we have that $A-\{x_{n+1}\}$ belongs to $\mathcal{P}(\{x_1,\dots,x_n\})$. Conversely each element $B \in \mathcal{P}(\{x_1,\dots,x_n\})$ yields a subset $A=B \cup \{x_{n+1}\} \subseteq X$ where $x_{n+1} \in A$. Again, by induction, we know $\mathcal{P}(\{x_1,\dots,x_n\})$ has exactly $2^n$ elements. Since the subsets of $X$ that contain $x_{n+1}$ are in a one-to-one correspondence with these sets, we must have exactly $2^n$ subsets of $X$ that include the element $x_{n+1}$.
\end{itemize}
Now since every subset of $X$ either includes $x_{n+1}$ or not, these cases account for all subsets of $X$. Also, there is no overlap between these cases (a set cannot both contain $x_{n+1}$ and simultaneously not contain $x_{n+1}$). Thus we must have a total of $2^n+2^n=2\cdot 2^n=2^{n+1}$ subsets of $X$. In other words, the size of $\mathcal{P}(X)$ is $2^{n+1}$. Therefore, if our statement is true for $n$, it must also be true for $n+1$.
\end{description}
Therefore, by induction, the result holds for all natural numbers $n$.
\eproof




\end{document}