
\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}
