\input{18.100C.macros}
\thispagestyle{empty}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\oddsidemargin 0in
\evensidemargin 0in
\topmargin -0.75in
\begin{document}
\centerline{\large 18.100C: Spring 2010}
\bigskip
\centerline{\large Recitation Worksheet: Proof by Contradiction}
\medskip
\centerline{February 17, 2010}
\bigskip
\begin{changemargin}{-.35cm}{0cm}
Following are three theorems, each given with a proof that is constructed as a proof by contradiction. In each case, decide whether the proof structure can be changed to omit the contradiction. For those you feel can be proved with a direct argument avoiding contradiction, construct such a proof.
\bigskip
\noindent {\bf Theorem 1.} Let $(X,d)$ be a metric space, and let $E\subseteq X$. If $x$ is a limit point of $E$, then in any neighbourhood $N$ of $x$ there are infinitely many points from $E$.
\medskip
\noindent {\em Proof:} Assume, for a contradiction, that there exists an $r>0$ such that the neighbourhood $B_r(x)$ contains only finitely many points from $E$. Thus $B_r(x)$ contains only finitely many points $e_1,\ldots,e_n$ in $E-\{x\}$. The number $s=\min\{r,d(e_1,x),\ldots,d(e_n,x)\}$ is strictly positive. Note that $e_j\notin B_s(x)$ for any $j\in\{1,\ldots,n\}$ since $d(x,e_j)\ge s$ for each such $j$. Also, as $s\le r$, we have $B_s(x)\subseteq B_r(x)$; since $e_1,\ldots, e_n$ are the only points in $B_r(x)\cap (E-\{x\})$, we have shown that $B_s(x)\cap(E-\{x\})$ is empty. Hence, $B_s(x)$ is a neighbourhood of $x$ that contains no points of $E-\{x\}$. But $x$ is a limit point of $E$, so no such neighbourhood can exist.
\hfill $\square$
\bigskip
\noindent {\bf Theorem 2.} There exists a subset $E$ of $\mathbb{R}$ such that $\overline{E} = \mathbb{R}$ but $\displaystyle{\mathop{E}^{\;\circ}}=\emptyset$.
\medskip
\noindent {\em Proof:} We suppose, for a contradiction, that no such set $E$ exists. Consider the rational number $\mathbb{Q}$. For any $x\in\R$, and any $r>0$, there is a rational number $q\in(x,x+r)$ since $\mathbb{Q}$ is dense in $\R$. Thus, every neighbourhood $B_r(x)$ contains elements from $\mathbb{Q}$, which shows that $x$ is a limit point of $\mathbb{Q}$. Since this is true for every real number $x$, it follows that $\overline{\mathbb{Q}}=\mathbb{R}$.
On the other hand, fix any $q\in\mathbb{Q}$ and any $r>0$. There is an irrational number between $q$ and $q+r$: if $r$ is irrational, then $q+r/2$ is such a number; if $r$ is rational and $r=m/n$ with $m,n\in\N$ then $q+\sqrt{m^2+1}/2n$ is such a number. Hence, the ball $B_r(q)$ is not contained in $\Q$. Since this is true for any $r>0$, there is no neighbourhood of $q$ contained in $\Q$, which means that $q$ is not interior to $\Q$. Since this holds for every $q\in\Q$, it follows that the interior of $\Q$ is empty.
Thus, there exists a set (namely $E=\Q$) in $\R$ whose closure is $\R$ but whose interior is empty. This contradicts the assumption that no such $E$ exists.
\hfill $\square$
\bigskip
\noindent {\bf Theorem 3.} Let $A$ be any set, and let $\mathscr{P}(A)$ denote the {\em power set} of $A$, the set of all subsets of $A$: $\mathscr{P}(A) = \{E\,;\,E\subseteq A\}$. There exists no surjection from $A$ onto $\mathscr{P}(A)$.
\medskip
\noindent {\em Proof:} Suppose, for a contradiction, that such a surjection $f\colon A\to\mathscr{P}(A)$ exists. Consider the subset $B\in\mathscr{P}(A)$ defined by $B=\{a\in A\,;\, a\notin f(a)\}$. We will demonstrate that, in fact, $B$ is not in the image of $f$, contradicting the assumption that $f$ is surjective.
Suppose, for a contradiction, that there exists some $x\in A$ for which $f(x)=B$. If $x\in B$, then by the definition of $B$, $x\notin f(x)$; but $f(x)=B$, and so this implies that $x\notin B$, contradicting the assumption that $x\in B$. Hence, we conclude that $x\notin B$, which means that $x\in f(x)$. But $f(x)=B$, so $x\in B$, contradicting the assumption that $x\notin B$. So the assumption that there is an $x$ for which $f(x)=B$ must be false. It follows that $B$ is not in the image of $f$. Therefore, the original assumption that a surjection $A\to \mathscr{P}(A)$ exists must be false.
\hfill $\square$
\end{changemargin}
\end{document}