\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