\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\st}{{\text{\huge {.}}}\;}
\newcommand{\vsp}{\vspace{0.2cm}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 8 \hfill 21-127 Concepts of Math \hfill due 11.08.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Andrew ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
\begin{problem}[You Can (Un)Count on Me (10 pts)]
Find the flaw in the following ``spoof'' that $\R$ is countably infinite:
\begin{quote}
Let $S\subseteq\R$ be the set defined by $S=\{y\in\R\mid 0\leq y<1\}$.\vspace{0.2cm}\\
For every $x\in S$, define the set $A_x=\{x+z\mid z\in\mathbb{Z}\}$.\vspace{0.2cm}\\
(For example, $A_{1/2}=\{\dots,-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2},\dots\}$.)\vspace{0.2cm}\\
Since $\mathbb{Z}$ is countably infinite, each set $A_x$ is countably infinite, as well.\vspace{0.2cm}\\
Also, notice that
\[ \R =\bigcup_{x\in S} A_x \]
This is a union of countably infinite sets, so $\R$ is also countably infinite.
\end{quote}
Be sure to point out any particular step that is incorrect, as well as {\it why} that step is incorrect. Ideally, you should point out why the ultimate conclusion of the spoof is incorrect, but without just explicitly stating ``$\R$ is uncountable because we proved that''. {\it Why} is the incorrect step a misuse of a result, {\it and} why is the conclusion of that particular step invalid?
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Possible or Possi-bull? (20 pts)]
For each of the following desired situations, provide an example or state that it is impossible.\vsp\\
For example, if the situation were ``Finite sets $A$ and $B$ such that $A\cup B$ has size 4'', an answer might be ``Consider $A=\{1,2\}$ and $B=\{3,4\}$.'' If the situation were, ``For every $x\in\N$, an infinite set $S_x$, such that $\displaystyle{\bigcup_{x\in\N}S_x}$ is finite'', the answer would be ``Impossible''.\vsp\\
There is no need to {\it prove} your answers here; a good example should suffice. However, any explanation you provide, in addition to the example/statement, would be helpful in (potentially) assigning partial credit.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item An uncountably infinite set $A$ and a countably infinite set $B$ such that $A\cap B$ is finite.
\item Uncountably infinite sets $C$ and $D$ such that $C-D$ is countably infinite.
\item Uncountably infinite sets $E$ and $F$ such that $E-F$ is uncountably infinite.
\item For every $x\in\N$, a countably infinite set $S_x$, such that $\displaystyle{\bigcup_{x\in\N}S_x}$ is uncountably infinite.
\item For every $y\in\R$, a countably infinite set $T_y$, such that $\displaystyle{\bigcup_{y\in\R}T_y}$ is countably infinite.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[$\Q$ and $\bigcup$ (20 pts)]
In lecture, we explained that $\Q$ is countably infinite by relating it to a finite union of countably infinite sets. Specifically, we talked about how there is a relationship between $\N\times\N$ and the positive rationals, as well as $\N\times\N$ and the negative rationals.\vsp\\
In this problem, you should provide an alternate proof that $\Q$ is countably infinite. Specifically, you should express $\Q$ as a {\bf countably infinite union of sets that are pairwise disjoint.}\vsp\\
There are many ways to do this. Whatever your method is, though, you should be be able to explain a few things: {\bf\color{blue}(a)} why the union of your chosen sets is $\Q$, {\bf\color{blue}(b)} why all of those sets are finite or countably infinite (depending on your choice), {\bf\color{blue}(c)} why those sets are pairwise disjoint, and {\bf\color{blue}(d)} why any relevant Theorems given in class apply to guarantee that $\Q$ is countably infinite because of this.\vsp\\
({\bf\color{blue}Bonus} points if all of your sets in the union are finite!)
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[I Think I Am Finite, Therefore I Am Finite (Cogito Ergo Product) (25 pts)]
In this problem, you will prove that whenever $A$ and $B$ are finite with $|A|=a$ and $|B|=b$, it follows that $|A\times B|=ab$. This will be structured as a ``double induction'' proof on the two variables $a,b\in\N$.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Show that $\bigl|\,[1]\times[1]\,\bigr|=1$. (This is very, very easy, but necessary.)
\item Suppose $n\in\N$ and $\bigl|\,[1]\times[n]\,\bigr|=n$. Show that $\bigl|\,[1]\times[n+1]\,\bigr|=n+1$.
\item Explain why {\bf\color{blue}(a)} and {\bf\color{blue}(b)} have shown that $\forall n\in\N\st \bigl|\,[1]\times[n]\,\bigr|=n$.
\item Suppose $k\in\N$ and suppose $\forall n\in\N\st\bigl|\,[k]\times[n]\,\bigr|=kn$. Show that $\bigl|\,[k+1]\times[n]\,\bigr|=(k+1)n$.
\item Explain why {\bf\color{blue}(c)} and {\bf\color{blue}(d)} have show that $\forall k,n\in\N\st\bigl|\,[k]\times[n]\,\bigr|=kn$.
\item {\bf\color{blue}[Bonus!]} Explain why {\bf\color{blue}(e)} proves the result stated in the problem description above.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[$f$u$\N$ctio$\N$ Ju$\N$ctio$\N$ (25 pts)]
For each of the following sets, you are given its cardinality. Prove that the given cardinality is correct by finding a bijection to a relevant set and/or citing a result.\vsp\\
({\bf Hint:} If you don't use some kind of inductive argument, your proof might not be rigorous enough \ldots)
\begin{enumerate}[{\bf\color{blue}(a)}]
\item $A$ is the set of all functions from $\N$ to $\N$. Show that $A$ is uncountably infinite.\vspace{0.2cm}\\
({\bf Hint:} Compare $A$ with the set $S$ of all functions from $\N$ to $\{1,2\}$. Can you explain why $S$ is uncountably infinite? What does this say about $A$? \ldots)
\item $B$ is the set of all functions from $\N$ to $\N$ with the additional property that
\[ \forall x\in\N\st f(x+1)=f(x)+1 \]
Show that $B$ is countably infinite.
\item $C$ is the set of all functions from $\N$ to $\N$ with the additional properties that
\begin{align*}
\forall x\in\N\st f(x+1)&=f(x)+1\\
f(1)&=42
\end{align*}
Show that $C$ is finite, and has only one element.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\end{document}