\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{1, Wed.}                    % !! start the paper

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
Generalize the proof from lecture (reproduced below) that $\sqrt{2}$ is
irrational, \eg how about $\sqrt[3]{2}$?  Remember that an irrational
number is a number that cannot be expressed as a ratio of two integers.

\begin{quote}

\begin{theorem*}
$\sqrt{2}$ is an irrational number.
\end{theorem*}

\begin{proof}
The proof is by contradiction.  Assume for purpose of contradiction that
$\sqrt{2}$ is rational.

Then we can write $\sqrt{2} = m/n$ where $m$ and $n$ are integers and the
fraction is in lowest terms.  Squaring both sides gives $2 = m^2 / n^2$,
so $2 n^2 = m^2$.  This implies that $m^2$ is even, and hence that $m$ is
even; that is, $m$ is a multiple of $2$.  But that means $m^2$ is actually
a multiple of 4, say $m^2 = 4k$.

Now we have $2 n^2 = m^2 = 4k$, so $n^2 = 2k$.  So $n^2$ is even, and
hence $n$ is even. But since $m$ and $n$ are both even, the fraction $m/n$
is not in lowest terms, a contradiction.
\end{proof}

\end{quote}

\solution{We prove that for any $n>1$, $\sqrt[n]{2}$ is irrational by
contradiction.

Assume that $\sqrt[n]{2}$ is rational.  Under this assumption, there
exist integers $a$ and $b$ with $\sqrt[n]{2} = a/b$, where $a$
and $b$ have no common factors (so that the fraction $a/b$ is in lowest
terms).  Now we prove that $a$ and $b$ are both even, which contradicts
the existence of $a,b$.
\begin{eqnarray*}
\sqrt[n]{2} & = & \frac{a}{b}\\
2 & = & \frac{a^{n}}{b^{n}}\\
2b^{n} & = & a^{n}.
\end{eqnarray*}
The lefthand side of the last equation is even, so $a^{n}$ is even.  This
implies that $a$ is even as well (see below for justification).

In particular, $a = 2c$ for some integer $c$.  Thus, 
\begin{eqnarray*}
2b^{n} & = & (2c)^n = 2^{n}c^{n},\\
b^{n} & = & 2^{n-1}c^{n}.
\end{eqnarray*}
Since $n-1>0$, the righthand side of the last equation is an even number,
so $b^{n}$ is even.  But this implies that $b$ must be even as well,
contradicting the fact that $m/n$ is in lowest terms.

\medskip
Now we justify the claim that if $a^n$ is even, so is $a$.

There is a simple proof by contradiction: suppose $a$ was not even, \ie
$a$ is odd.  It's a familiar (and easily verified) fact that the product
of \emph{any} number of odd numbers is odd, so $a^n$ would also be odd,
contradicting the fact that $a^n$ is even.

But more generally for \emph{any} integers $m,k >0$, if $m^k$ is divisible
by a prime number, $p$, then $m$ must be divisible by $p$.  This follows
from the factorization of an integer into primes (which we'll discuss
further in a coming lecture): the primes in the factorization of $m^k$ are
precisely the primes in the factorization of $m$ repeated $k$ times, so if
there is a $p$ in the factorization of $m^k$ it must be one of $k$ copies
of a $p$ in the factorization of $m$.

\begin{optional}
%From S99 Tutorial 1 Notes:

Here's a somewhat broader generalization of the proof that $\sqrt{2}$ is
irrational.

\begin{lemma*}
Let the coefficients of the polynomial
$a_0+a_1x+a_2x^2+\cdots + a_{n-1}x^{n-1} + x^n$ be
integers.  Then any real root of the polynomial is either integral or
irrational.
\end{lemma*}

Notice that this Lemma directly implies that $\sqrt{2}$ is irrational:
$x^2 - 2$ has no integer root because 2 is not a perfect square, so the
real roots, namely, $\pm\sqrt{2}$, must be irrational.  Similarly, if $m
\in \naturals$ is not the $k$th power of an integer, then $x^k - m$ has no
integer roots, so $\sqrt[k]{m}$ will be irrational.

\begin{proof}

Let $r\in \reals$ be a root of the polynomial, that is,
\[
a_0+a_1r+a_2r^2+\cdots+  a_{n-1}r^{n-1}+ r^n = 0.
\]
There are three cases for $r$: it is either integral, irrational, or the
ratio of two integers with no common divisors where the denominator is
greater than one.  We want to eliminate the last case.

So assume to the contrary that $r = s/t$ for integers $s$ and $t$ which
have no common divisors and such that $t >1$.  Now $t$ must have a prime
divisor, $p$.

Substituting $s/t$ for $r$ and multiplying both sides of the above
equation by $t^n$ yields:
\begin{eqnarray}
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\cdots+a_{n-1}s^{n-1}t+s^n & = & 0,\\
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^{n-1}t & = & -s^n.\label{e2}
\end{eqnarray}
Then $p$ divides each term of the lefthand side of equation~(\ref{e2}),
and therefore also divides the righthand side, viz., $p \divides -s^n$.
But this means that $p$ must also divide $s$.  So $p$ is a common divisor
of $s$ and $t$, contradicting our choice of $s$ and $t$.

\end{proof}

\end{optional}
}

\end{problem}


\instatements{\newpage}

\begin{problem}  %revised 2/24/04

\begin{proposition*}
Suppose $x$ is a real number and
\begin{equation}\label{eq}
x^2 -2x = -1
\end{equation}
Then $x=1$.
\end{proposition*}

What is wrong with the following proof of this proposition?

\begin{falseproof}
Suppose $x=1$.  Then
\[
x^2 -2x = 1^2 -2\cdot 1 = 1 - 2 = -1,
\]
confirming that equation~(\ref{eq}) holds as claimed.  Therefore, $x =1$.
\end{falseproof}

\solution{This reasoning is circular.  We suppose $x=1$ and then conclude
that $x=1$.  The verification that letting $x=1$ makes equation~(\ref{eq})
true only shows that $x$ \emph{might} equal 1 when~(\ref{eq}) holds, not
that it is \emph{necessarily} is equal to 1.

The Proposition is true of course:~(\ref{eq}) is a quadratic equation
which we can solve to prove that 1 is the only root.

Now if we already knew that there was only one solution, then showing that
1 is a solution would be enough to conclude that $x=1$, and the false
proof could be salvaged.  But in general, quadratic equations have more
than one root, a possibility the false proof ignores.}

\end{problem}


\iffalse  replaced by above 2/24/04

\begin{problem} %S00, ps1.6

\begin{proposition*}
Suppose $x$ is a real number and
\begin{equation}\label{eq}
\frac{2x-5}{x-4}=3.
\end{equation}
Then $x=7$.
\end{proposition*}

What is wrong with the following proof of this proposition?

\begin{falseproof}
Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $(2x-5)/(x-4) = 3$, then $x=7$.
\end{falseproof}

\solution{This proof is a typical example of circular reasoning.  We
suppose $x=7$ and then conclude that $x=7$.

Notice that the proposition is true, as can easily be shown by solving
equation~(\ref{eq}) for $x$.}

\end{problem}
\fi


\instatements{\newpage}
\begin{problem}
Albert \& Eric announce that they plan a surprise 6.042 quiz next week.
Their students wonder if the quiz could be next Friday.  The students
realize that it obviously cannot, because if it hadn't been given before
Friday, everyone would know that there was only Friday left on which to
give it, so it wouldn't be a surprise any more.

So the students ask whether Albert \& Eric could give the surprise quiz
Thursday?  They observe that if the quiz wasn't given \emph{before}
Thursday, it would have to be given \emph{on} the Thursday, since they
already know it can't be given on Friday.  But having figured that out, it
wouldn't be a surprise if the quiz was on Thursday either.  Similarly, the
students reason that the quiz can't be on Wednesday, Tuesday, or Monday.
Namely, it's impossible for Albert \& Eric to give a surprise quiz next
week.  All the students now relax having concluded that Albert \& Eric
must have been bluffing.

And since no one expects the quiz, that's why, when Albert \& Eric give
it on Tuesday next week, it really is a surprise!

What do you think is wrong with the students' reasoning?

\solution{The basic problem is that ``surprise'' is not a mathematical
concept, nor is there any sure, clear way to give it a mathematical
definition.  The ``proof'' above assumes some plausible axioms about
surprise, without defining it.  The paradox is that these axioms are
inconsistent.  But that's no surprise \texttt{:-)}, since---mathematically
speaking---we don't know what we're talking about.

Mathematicians and philosophers have had a lot more to say about what
might be wrong with the students' reasoning, (see Chow, Timothy Y.
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/surprise-paradox.pdf} 
{\emph{The surprise examination or unexpected hanging paradox}}, American
Math. Monthly (January 1998), pp.41--51.)}

\end{problem}


\end{document}
