        \problemdata       % Takes 5 *mandatory* arguments
        {gold-triangles}             % latex-friendly label for the prob.
        {false proof}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut1-1} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}

\medskip
\begin{center}
\large\textbf{Identify where and what the bugs are in each of the following false
proofs.}\end{center}

\problempart\label{millions} Consider the following scheme to make millions.
Obtain a slab of gold $10'' \times 11'' \times 1''$.  Score it diagonally
as shown in Figure~\ref{fig:millions}.  Then cut out two little
one-inch triangles at the corners as shown in the figure.  These
triangles are the profit.  Finally, slide the two slabs together again and
note that the rectangle is now $11'' \times 10'' \times 1''$---the same
size as it was before we removed the small triangles.  By repeating the
process, we can produce an unlimited supply of gold!

\solution{The picture makes the little triangles look like right
  triangles, but they aren't.  So when the two large pieces left after
  the little triangles are removed are slid together, they do not form
  a rectangle, which means the resulting shape is not the same as the
  original figure. (This illustrates why ``proof by diagram'' is
  mathematically suspicious.)}

\begin{figure}[ht]
\centerline{\includegraphics{figures/profitability.jpg}}
\caption{Get Rich!}
\label{fig:millions}
\end{figure}

\problempart
\begin{eqnarray*}
1 & = & \sqrt{1} \\
& = & \sqrt{(-1)(-1)} \\
& = & \sqrt{-1} \sqrt{-1} \\
& = & \sqrt{-1}^2 \\
& = & -1.
\end{eqnarray*}
So, $1 = -1.$

\solution{The assumption that $\sqrt{uv}=\sqrt{u}\sqrt{v}$ arises from
our ``common usage'' of $\sqrt{\cdot}$ to be the {\em positive} square
root.  But this isn't defined for the sqrt of a negative number
(which is complex, so not positive or negative).}

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

\solution{We prove that $\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).
\[\sqrt[n]{2} = \frac{a}{b} \] 
\[ 2 = \frac{a^{n}}{b^{n}} \]
\[ 2b^{n} = a^{n} \]

This means that $a^{n}$ is even, implying that $a$ is even.
As $a$ is even, $a$ = 2$c$ for some integer $c$. Thus, 
\[ 2b^{n} = 2^{n}c^{n} \]  
\[ b^{n} = 2^{n-1}c^{n} \]
This means that $b^{n}$ is even, implying that $b$ must be even as well. \\
Thus, the fraction, $\frac{a}{b}$ was not in its lowest terms. \\
This gives us our contradiction. Our original hypothesis, that $\sqrt[n]{2}$ is irrational, is true. 
}

\problempart \begin{claim*} If $a$ and $b$ are two equal real numbers, then
$a=0$.
\end{claim*}
\begin{falseproof}
\begin{eqnarray}
a&=&b \\
a^2&=&ab \\
a^2-b^2&=&ab-b^2 \\
(a-b)(a+b)&=&(a-b)b \label{cancel}\\
a+b&=&b \label{bug}\\
a&=&0.
\end{eqnarray}
\end{falseproof}

\solution{The bug is at line~(\ref{bug}): one cannot cancel $(a-b)$ from
both sides of equation line~(\ref{cancel}) because $a-b = 0$. }

\problempart\label{cents}
You are richer than you think:
\[1 \cent = \$0.01 = (\$0.1)^2 = (10\cent)^2 = \$1.\]

\solution{$\$0.01 = \$(0.1)^2 \neq (\$0.1)^2$ because the units $\$^2$ and
$\$$ don't match (just as in physics the difference between $sec^2$ and
$sec$ indicates the difference between acceleration and velocity).}


\problempart
\begin{claim*}
Every polynomial $p(x) = ax^2 + bx +c$ over $\complex$
(the complex numbers) has two roots.
\end{claim*}

Sounds good, but the claim is false.  Find the counterexamples and the
bugs in the following proof.  Then restate the claim so it is correct.

\begin{proof}
Using the usual formulas for the roots of a quadratic, let
\begin{eqnarray*}
r_1 & ::= & \frac{-b + \sqrt{D}}{2a}, \mbox{ and} \\
r_2 & ::= & \frac{-b - \sqrt{D}}{2a}, \mbox{ where}\\
D & ::= & b^2-4ac.
\end{eqnarray*}
Simple algebraic calculation confirms that $p(r_1) = 0$ and $p(r_2)=0$, so
$r_1$ and $r_2$ are the two required roots.

\end{proof}

\solution{The polynomial $0x^2 + 0x + 1$ has no roots.  The proof failed
for this case since it divides by $a$, which is unsound when $a=0$.

The polynomial $x^2 + 2x + 1$ has only one root.  For $a\neq 0$, the
algebra is ok, but the proof assumes that $r_1 \neq r_2$, which will be
false when $D = 0$.

The proof is correct for polynomials with $a\neq 0 \neq D$ (even
though when $D < 0$, the meaning of $\sqrt{D}$ is ambiguous as we saw
in lecture). So these two conditions are required to make the claim
correct.
}

\problempart Prof. Meyer announces that he plans to give a surprise 6.042 quiz
next week.  His students wonder if he can give the exam Friday of next
week.  They realize that he obviously cannot, because if he hadn't given
it before Friday, everyone would know that he had only Friday left on
which to give it, so it wouldn't be a surprise any more.

So they ask whether he could he give it Thursday?  They observe that if he
hadn't given it \emph{before} Thursday, he would have to give it \emph{on}
the Thursday, since they already know he can't give it Friday.  But having
figured that out, it wouldn't be a surprise if he gave it on Thursday
either.  Similarly, they reason that he can't give it Wednesday, Tuesday,
or Monday.  Namely, it's impossible for him to give a surprise quiz next
week, and all the students conclude they can relax knowing that
Prof. Meyer must have been bluffing.

And since no one expects the quiz, that's why, when Prof. Meyer gives it
on Tuesday next week, it really is a surprise!

\solution{The basic problem is that ``surprise'' is not a mathematical
concept, nor is there any 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.  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. \emph{The surprise examination or unexpected hanging paradox}, American
Math. Monthly (January 1998), pp.41--51.}


\problempart Let $\text{ND}_{14}$ be the set of natural numbers that cannot be
defined in fewer than fourteen English words.  $\text{ND}_{14}$ must be
infinite because there are only a finite number of fourteen word English
definitions.  Let $m$ be the smallest integer in $\text{ND}_{14}$.  But
``The smallest nonnegative integer which cannot be defined in fewer than
fourteen words,'' is a thirteen word definition in English of $m$,
contradicting the fact that $m \in \text{ND}_{14}$.  Hence
$\text{ND}_{14}$ is an infinite set of natural numbers that has no
smallest element.

\solution{Like ``surprise'' in the previous problem, ``English'' is not
a mathematical concept, and ``English definition'' even less so.  So
$\text{ND}_{14}$ is not mathematically defined, and there's no way to
determine, mathematically, what's true of it.}

\problempart A more serious version of the above is \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 apddition, 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.}



\medskip
Problems 2, 5, and 6 \remove{~\ref{log10}, ~\ref{cents},
and~\ref{millions}} are from Stueben Michael and Diane
Sandford. \emph{Twenty Years Before the Blackboard}, Math. Assoc America,
\copyright 1998, p.27.

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