\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 1    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $A$, $B$, and $C$ be sets.  Assume that $A \cap
B \cap C = \emptyset$.  Prove that

\[
A \cup B \cup C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A).
\]

(Note: If $X$ and $Y$ are sets, then $X \setminus Y$ is the set of
elements in $X$ that are not in $Y$.)

\bigskip

\begin{proof}
We prove the equality by showing that the left set contains the right
set and vice versa.  Let $S$ be the set on the left, $A \cup B \cup
C$, and let $T$ be the set on the right, $(A \setminus B) \cup (B
\setminus C) \cup (C \setminus A)$.  Our objective is to prove that $S
= T$.

First, we show that $S$ is contained in $T$.  Let $x$ be an element of
$S = A \cup B \cup C$.  There are then six cases:

\begin{itemize}
\item $x \in A, x \not\in B, x \not\in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \not\in A, x \not\in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.

\item $x \in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \in A, x \not\in B, x \in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.
\end{itemize}

In every case, $x \in T$ as well; therefore, every element of $S$ is
also an element of $T$, and so $S \subseteq T$.  (Note that the case
$x \in A, x \in B, x \in C$ does not exist, since $A \cap B \cap C =
\emptyset$ by assumption.)

Now we show that $T$ is contained in $S$.  Let $x$ be an element of $T
= (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.  There
are then three cases:

\begin{itemize}
\item $x \in A \setminus B$:  This implies that $x \in A$, and so $x \in S$.
\item $x \in B \setminus C$:  This implies that $x \in B$, and so $x \in S$.
\item $x \in C \setminus A$:  This implies that $x \in C$, and so $x \in S$.
\end{itemize}

In every case, $x \in S$ as well; therefore, every element of $T$ is
also an element of $S$, and so $T \subseteq S$.  Since set $S$
contains set $T$ and vice versa, $S$ and $T$ must be the same set;
that is, $S = T$.
\end{proof}

\bigskip

The following alternative presentation of the proof may make the
structure of the argument more clear.

\begin{proof}
Goal: show that if $A \cap B \cap C = \emptyset$, then $A \cup B \cup
C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.

\begin{enumerate}
\item Let $S = A \cup B \cup C$.
\item Let $T = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.
\item $S \subseteq T$
	\begin{enumerate}
	\item Let $x$ be an element of $S$.
	\item If $x \in A, x \not\in B, x \not\in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \not\in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \not\in B, x \in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item $T \subseteq S$
	\begin{enumerate}
	\item Let $x$ be an element of $T$.
	\item If $x \in A \setminus B$, then $x \in A \subseteq S$
		by definition of $\setminus$ and of $S$.
	\item If $x \in B \setminus C$, then $x \in B \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item If $x \in C \setminus A$, then $x \in C \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item Q. E. D. since two-way set inclusion implies equality.
\end{enumerate}
\end{proof}

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

\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.)

\bigskip

\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}$,
which implies that $\sqrt[3]{4}$ is rational.

Since $\sqrt[3]{4}$ is rational, we can write it as a fraction $x / y$
in lowest-terms, where $x$ is an integer and $y$ is a positive
integer.  Therefore, we have:

\begin{eqnarray*}
\sqrt[3]{4}	& = &	x / y \\
4		& = &	x^3 / y^3 \\
4 y^3		& = &	x^3
\end{eqnarray*}

In the last equation, the left side is even, and so the right side
must be even.  Since $x^3$ is even, $x$ itself must be even.  This
implies that the right side is actually divisible by 8, and so the
left side must also be divisible by 8.  Therefore, $y^3$ is even, and
so $y$ itself must be even.

The fact that both $x$ and $y$ are even contradicts the fact that $x /
y$ is a fraction in lowest terms.  Therefore, $\sqrt[3]{2}$ is not
sensible.
\end{proof}

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

\problem

\begin{problemparts}

\problempart {\bf (Oiler's Conjecture)} The following claim,
often confused with the famous Euler Conjecture, was made by the
driver of a heating-oil truck in Cambridge.  Prove or disprove: the
equation $a^3 + b^3 + c^3 + d^3 = e^3$ has no solutions when $a$, $b$,
$c$, $d$, and $e$ are all positive integers.

The claim is false.  One solution to the equation is:

\[
1^3 + 1^3 + 5^3 + 7^3 = 343 = 7^3
\]

\problempart {\bf (The Goldenbacher Conjecture)} The oiler's brother-in-law,
Stu Goldenbacher, has made a claim of his own, which is similar to the
well-known Goldbach Conjecture.  Prove or disprove: every positive
even number is the sum of at most two primes, one of which has a
single digit.  As evidence for his conjecture, Stu points out that 2 =
2, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, and 12 = 7 + 5.

There are only four possible ways to write a number $n$ as the sum of
a single digit prime and another number: $2 + (n-2)$, $3 + (n-3)$, $5
+ (n-5)$, and $7 + (n-7)$.  If there exists an $n$ such that $n-2$,
$n-3$, $n-5$, and $n-7$ are all composite, then there is no way to
write $n$ as the sum of two primes, one of which has a single digit,
and the conjecture is disproved.

Such is the case if, for example, we choose $n = 2 \cdot 3 \cdot 5
\cdot 7 = 210$.  Then we have

\begin{eqnarray*}
n-2 & = & 2 \cdot(3 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
n-3 & = & 3 \cdot(2 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
n-5 & = & 5 \cdot(2 \cdot 3 \cdot 7 - 1) \quad \mbox{composite} \\
n-7 & = & 7 \cdot(2 \cdot 3 \cdot 5 - 1) \quad \mbox{composite}
\end{eqnarray*}

Therefore, the conjecture is false.

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%%%%%%%%%  S99 ps1

\problem (\S 3.1, Exercise 18) As a preliminary, note that a natural
number $n$ is a perfect square if an only if every prime appears an
even number of times in the prime factorization of $n$.  To prove one
direction, note that if $n$ is a perfect square, then there exists an
$m$ such that $n = m^2$.  Each prime appears twice in the prime
factorization of $n$ for each appearance of the prime in the
factorization $m$; thus, each prime appears an even number of times in
the factorization of $m$.  To prove the other direction, suppose that
every prime appears an even number of times in the factorization of
$n$.  Then let $m$ be the product of primes in which each prime
appears half as many times as in the factorization of $n$.  Then $m^2
= n$, and so $n$ is a perfect square.

Now we prove the main claim.  Let $n$ be a natural number that is not
a perfect square.  Assume for the purpose of contradiction that
$\sqrt{n}$ is rational.  Then we can write $\sqrt{n} = a / b$, where
$a$ and $b$ are integers and $b$ is positive.  Squaring and
multiplying both sizes of this equation by $b^2$ gives $nb^2 = a^2$.
Since $n$ is not a perfect square, there is a prime $p$ such that the
highest power of $p$ dividing $n$ is odd.  Since $b^2$ is a perfect
square, the highest power of $p$ dividing $b^2$ is even.  Thus, the
highest power of $p$ dividing $n b^2$ is odd.  On the other hand, the
highest power of $p$ dividing $a^2$ is even, since $a^2$ is a perfect
square.  These conclusions contradict the fact that $n b^2 = a^2$.
Thus, the assumption that $\sqrt{n}$ is rational must be false.


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%
%pset1 problem8 from spring98

\problem \hfill

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of a
prime number is irrational.

\ppart Your proof must depend on some property of prime numbers not shared
by all integers greater than one.  Why?  What property?

\eparts

%%%%%%%% SOLUTION
%pset1 problem8 from spring98

\solution{

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of
a prime number is irrational.

Proof by contradiction:
Assume for the purposes of contradiction that the $n$th root
of a prime number, $p$, is rational.

$p ^ {1/n} = a/b$ where $a,b \in \naturals$ and $a,b$ are in lowest terms.\\
$p = a^n/b^n$\\
$b^np = a^n$ \\
therefore $a^n$ is divisible by $p$\\
therefore $a$ is divisible by $p$.\\
$a = pa_1$\\
$b^np=p^n(a_1)^n$\\
$b^n=p^{n-1}(a_1)^n$\\
therefore $b^n$ is divisible by $p^{n-1}$, and $n > 1$, \\
so $b^n$ is divisible by $p$\\
therefore $b$ is divisible by $p$\\
therefore $a$ and $b$ are both divisible by $p$, and so are not in lowest terms,
a contradiction. \qed

\ppart Your proof must depend on some property of prime numbers not
shared by all integers greater than one.  Why?  What property?

\solution{The property used is that $p | a^n$ for some $n > 0$, implies that $p$
divides $a$.}

\eparts
}

%%% Example in Spring98 recitation 1; generalizes S98, pset1, prob 8 above
%%Edited by ARM 9/2/01

\subsection*{Proof by contradiction; Least Number Principle}

\begin{lemma}
For any positive integers $m$ and $n$, $\sqrt{m}{n}$, the $m$th root of
$n$ is either an integer or irrational.
\end{lemma}

So for example the lemma tells us that $\sqrt{2}$, $4^{1/3}$, $10^{1/5}$ 
are all irrational numbers.\\

{\em Proof. } 
Every real number is either an integer, or a ratio of two integers with
the denominator greater than 1, or irrational. Let us assume for the
purpose of getting a contradiction that for some integers $m,n$ the 
number $\sqrt{m}{n}$ is of the second kind, namely,
\[
\sqrt{m}{n}= \frac{a}{b}
\]
for some relatively prime positive integers $a,b$ with $b>1$.

Taking $m$th powers and multiplying by $b^m$, we have
\[
nb^m = a^m.
\]
Let $p$ be a prime divisor of $b$ (such a prime divisor exists since $b
>1$).  Then $a^m$ must also be divisible by the same prime.  By the
Fundamental Theorem of Arithmetic (aka the Prime Factorization Theorem),
this means that $p$ is a divisor of $a$.  But we assumed that $a,b$ have
no common divisors, so this is a contradiction.  \qed

Using the same idea as above we can prove the following more general
statement.

\begin{lemma}
Let $p(x)$ be a nonconstant, monic\footnote{``monic'' means the high order
coefficient of the highest degree term in $p$ is 1.} polynomial with
integer coefficients.  Then any root of the polynomial is either integral
or irrational.
\end{lemma}

{\em Proof.} 
Say 
\[
p(x) = a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1} + x^n
\]
where each $a_i \in \ints$.  Since $p$ is nonconstant, we know $n>0$.

Let $r$ be a root of $p$.  That is,
\[
a_0 + a_1r + \dots + a_{n-1}r^{n-1} + x^n = 0.
\]

There are three cases according to whether $r$ is (1) integral, (2)
irrational, or (3) the ratio of two integers with no common divisors where
the denominator is greater than one.  We want to eliminate the last case.

So let us assume for a contradiction that $r = s/t$ where $s$ and $t$ are
integers that have no common divisors, and $t >1$.  Substituting $s/t$ for
$r$ and multiplying both sides of the above equation by $t^n$ yields:
\[
a_0t^n + a_1st^{n-1} + \dots + a{n-1}s^{n-1}t + s^n = 0.
\]
So
\[
a_0t^n+a_1st^{n-1}+ \dots + a_{n-1}s^{n-1}t = -s^n.
\]

Now let $q$ be a prime divisor of $t$.  Then $q$ divides the lefthand side
of the above equation, and therefore also the righthand side.  So $q
\divides s^n$, and since $n>0$ and $q$ is prime, we can conclude that $q
\divides s$.  Hence $q$ is a common prime factor of $s$ and $t$,
contradicting our assumption that they have no common divisors.  \qed


%%%%%%%%
%pset1 problem9 from spring98

\problem
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or $4 |
(n^2-1)$.

%%%%%%%% SOLUTION
%pset1 problem9 from spring98

\solution{
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or
$4 | (n^2-1)$.\\

Case one: n is even.  Then $2 | n$ and therefore $4 | n^2$.\\

Case two: n is odd.  So $n = 2k+1$ for some $k \in \naturals$.  Then $n^2
-1 = (2k+1)^2 -1 = (4k^2 + 4k +1) - 1 = 4k^2 + 4k = 4(k^2 + k)$, so $4 |
n^2 -1$. \qed
} %solution

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem \textbf{Proofs or fallacies?}  %variant of fall99

Determine whether each of the following arguments is valid.
If it is not valid, then explain what the error is. (You may want to use the rules of inference and fallacies from Rosen in your solutions.)

\begin{problemparts}

\problempart
{\em Theorem:} if $n^3>1$, then $n>1$.  {\em Proof:}
If $n$ is a real number such that $n>1$, then $n^3>1$.  Suppose that
$n^3>1$, then $n>1$.
\solution{
\medskip
\textbf{Solution:}\\
Not valid. Given the propositions \\
p: $n>1$ \\
q: $n^3>1$ \\ 
the argument says that $p \rightarrow q$, so if q then p.
This is the fallacy of affirming the conclusion.
}

\problempart
{\em Theorem:} The number $\log_2 3$ is irrational. {\em Proof:} A number is irrational if it is not the ratio of two integers.
Therefore, since $\log_2 3$ cannot be written in the form $a/b$ where
$a$ and $b$ are integers, it is irrational.
\solution{
\medskip
\textbf{Solution:}\\
Not valid. Fallacy: Circular reasoning.  The statement following the
``therefore'' is precisely the one we want to prove.  And it doesn't
follow from anything before, so the therefore has no justification for
being there.

}
\problempart
{\em Theorem:} If $n^2 > 9$ then, $n > 3$.  {\em Proof:} Because
if $n$ is a real number with $n>3$, then $n^2 >9$.
\end{problemparts}
\solution{
\medskip
\textbf{Solution:}\\
Not valid. Given the propositions \\
p: $n > 3$ \\
q: $n^2 >9$ \\
the argument says that $p \rightarrow q$, so if q then p.
Again, this is the fallacy of affirming the conclusion.
}
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem \textbf{Proofs}
Velleman \S 3.1, Exercise 6.
\solution{
\medskip
\textbf{Solution:}\\
We prove the contrapositive i.e. if $x = 8$, $\frac{\sqrt[3]{x} + 5}{x^2 + 6} \ne \frac{1}{x}$.
\[\frac{\sqrt[3]{8} + 5}{8^2 + 6} = \frac{1}{10} \ne \frac{1}{x} = \frac{1}{8} \]\\
As we have shown the contrapositive to be true, the original hypothesis, that if $\frac{\sqrt[3]{x} + 5}{x^2 + 6} = \frac{1}{x}$ then $x \ne 8$, is true. This is an example of an indirect proof. 
 }
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem \textbf{And more proofs}
Rosen \S 3.1, Exercise 46.
\solution{
\bigskip
\textbf{Solution:}\\
Proof by cases:
\begin{enumerate}
\item $m = 1$ 
\\
As $n$ is an integer, $\lfloor \lfloor x \rfloor + n \rfloor = \lfloor \lfloor x \rfloor \rfloor + n = \lfloor x \rfloor + n = \lfloor x + n \rfloor$\\
The hypothesis is proved to be true when $m = 1$.

\medskip
\item $m > 1$ 
\\
Proof by contradiction: \\
Assume that the hypothesis is false, that is $\lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor \ne \lfloor \frac{x + n}{m} \rfloor$.\\
Let $x = z + y$, where $z$ is an integer and $0 \leqslant y < 1$.\\
Also, let  $k = \lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor$.
\[k = \lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor \ne \lfloor \frac{x + n}{m} \rfloor\]
\[k = \lfloor \frac{z + n}{m} \rfloor \ne \lfloor \frac{z + y + n}{m} \rfloor\]
As $m$ is an integer and is greater than 1, it follows that 
\[\frac{z + n}{m} \leqslant k + \frac{m - 1}{m} \]
and
\[\frac{z + n + y}{m} \geqslant k + \frac{m}{m}\]
\medskip
Thus, 
\[\frac{y}{m} \geqslant \frac{1}{m}\]
\[y \geqslant 1\]

This is a contradiction, as we defined $0 \leqslant y < 1$. Thus, our original hypothesis, $\lfloor \frac{\lfloor x \rfloor + n}{m} \rfloor = \lfloor \frac{x + n}{m} \rfloor$, is true when $m > 1$. 
\end{enumerate}

As we have proved that the hypothesis is true in both cases, the hypothesis is always true.
} 
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem
% Explicit identification of EI, EG, UI, UG steps in a logical proof.

\ppart Give a formal reason for each starred line in the following structured 
proof. Refer to previous steps wherever you think that will be helpful in 
understanding your proof.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Given:  $\forall x  \forall y [P(x) \vee Q(y)]$ \\
Prove:  $(\forall x  P(x)) \vee (\forall y Q(y))$ \\
1. Assume $\neg \forall x P(x)$ \\
2(*). $\exists x \neg P(x)$ \> \> \> \> \> \solution{ Negation of universal quantifier}\\
3(*). Choose $x_0$ such that $\neg P(x_0)$. \> \> \> \> \> \solution{ Existential Instantiation }\\
4(*). $\forall y (P(x_0) \vee Q(y))$ \> \> \> \> \> \solution{ Universal Instantiation of hypothesis}\\
5. $\forall y Q(y)$ \\
\> 1. Pick an arbitrary $y_0$ \\
\> 2(*). $P(x_0) \vee Q(y_0)$  \> \> \> \> \solution{ Universal Instantiation, using 4.}\\
\> 3(*). $Q(y_0)$ \> \> \> \>  \solution{ Propositional reasoning, using 5.2. and 3.}\\
\> 4(*). QED ($\forall y Q(y)$) \> \> \> \> \solution{ Universal Generalization }\\
6(*). QED ($(\forall x  P(x)) \vee (\forall y Q(y))$) \> \> \> \> \> \solution{ Propositional reasoning, using 5.  
              ($B \implies A \vee B$)}\\
\end{tabbing}
\ppart
Write your own structured proof of the other direction, complete with reasons:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Given:  $(\forall x  P(x)) \vee (\forall y Q(y))$ \\
Prove:  $\forall x  \forall y [P(x) \vee Q(y)]$ \\
\solution{
\medskip
\textbf{Solution:}\\
1. First, we will prove $(\forall x  P(x)) \implies \forall x \forall y [P(x) \vee Q(y)]$\\
 \> 1. Assume $\forall x P(x)$ \\
 \> 2. To prove 1, use 1.1 to prove $\forall x \forall y [P(x) \vee Q(y)]$ \\
 \> \> 1. Pick an arbitrary $x_0$, $y_0$ \\
 \> \> 2. $P(x_0)$ 
 \> \> \> Universal Instantiation, from 1.1. \\
 \> \> 3. $P(x_0) \vee Q(y_0)$ 
       \> \> \> Propositional reasoning, from 1.2.2 \\
 \> \> 4. QED
       \> \> \> Universal Generalization \\
 \> 3. QED 
    \> \> \> \> Implication\\
 2. Next, prove $(\forall y  Q(y)) \implies \forall x \forall y [P(x) \vee Q(y)]$ 
 \> \> \> \> \> Similar argument to the one for 1. \\
 3. Combine 1 and 2 to get $[(\forall x  P(x)) \vee (\forall y Q(y))] \implies [\forall x  \forall y [P(x) \vee Q(y)]]$ \\
 \> \> \> \> \> Cases\\
 4. QED
 \> \> \> \> \> Modus ponens, from 3. and ``Given''.
}
\end{tabbing}
%%%%%%%%%%%%%%%%%%%%%%%%%END  Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems

%PROOFS from Spring94
%%FALSE PROOF ARITHMETIC, revised ARM 9/3/01

\problem Identify the error in the following ``proof'' that if $a$ and $b$
are two equal real numbers, then $a=0$.
\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}

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


\end{problems}

\end{document}


