\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\st}{{\huge\text{.}}\;}
\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 4 \hfill 21-127 Concepts of Math \hfill due 10.04.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}[Proof or Spoof? (10 pts)]
What, if anything, is wrong with the following proof?
\begin{quote}
Let $A$ and $B$ be any two subsets of a set $U$. We claim
\[ (A\cup B)-(A\cap B)\subseteq (A-B)\cup(B-A) \]
We will prove this by contrapositive, so we want to show, for every $x\in U$, that
\[ x\notin (A-B)\cup(B-A) \implies x\notin (A\cup B)-(A\cap B) \]
AFSOC that $x\in (A-B)\cup(B-A)$. Then
\[ (x\in A\wedge x\notin B) \vee (x\in B\wedge x\notin A) \]
so we have two cases.\vspace{0.2cm}\\
{\bf Case 1:} If $x\in A\wedge x\notin B$ then certainly $x\in A\cup B$ and $x\notin A\cap B$.\vspace{0.2cm}\\
{\bf Case 2:} If $x\in B\wedge x\notin A$ then certainly $x\in A\cup B$ and $x\notin A\cap B$.\vspace{0.2cm}\\
Thus, $x\in(A\cup B)-(A\cap B)$, since this holds in either case. This is a contradiction.\vspace{0.2cm}\\
Therefore, the conclusion follows.
\end{quote}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Stay Positive (Well, Non-Negative) (20 pts)]
Define $P=\{y\in\mathbb{R}\mid y>0\}$ to be the set of positive real numbers.\vspace{0.2cm}\\
Prove that
\[ \forall x\in\mathbb{R}\st \left[\left(\forall y\in P\st x\geq -y\right)\implies x\geq 0\right]\]
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Everybody To The Limit (20 pts)]
Define $P=\{y\in\mathbb{R}\mid y>0\}$ to be the set of positive real numbers.\vspace{0.2cm}\\
Prove that
\[ \forall\varepsilon\in P\st \exists L\in\mathbb{R}\st \forall n\in\mathbb{N}\st\left( n\geq L \implies \left|\frac{(-1)^n}{n^2}\right|<\varepsilon\right)\]
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Well, I Order You To Prove The Well-Ordering! (30 pts)]
In this problem, you will prove the fantastically useful {\bf Well-Ordering Principle} of the natural numbers. The {\bf WOP} claims that
\[ \forall S\subseteq\mathbb{N}\st \left[S\neq\varnothing \implies \left(\exists \ell\in S \st (\forall x\in S\st \ell\leq x)\right)\right] \]
That is, every non-empty set of natural numbers has a {\bf least element}.\vspace{0.2cm}\\
You will prove this claim by induction on whether or not a given set $S$ contains $n$ as an element.\vspace{0.2cm}\\
We will start the proof for you, and then guide you through the rest:\vspace{0.5cm}\\Let $S\subseteq\mathbb{N}$ be arbitrary and fixed. For every $n\in\mathbb{N}$, define $P(n)$ to be the proposition
\[\text{``}\;\; n\in S\implies \left[\exists \ell\in S \st (\forall x\in S\st \ell\leq x)\right] \;\;\text{''}\]
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Prove that $P(1)$ holds.\qquad (Hint: What's the smallest natural number?)
\item Let $k\in\mathbb{N}$ be arbitrary and fixed. Write down, using logical notation, a hypothesis which asserts that $P(i)$ holds true for every $i$ between $1$ and $k$ (inclusive).\vspace{0.2cm}\\(Hint: This should be easy; just write an ``and'' statement. Think about what it means.)\vspace{0.5cm}\\
Next, suppose $k+1\in S$. Define $T=S-\{k+1\}$. There are three cases:
\item Consider the case that $T=\varnothing$. Prove that $S$ has a least element.
\item Consider the case that $T\neq\varnothing$ and $\forall x\in S\st x\geq k+1$. Prove that $S$ has a least element.
\item Consider the case that $T\neq\varnothing$ and $\exists x\in S\st x<k+1$. Prove that $S$ has a least element.\vspace{0.2cm}\\
(Hint: {\it Here} is where you will need to use an assumption from {\bf\color{blue}(b)}, one of the induction hypotheses!)\vspace{0.5cm}\\
Since $S$ has a least element in every case, we deduce that $P(k+1)$ holds. By induction, $\forall n\in\mathbb{N}\st P(n)$.
\item Let's show why this proof actually worked! Consider an arbitrary $S\subseteq\mathbb{N}$ such that $S\neq \varnothing$. How do we know $S$ has a least element? That is, which {\bf instance} of the claim $P(n)$ is guaranteed to hold?\vspace{0.2cm}\\
(Hint: This would fail if $S=\varnothing$ \ldots)
\item {[\bf\color{blue}Bonus]} Why didn't we just induct on the size of the set $S$? Why would that not prove {\bf WOP}?
\end{enumerate}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Party People (20 pts)]
Suppose that there are $n$ Concepts students at a homework party, and $n\geq 2$. Assume that every two people are either friends or not friends. (That is, there's no such thing as mere acquaintances or frenemies or anything like that, just two possiblities. Also, you can't be friends with yourself. Sorry.)\vspace{0.2cm}\\
Prove (by contradiction!) that there exist two people at the party with the same number of friends.
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Challenge: Primes and Irrationals (0 pts)]
From now on, I'll be providing a {\bf Challenge Problem} at the end of each homework. It's not worth any credit, so don't worry about it either way. However, I think the problems will present some interesting mathematics that is related to the course content, will give you something extra to think about and mull over, and will likely help you solidify the concepts from the course as you apply them to other settings. Feel free to speak with me about these problems outside of class and during office hours!\vspace{0.3cm}\\
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Let $p\in\mathbb{N}$ be a prime number. Prove that $\sqrt{p}$ is irrational.
\item Prove that $\sqrt{2}\cdot\sqrt{3}$ is irrational.
\item Prove that $\sqrt{2}+\sqrt{3}$ is irrational.\vspace{0.2cm}\\
These last two parts show that the set of irrationals is {\bf not closed} under the standard arithmetic operations, $\cdot$ and $+$\;.
\end{enumerate}
\vspace{0.2cm}

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