\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

\handout{mistakes}{Common Errors on Problem Sets}{October 15, 1998}

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

\begin{problems}

\problem Write the statement ``$n$ is prime'' in propositional form.
Let the universe of discourse be the natural numbers $N$.

Incorrect answer:

$(n>1) \wedge (\forall x: (\neg (x = 1) \wedge \neg (x = n)) 
\wedge (n/x 	\not\in N))$

The problem is in the long chain of
ANDs.  The last AND should be swapped for an IMPLIES.
As it stands, this proposition is satisfied for NO number $n \in N$. 
One of the things it says is $\forall x: \neg(x=1)$.  There is,
however, a value of $x$ for which $(x=1)$, namely, $1$.  
Students often mistakenly swap $\rightarrow$ and $\wedge$.  

The following is a correct answer:

$(n>1) \wedge (\forall x: (\neg (x = 1) \wedge \neg (x = n))
\rightarrow (n/x \not\in N))$

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

\problem Write the statement ``There is a deceitful person who
did not give gifts to anyone''.  Let the universe of discourse be
all people.  Let $D(x)$ be true iff $x$ is deceitful.  Let
$G(x,y)$ be true iff $x$ gave a gift to $y$.  

Incorrect answer:

$\exists x \neg \exists y : (D(x) \wedge G(x,y))$

The problem is that the statement does not
say that such a person exists.  Suppose everyone in the world
gave a gift to someone, and at least one person, call her $z$, is
not deceitful.  Then the statement ``There is a deceitful
person who did not give gifts to anyone'' is certainly not true.
There does exist an $x$, however, for which there is no person
$y$ for which $x$ is deceitful and generous.  If $x=z$, then 
there is no $y$ for which $D(x)$ holds.  The problem arises when
placing statements, such as $D(x)$ inside a $\exists$ or $\forall$
with which they have nothing to do(i.e. $\exists y: D(x)$.  

Another incorrect answer:

$\exists x : (D(x) \rightarrow \neg \exists y : G(x,y))$

The problem here is once again the swapping of $\rightarrow$ and
$\wedge$.  If $D(x)$ is not satisfied, then you have the case of
false implies anything.  Once again, if $x=z$, the rest of
the statement holds, but there is no deceitful person
who was unkind to everyone.

The following is a correct answer:

$\exists x : (D(x) \wedge \neg \exists y : G(x,y))$

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

\problem A real number $r$ is called {\em sensible} if there exist
positive integers $a$ and $b$ such that $\sqrt{a / b} = r$.  For
example, setting $a = 2$ and $b = 1$ shows that $\sqrt{2}$ is 
sensible.  Prove that $\sqrt[3]{2}$ is not sensible.  (Consider only
positive real roots in this problem.)

Incorrect proof:

\begin{proof}
The proof is by contradiction.  Assume for the purpose of contradiction
that $\sqrt[3]{2}$ is sensible.  Then there exist positive integers
$a$ and $b$ such that $\sqrt{a / b} = \sqrt[3]{2}$.  Squaring both
sides of this equation gives $a / b = \sqrt[3]{4}$.  This can
be rewritten as $a = b \cdot \sqrt[3]{4}$.  Because $\sqrt[3]{4}$ is
not an integer, at least one of $a$ and $b$ is not an integer,
which leads to a contradiction.
\end {proof}

The error is in the last sentence.  It states that multiplying an
integer by a non-integer yields a non-integer.
 This is incorrect.  Consider the following
values for $a$, $b$, and $c$.\\
$a=2$, $b=5$, $c=2/5$\\ 
$(2 = 5 * 2/5) \wedge (2/5 \not\in Z)$, but $2$ and $5$ are both
integers.

A correct proof should show that $\sqrt[3]{4}$ is not rational
in order to reach a contradiction.

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

\problem Use induction to prove that the following equation holds
for all $n \geq 2$.

\begin{eqnarray*}
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) & = &	\frac{1}{n}
\end{eqnarray*}

\bigskip

\begin{proof}
The proof is by induction on $n$.  In the base case, $P(2)$ is
true because $(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive
step, for $n \geq 2$ assume $P(n)$ to prove $P(n+1)$ as follows.

\begin {eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n+1}\right)
	& = & 	\frac{1}{n+1} \\
P(n) \cdot \left(1 - \frac{1}{n+1}\right)
	& = &	\frac{1}{n+1} \\
\frac{1}{n} \cdot \left(1 - \frac{1}{n+1}\right) 
	& = &	\frac{1}{n+1} \\
\frac{1}{n} \cdot \frac{n}{n+1} 
	& = & 	\frac{1}{n+1} \\
\frac{1}{n+1}
	& = & 	\frac{1}{n+1}
\end{eqnarray*}

This shows that $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.

\end{proof}

There are three problems with this proof.  The first is that
the inductive hypothesis, $P(n)$, was never defined.  Even though it
may seem obvious to you what it is, you should always define it.
The second problem is a misuse of the inductive hypothesis in
the proof.  The proof makes the statement:\\
\begin{eqnarray*}
P(n) \cdot \left(1 - \frac{1}{n+1}\right) 
	& = &	\frac{1}{n+1}
\end{eqnarray*}

The problem here is that the proof uses $P(n)$ to be the expression\\
\begin {eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right)
\end{eqnarray*}

In reality, the proposition $P(n)$ is the entire statement of
equality, namely\\
\begin {eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) & = &	\frac{1}{n}
\end{eqnarray*}

The final problem is the chain of ``equalities''.  The first
equality is $P(n+1)$, which isn't known yet to be true.  The way
to do this correctly is to reverse the equalities to start with
something true and work from there.  

A corrected proof, by reversing the order of the steps follows:


\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above equation holds.  In the base case, $P(2)$ is
true because $(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive
step,for $n \geq 2$ assume $P(n)$ to prove $P(n+1)$ as follows.

\begin {eqnarray*}
\frac{1}{n+1}
	& = &	\frac{1}{n+1} \\
\frac{1}{n} \cdot \frac{n}{n+1}
	& = &	\frac{1}{n+1} \\
\frac{1}{n} \cdot \left(1 - \frac{1}{n+1}\right)
	& = &	\frac{1}{n+1} \\
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n+1}\right)
        & = &   \frac{1}{n+1} \\
\end{eqnarray*}

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved
by induction.

\end{proof}

\end{problems}
\end{document}

