\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}

\newtheorem{mytheorem}{Theorem}
\newtheorem{myfalsetheorem}[mytheorem]{False Theorem}

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\begin{document}

\tutprobn{2}{Thursday, 9/16/99}{September 15, 1999}

\begin{problems}

\problem We ask you to construct some logical formulas using only
propositional formulas and quantification of variables which range over just
one domain of discourse, starting from formulas only of the forms $x=y$
and $P(x,y)$.  Here $x$ and $y$ may be replaced by any variables, but
$P$ is a fixed symbol.

For example, say an element $x$ is ``OK'' if $P(x,x)$ holds.
To say that there are at least two OK elements, one could write
\[\exists x,y (\neg (x=y) \wedge P(x,x) \wedge P(y,y))\]

\bparts

\ppart For every natural number $n$, describe a logical formula $E_n$ which means
``there are at least $n$ OK elements in the domain.''

\solution{For $n\ge 1$, the desired formula is
\[
\exists x_1,\dots,x_n [(\bigwedge_{1 \leq i < j \leq n} \neg x_i = x_j)
        \wedge (\bigwedge_{1 \leq i \leq n} P(x_i,x_i))].
\]
}

\ppart Describe a formula which means that there are \emph{exactly} $n$ OK
elements.

\solution{$E_n \wedge \neg E_{n+1}$.}

\ppart Describe a formula, $F_P$, which means that $P$ determines a
function on the domain, that is, there is some function $f$ on the domain
such that $P(x,y)$ holds iff $y=f(x)$.  (Remember, however, that you may
not write a formula $\exists f \dots$ because variables may only range
over the domain, not functions on the domain.)

\solution{$F_P$ is the conjunction of the following two formulas:

``$P$ determines a function where it is defined'':
\[\forall x, y, z (P(x,y) \wedge P(x,z))\implies y=z\]

``the function is defined on the whole domain'':
\[\forall x \exists y P(x,y)\]
}

\ppart Describe a formula which cannot hold for any finite domain, but can
hold for some infinite domain.  \hint Start by saying that $P$ determines
a function which is one-to-one (injective), that is, that the function
always yields two different values on any two different arguments.

\solution{$P$ determines a function which is one-to-one:
\[
F_P \wedge \forall x_1,x_2, y((P(x_1,y) \wedge P(x_2,y)) \implies x_1 = x_2)
\]

Some element is not in the range of the function:
\[\exists y \forall x \neg P(x,y).\]}


\eparts

\problem

The following theorems are false, but where exactly are the bugs in
the proofs?

\bparts

\ppart
\begin{myfalsetheorem}
$\forall x \in \mathbb{R} \ \forall n \in \mathbb{N} \ x^n=1$.
\end{myfalsetheorem}

\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that $x^n = 1$ for all real $x$.  In the base case, $P(0)$ holds
because $x^n = x^0 = 1$ by definition of ``zero-th power'' of a real
number.

In the inductive step, for some $n \geq 0$ we may assume that $x^k = 1$
for all real $x$ and for all integers $0 \leq k \leq n$

We must show that $x^{n+1}=1$.  By the induction hypothesis with $k=n$ and
again with $k=1$, we have $x^n=1$ and $x^1=1$.  So,
\[
x^{n+1} = x^n \cdot x^1 = 1 \cdot 1 = 1.
\]
\end{proof}

\solution{
The proof of the induction step is not correct when $n=0$.  In this
case, $k=1$ does not satisfy $0 \leq k \leq n$.  Therefore we cannot
assume by strong induction that $x^1 = 1$, which is false anyway when
$x \neq 1$.}

\ppart

\begin{myfalsetheorem}
Let $p$, $n$, and $x_1, x_2,\ldots, x_n$ be positive integers.  If $p
\mid x_1 x_2 \cdots x_n$, then $p \mid x_i$ for some $1 \leq i \leq
n$.
\end{myfalsetheorem}

\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that if $p$ divides the product $x_1 x_2 \cdots x_n$, then $p$ divides
$x_i$ for some $1 \leq i \leq n$.

\emph{Base case}. $P(1)$ is trivial: if $p$ divides the length one product
$x_1$, then $p$ divides $x_1$.

In the inductive step, assume $P(1), \ldots, P(n)$ to prove $P(n+1)$.

So suppose that $p \mid x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n
x_{n+1}$, so $x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since
the right side of this equality is a product of $n$ terms, we have by
induction that $p$ divides one of them.  If $p \mid x_i$ for some $i <
n$, then we have the desired $i$.  Otherwise $p \mid y_n$.  But since
$y_n$ is a product of the two terms $x_n, x_{n+1}$, we have by strong
induction that $p$ divides one of them.  So in this case $p \mid x_i$
for some $i = n$ or $i = n+1$.
\end{proof}

\solution{
The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.}
\eparts


\end{problems}

\end{document}

