\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{1W}			% !! start the paper

\begin{problem}
Generalize the proof from lecture\footnote{See attached.  This one
not a false proof.} that $\sqrt{2}$ is irrational, \eg how about
$\sqrt[3]{2}$?

\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
exists 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, a
contradicting the fact that $m/n$ is in lowest terms.

\medskip
Now we justify the claim that if $m^k$ is even, so is $m$.  The original
argument that $\sqrt{2}$ is irrational (repeated on the last page of this
handout) key used the special case that if the square of an integer is
even, then the integer itself is even.  There's a simple proof by
contradiction of this fact, suppose $m$ was not even.  Then $m$ is odd, so
$m^2$ would also be odd---using the familiar fact that an odd number times
an odd number is odd---contradicting the fact that $m^2$ is even.

But more generally, if $m^k$ is divisible by a prime number, $p$, for any
integer $k>0$, then $m$ must be divisible by $p$.  This follows from the
factorization of an integer into primes: 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$.}
\end{problem}

\iffalse

\problem\label{2=1}
\[ x^2 = \overbrace{x + x + \ldots + x}^x\]
Differentiating both sides with respect to $x$, we get
\[ 2x =  \overbrace{1 + 1 + \ldots + 1}^x = x\]
So letting $x=$, we conclude that $2=1$.

\solution{The function
\[f(x) = \overbrace{x + x + \ldots + x}^x\]
is defined only for nonnegative integers $x$. 
It is defined only on discrete points and is not continuous. 
Hence its derivative does not make sense.
}
\fi

\begin{problem}
Albert \& Radhi 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 \& Radhi 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 \& Radhi to give a surprise quiz next
week.  All the students now relax having concluded that Albert \& Radhi
must have been bluffing.

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

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

\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, whatever that is, and the paradox is that these axioms are
inconsistent.  But that's no surprise \texttt{:-)}, since 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}

\iffalse

\problem \emph{Russell's paradox}:

Let $S$ be a variable ranging over all sets, and define
\[W \eqdef \set{S \mid S \not\in S}.\]
So by definition,
\[S \in W  \mbox{  iff  } S \not\in S,\]
for every set $S$.  In particular, we can let $S$ be $W$, and obtain
the contradictory result that
\[W \in W  \mbox{  iff  } W \not\in W.\]

\solution{ Bertrand Russell first observed the contradiction above at
the turn of the Twentieth Century.  It demonstrated that the initial
effort to axiomatize set theory by the German logician Frege was deeply
flawed.  (Russell won two Nobel prizes: one for Literature and the other
for Peace, even though his ``real'' profession was as a Logician and
Philosopher.  He is also credited with the ``I am the Pope'' joke.)

The failure of Frege's axiom system was such an astonishing blow to the
Foundations of Mathematics, that Russell and Whitehead immediately went to
work and spent a dozen years developing a new axiom system in a huge
monograph called \emph{Principia Mathematica}.  The Russell-Whitehead
system was a much more technical "typed" set theory compared to Frege's,
according to which a set, $S$, can be a member of set, $T$, only if $S$
has "lower" type than $T$.  In particular $S \not\in S$.

\iffalse More generally, can't have ``infinite
descending membership chain:''
\[
\dots x_n \in x_{n-1} \in \dots \in x_2 \in x_1.
\]
\fi

Modern set theory no longer makes explicit use of types, and much of it
looks like Frege's original theory.  But it still avoids paradoxes like
Russell's with axioms specifying that sets must built up from ``simpler''
sets in certain standard ways, and in particular, it remains the case that
no set can be a member of itself.

In addition, there are certain collections of mathematical objects that
are recognized to be mathematically well-defined but are \emph{not
considered to be sets}.  These collections are called ``classes.''
Classes can be thought of intuitively as things that are ``too big'' to be
a member of anything---not even another class.  A basic example is the
collection of all sets; it is class but not a set.

So what is the modern resolution of Russell's paradox?  Well, note that
since $S \not \in S$ for all sets $S$, it follows that $W$, defined above,
contains every set.  In other words, $W$ equals the class of all sets.  So
the step in the proof above where we let $S$ be $W$ is invalid, because
$S$ ranges over sets, and $W$ is not a set.

These issues rarely come up in mainstream Mathematics.  And they don't
come up at all in Computer Science, where the focus is generally on
``countable,'' and often just finite, sets.  In practice, only Logicians
and Set Theorists worry about collections that are too big to be sets.}
\fi

\newpage

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

Remember that an irrational number is a number that can not be
expressed as a ratio of two integers.

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