\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\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 3 \hfill 21-127 Concepts of Math \hfill due 09.20.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}[Spoof Me Once, Shame On You. Spoof Me Infinitely Many Times \ldots (10 pts)]
Consider the (false!) claim that
\[ \bigcup_{n\in\mathbb{N}} \mathcal{P}([n]) = \mathcal{P}(\mathbb{N}) \]
\begin{enumerate}[{\bf\color{blue}(a)}]
\item What is wrong with the following ``proof'' of the claim? Point out any error(s) and explain why it/they ruin the ``proof''.
\begin{quote}
First, we will show that
\[ \bigcup_{n\in\mathbb{N}}\mathcal{P}([n])\subseteq \mathcal{P}(\mathbb{N}) \]
Consider an arbitrary element $X$ of the union on the left.\vspace{0.2cm}\\
By the definition of an indexed union, we know there exists some $k\in\mathbb{N}$ such that $X\subseteq[k]$.\vspace{0.2cm}\\
Since $[k]\subseteq\mathbb{N}$, and $X\subseteq[k]$, we deduce that $X\subseteq\mathbb{N}$.\vspace{0.2cm}\\
Thus, $X\in\mathcal{P}(\mathbb{N})$.\vspace{0.2cm}\\
Second, we will prove the ``$\subseteq$'' relationship holds in the other direction, as well.\vspace{0.2cm}\\
Consider an arbitrary $Y\subseteq\mathbb{N}$.\vspace{0.2cm}\\
By the definition of subset, and the fact that $Y$ is a set of natural numbers, we know there exists some $\ell\in\mathbb{N}$ such that $Y\subseteq[\ell]$.\vspace{0.2cm}\\
By the definition of an indexed union, then, we know that $\displaystyle{Y\in\bigcup_{n\in\mathbb{N}}\mathcal{P}([n])}$.\vspace{0.2cm}\\
Since we have shown $\subseteq$ and $\supseteq$, we know the two sets are equal.
\end{quote}
\item Disprove the claim by defining an {\bf explicit} example of a set $S$ such that
\[ S\in\mathcal{P}(\mathbb{N}) \qquad\text{ and }\qquad S\notin\bigcup_{n\in\mathbb{N}}\mathcal{P}([n])\]
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Are All Sets Created Equal? (15 pts)]
Let $A=[3]\times[4]$. \qquad (Remember that $[n]=\{1,2,3,\dots,n\}$.)\vspace{0.2cm}\\
Let $B=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}\mid 0\leq 3x-y+1\leq 9\}$.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item {\bf Prove} that $A\subseteq B$.
\item Is it true that $A=B$? Why or why not? {\bf Prove} your claim.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[You've Got The Power Sets (25 pts)]
Suppose $A$ and $B$ are sets.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item {\bf Prove} that
\[ \mathcal{P}(A)\cup\mathcal{P}(B)\subseteq\mathcal{P}(A\cup B)\]
\item Provide an {\bf explicit} example of $A$ and $B$ where the inequality in {\bf\color{blue}{(a)}} is {\bf strict}.
\item {\bf Prove} that
\[ \mathcal{P}(A\cap B)\supseteq\mathcal{P}(A)\cap\mathcal{P}(B) \]
Then, cite something we proved in lecture to decide whether or not ``$=$'' holds in the line above.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Subsettle Down (15 pts)]
Let $S$ and $T$ be sets whose elements are sets, themselves. Suppose that $S\subseteq T$.\vspace{0.2cm}\\
{\bf Prove} that
\[ \bigcup_{X\in S}X\subseteq \bigcup_{Y\in T} Y \]
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Don't Get Cross (20 pts)]
Let $A,B,C,D$ be sets.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item {\bf Prove} that
\[ (A\times B)\cup(C\times D)\subseteq (A\cup C)\times(B\cup D)\]
\item Provide an {\bf explicit} example of $A,B,C,D$ where the inequality in {\bf\color{blue}{(a)}} is {\bf strict}.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[What's $\mathbb{Z}$ Point Of This Problem? (15 pts)]
In this problem, we are going to ``prove'' the existence of the negative integers! I say ``prove'' because we won't really understand what we've done until later but, trust me, it's what we're doing.\vspace{0.2cm}\\
Because of this goal, you cannot {\bf assume} any integers strictly less than 0 exist, so your algebraic steps, especially in part {\bf\color{blue}(d)}, should not involve any terms that might be negative.\vspace{0.2cm}\\
That is, if you consider an equation like
\[ x+y=x+z \]
we {\bf can} deduce that $y=z$, by subtracting $x$ from both sides, since $x-x=0$.\vspace{0.2cm}\\
However, if we consider an equation like
\[ x+y=z+w\]
we {\bf cannot} deduce that $x-z=w-y$. Perhaps $y>w$, so $w-y$ does not exist in our context \ldots\vspace{0.2cm}\\
Be sure to ask questions if you want any clarification about this. Okay, on to the problem!\vspace{0.5cm}\\
Let $P=\mathbb{N}\times\mathbb{N}$. Define the set $R$ by
\[ R = \{((a,b),(c,d))\in P\times P\mid a+d=b+c\} \]
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Find three different pairs $(c,d)$ such that $((1,4),(c,d))\in R$.
\item Let $(a,b)\in P$. Prove that $((a,b),(a,b))\in R$.
\item Let $((a,b),(c,d))\in R$. Prove that $((c,d),(a,b))\in R$, as well.
\item Assume $((a,b),(c,d))\in R$ and $((c,d),(e,f))\in R$. Prove that $((a,b),(e,f))\in R$, as well.
\end{enumerate}
\vspace{0.2cm}

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