\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\renewcommand{\nand}{|}
\newcommand{\solspace}{\medskip\\ 
\textbf{Solution:}\\}
\renewcommand{\implies}{\longrightarrow}
\askaboutsolutions
\begin{document}
\pset{1}{February 6, 2001}{2:35pm in lecture, February 13, 2001}

%6782685711022254907  
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

%---------------------------------------------------------------------------\\
%
%\textbf{Self-study:  ???}
%Read: ????
%Self-study problems (not to be handed in): 
%????
%
%----------------------------------------------------------------------------\
\textbf{Background Reading:} Velleman, \textit{How to Prove It},
Chapter 1.  Rosen, Section 1.6.  

Much of this reviews elementary mathematical topics that should be
familiar to you; you can skim these.  Do look closely at any topics
that seem unfamiliar, and if there are many such topics, we encourage
you to discuss this with your TA so he can help you plan a catch-up
strategy.

\textbf{Reading:}
Velleman, \textit{How to Prove It}, Sections 2.1, 2.2, 3.1--3.3 \\
Rosen, \textit{Discrete Mathematics and Its Applications}, Sections 2.3, 3.1 \\

\vspace{-.25in}
\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

\vspace{-.25in}
\paragraph{Proofs} Some of the problems ask you to ``verify or falsify''
a proof. For these problems, you must either justify the correctness of
each step of the proof, or else locate and explain the error.
It is not sufficient to merely show that an incorrect proof is indeed
wrong. You must explain where the bug is.

%When you are asked for a proof, you may assume only the facts and theorems we have seen in class so far.  Do
%not assume facts that we have not proved, such as, for example, that
%every rational number is representable by a fraction in lowest terms.  

The following exercises are {\bf optional;} do them if you think you
need the practice.  The mini-quiz in tutorial on Friday will draw
(only) from these problems.

\begin{enumerate}

\item Exercises from Velleman: 1.1.3 (that is, exercise 3 in section
  1.1), 1.2.7 

\item Exercises from Rosen (answers in the back of the book): Section
  1.1, numbers 1, 3, 5, 7, 15, 17, 19; Section 1.2, numbers 5,
  7, 11, 13.  

\end{enumerate}


\medskip
\begin{problems} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
%PROOFS
%from Spring94
\problem Verify or falsify the following proof that if $a$ and $b$
are two equal real numbers, then $a=0$.\\
\emph{Suggested proof:}
\begin{eqnarray*}
a&=&b \\
a^2&=&ab \\
a^2-b^2&=&ab-b^2 \\
(a-b)(a+b)&=&(a-b)b \\
a+b&=&b \\
a&=&0 
\end{eqnarray*}

\solution{
\medskip
\textbf{Solution:}\\ 
The proof is incorrect: One cannot divide the two sides of the
equation by $a-b$ since $a=b$. }

%PROOFS
%from Fall 99
\problem %From Fall 95 ps1, prob 7

Determine whether each of the following arguments is valid.  If an
argument is correct, what rule of inference (from Rosen, \S~3.1) is
being used? If it is not, what fallacy (again from Rosen \S~3.1)
occurs?

\begin{problemparts}
\problempart
{\em Theorem:} if $n^2>1$, then $n>1$. \\
{\em Suggested proof:} If $n$ is a real number such that $n>1$, then $n^2>1$.
Suppose that $n^2>1$, then $n>1$.

\solution{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} The number $\log_2 3$ is irrational. \\
{\em Suggested 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{Invalid. Fallacy of affirming the conclusion.}

\problempart
{\em Theorem:} If $n^2 \leq 9$ then, $n \leq 3$. \\
{\em Suggested proof:} Because if $n$ is a real number with $n>3$,
then $n^2 >9$.

\solution{Valid. Modus tollens.}

\problempart
{\em Theorem} If $n\leq 2$, then $n^2\leq 4$.\\
{\em Suggested proof:} Because if $n$ is a real number with $n>2$,
then $n^2>4$.

\solution{Invalid. Fallacy of denying the hypothesis.}

\end{problemparts}      
                               
%spring00
\problem Consider the following incorrect theorem: \begin{quote} If $\forall x \in
A (x \ne 0)$ and $A \subseteq B$ then $\forall x \in B (x \ne 0)$. \end{quote}


\vspace{-3ex}
\begin{problemparts}
\ppart What is wrong with the following proof of the theorem? \begin{quote}
\emph{``Proof'':}~~~Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A \; (x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B \; (x \ne 0)$. \end{quote}
\solution {
\medskip

\textbf{Solution:}
Universal generalization requires that the generalized variable be
arbitrarily chosen \emph{from the set over which we are
generalizing}. We selected $x$ arbitrarily from set $A$ but are
generalizing over a different (larger) set $B$, 
which is not a valid inference rule.   To use universal generalization,
we should imagine an adversary picking the worst possible element from
the set over which we are generalizing.  The proof must work even for that
worst case.
}
\ppart Give a counterexample to the theorem.
\solution{
\medskip

\textbf{Solution:} 
Let $A = \mathbb{N^+}$ and $B = \mathbb{Z}$. 
}

\end{problemparts}  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\problem 
%QUANTIFIERS
%from spring97
% 1.3 # 8

Let $T(x,y)$ be the statement ``$x$ has proven $y$.''
Express each of the following sentences in terms of $T(x,y)$,
quantifiers and logical connectives, where the universe of the
discourse for $x$ is the set of all mathematicians and for
$y$ is the set of all theorems.

\begin{description}
\item[a)] There is a mathematician who has never proven a theorem. 
\item[b)] Every mathematician has proven a theorem.
\item[c)] Every theorem has been proven by a mathematician.
\item[d)] There is a mathematician who has proven the 
{\it Dominated Convergence Theorem} and the {\it Bounded Convergence Theorem}.
\item[e)] At least two mathematicians have proven the {\it Hahn-Banach
    Theorem} (Don't introduce numbers.  You will have to add one more
  standard symbol for this one).

\end{description}
\solution{
\medskip

\textbf{Solution:}\\ 
\begin{description}
\item[a)] $ \exists x \forall y (\neg T(x,y)) $
\item[b)] $ \forall x \exists y T(x,y) $

\item[c)] $ \forall y \exists x T(x,y)$

\item[d)]$ \exists x (T(x, \textrm{Dominated\_Conv.\_Thm}) \wedge
 T(x, \textrm{Bounded\_Conv.\_Thm})) $

\item[e)]  $ \exists x_1, x_2 ((x_1 \neq x_2) \wedge
 T(x_1, \textrm{Hahn-Banach\_Thm}) \wedge
 T(x_2, \textrm{Hahn-Banach\_Thm})) $

\end{description}
                                                                                               
}


\problem Identify the premises and conclusions of the following
deductive arguments and analyze their logical forms.  This may require
that you ``pin down'' a statement that could be interpreted in many ways.
Determine which are valid deductions and which are not.  If the
deduction is invalid, demonstrate a possible scenario in which the all
the premises are met but the conclusion is not.

\emph{Example:} If Alice is tall then she can reach the top shelf.  Alice is
not tall. Therefore, Alice cannot reach the top shelf.

\emph{Solution:} The proposed deduction can be written as a theorem
(with the premises above the line and the conclusions below).
\vspace{-1ex}
\begin{center}
\begin{tabular}{l}
        $ T \implies R$ \\
        $ \neg T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T = \mbox{``Alice is tall.''}$ \\
        $R = \mbox{``Alice can reach the top shelf.''}$
\end{tabular}
\end{center}
\vspace{-1ex}
This deduction is invalid.  For example, $\neg T \wedge R$ is consistent with
the premises but not with the conclusion.
%For example, given the statements, ``If Alice is tall then she can reach the
%top shelf.  Alice is not tall. Therefore, Alice cannot reach the top shelf.''
%Let $T$ be the proposition that Alice is tall.  Let $R$ be the proposition that
%Alice can reach the top shelf.  The proposed deduction can written as a theorem
%(with the premises above the line and the conclusions below).
%\begin{center}
%\begin{tabular}{l}
%       $ T \implies R$ \\
%       $ \neg T$ \\ \hline
%       $\therefore \neg R$
%\end{tabular}
%\end{center}
%This deduction is invalid.  For example, $\neg T \wedge R$ is consistent with
%the premises but not the conclusion.

\begin{problemparts}
\ppart Jane and Pete won't both win the math prize.  Pete will win
either the math prize or the chemistry prize.  Jane will win the math
prize.  Thus, Pete will win the chemistry prize.
\solution{
\medskip

\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $\neg (J \land M)$ \\
        $M \lor C$ \\ 
        $J$ \\ \hline
        $\therefore C$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``Jane will win the math prize.''}$ \\
        $M \equiv \mbox{``Pete will win the math prize.''}$ \\
        $C \equiv \mbox{``Pete will win the chemistry prize.''}$
\end{tabular}
\end{center}
This deduction is valid.    
}

\ppart The main course will be beef or fish.  The vegetable will be
peas or corn. We will not have both fish as a main course and corn as
a vegetable. Therefore, we will not have both beef as a main course
and peas as a vegetable.
\solution{
\medskip

\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $B \lor F$ \\
        $C \lor P$ \\
        $\neg (F \land C)$ \\ \hline
        $\therefore \neg (B \land P)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $B \equiv \mbox{``The main course will be beef.''}$ \\
        $F \equiv \mbox{``The main course will be fish.''}$ \\
        $C \equiv \mbox{``The vegetable will be corn.''}$ \\
        $P \equiv \mbox{``The vegetable will be peas.''}$ 
\end{tabular}
\end{center}
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the premises but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.  If we wished to exclude
the possibility of multiple courses we could have used exclusive-or
instead of inclusive-or. So our premise about the main course would
then read $B \oplus F$ or, equivalently, 
$(B \lor F) \land \neg (B \land F)$. 
The premise about the vegetable could be changed similarly.  
The deduction is still invalid with this formalization. 
                                                         
}

\ppart Either John or Bill is telling the truth.  Either Sam or Bill
is lying.  Thus, either John is telling the truth or Sam is lying.
\solution{
\medskip

\textbf{Solution:}
We interpret ``John is lying,'' to be 
the negation of ``John is telling the truth.'' 
Similarly for the corresponding propositions involving Bill and Sam.
The deduction is:
\begin{center}
\begin{tabular}{l}
        $J \lor B$ \\
        $\neg S \lor \neg B$ \\ \hline
        $\therefore J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``John is telling the truth.''}$ \\
        $B \equiv \mbox{``Bill is telling the truth.''}$ \\
        $S \equiv \mbox{``Sam is telling the truth.''}$
\end{tabular}
\end{center}
This deduction is valid.  It is an example of a common
``cancellation'' rule that lets us get rid of the proposition $B$.   
}

\ppart Either sales will go up and the boss will be happy, or expenses
will go up and the boss won't be happy.  Therefore, sales and expenses
will not both go up.
\solution{

\medskip
\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $(S \land H) \lor (E \land \neg H)$ \\ \hline
        $\therefore \neg (S \land E)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $S \equiv \mbox{``Sales will go up.''}$ \\
        $H \equiv \mbox{``The boss will be happy.''}$ \\
        $E \equiv \mbox{``Expenses will go up.''}$ 
\end{tabular}
\end{center}
This deduction is invalid. 
For example, $S \land E \land H$ is consistent 
with the premises but not with the conclusion. 
                     
}

\ppart If the tax rate and unemployment both go up then there will be
a recession.  If the GNP goes up there will not be a recession.  GNP
and taxes are both going up.  Therefore, there will not be a
recession.
\solution{

\medskip
\textbf{Solution:}
The deduction is:
\begin{center}
\begin{tabular}{l}
        $T \land U \implies R$ \\
        $G \implies \neg R$ \\
        $G \land T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T \equiv \mbox{``The tax rate goes up.''}$ \\
        $U \equiv \mbox{``Unemployment goes up.''}$ \\
        $G \equiv \mbox{``GNP goes up.''}$ \\
        $R \equiv \mbox{``There will be a recession.''}$
\end{tabular}
\end{center}
This deduction is valid. 
(The first premise is superfluous.)    
}
\end{problemparts}

% This is proven on page 3 of Velleman (Proposition 2). Add a remark
% about this to the problem repository.
% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
% % %PROOFS
% % %may be too difficult..
% % %from fall 94
% %
% % \problem
% % Prove that if $2^n-1$ is prime, then $n$ is prime.\\\hint  Recall that $(x-1) \mid (x^k -1)$.
% % \solution{
% % \begin{proof}
% % We will prove the contrapositive:
% % If $n$ is composite, then $2^n-1$ is composite.
% %
% % If $n$ is composite, then $n=ab$ for some $a,b\in\nats$ with $1<a<n$.
% % Recall that $(x-1) \mid (x^k -1)$ (the quotient is $x^{k-1}+\cdots +x+1$).
% % Letting $x=2^a$, we have $(2^a - 1) \mid ((2^a)^b - 1)$.
% % Since $1<a<n$, we have $1<(2^a-1)<(2^n-1)$, 
% % and so $2^a-1$ is a nontrivial divisor of $2^n-1$.
% % \remove{
% %     Now, $2^n-1=2^{ab}-1=(2^a-1)(2^{(b-1)a}+2^{(b-2)a}+2^{(b-3)a}+ \cdots +
% %     2^a + 1)$.
% %     For $a>1$, $2^a-1>1$.  
% %     For $a>1,b>1$, $2^{(b-1)a} >1$, thus
% %     $(2^{(b-1)a}+2^{(b-2)a}+2^{(b-3)a}+ \cdots +
% %     2^a + 1) >1$.
% % }
% % Therefore, $2^n-1$ is composite.
% % \end{proof}
% % }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    

%PROOFS
%from Fall98

\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)
\solution{\solspace
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.  
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%spring00
\problem Suppose $x$ is a real number.  Prove \textbf{by cases} that there is a
real $y$ such that $\frac{y+1}{y-2}=x$ if and only if $x \ne 1$.
\solution{
\medskip  \\
\textbf{Solution:} \\
We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1 ($x \not = 1$): ]
We need to prove that there exists $y \in \mathbb{R}$ such that
$\frac{y+1}{y-2}=x$.  In particular, consider $y = \frac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\[\frac{y+1}{y-2} 
        = \frac{\frac{2x+1}{x-1}+1}{\;\frac{2x+1}{x-1}-2\;} 
        = \frac{\frac{2x+1 + (x-1)}{x-1}}{\;\frac{2x+1-2(x-1)}{x-1}\;}
        = \frac{\frac{3x}{x-1}}{\;\frac{2x+1-2x+2}{x-1}\;}
        = \frac{3x}{3}
        = x
\]
Therefore, by existential generalization, $\exists y \in \mathbb{R}$ such that
$\frac{y+1}{y-2} = x.$

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \mathbb{R}$ exists 
such that $\frac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\Longleftrightarrow \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\Longrightarrow \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\Longleftrightarrow \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)} \\
        &\Longleftrightarrow \;\; \text{false.}
\end{align*}
Therefore our supposition is wrong, 
and there is no $y$ such that $\frac{y+1}{y-2}=x$. 

\end{description}
}     


%LOGIC
%from fall97
%problem 3
% 1.2 - 25 modified 
\problem Find a compound proposition involving the propositions $p$,
$q$, and $r$ that is false when exactly two of $p$, $q$, and $r$ are
false.  The compound proposition is true otherwise. 

\solution{
\medskip
\textbf{Solution:}\\ 
It is easier to negate the proposition so that it's true when exactly two
are false.  This in turn asks for exactly one variable to be true.  
So we divide the proposition in three subclauses, one for each variable 
that might be the only true one.  This gives us:

\[ \neg ((\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r) 
\vee (p \wedge \neg q \wedge \neg r)) \]
which is equivalent (using DeMorgan's laws; see Rosen) to
\[ ((p \vee q \vee \neg r ) \wedge (p \vee \neg q \vee r ) \wedge (\neg p \vee q \vee r ))
\]
which is also equivalent to
\[
((p \wedge q) \vee (q \wedge r) \vee (p \wedge r)  \vee (\neg p \wedge \neg q \wedge \neg r))
\]
(This last derives the proposition by first putting in 3 clauses that
are true when exactly $2$ clauses are true, and then one clause when
exactly $0$ clauses are true (note that the third case, all 3 clauses
true, is already covered by the first 3 clauses).

As an alternative solution, 
notice that the proposition is true if (1) All the $p.q,r$ are false
($\neg p \wedge \neg q \wedge \neg r$), (2) All of them are true 
($p \wedge q \wedge r$), or (3) 
only one is false (in which case we have the three
subcases $(\neg p \wedge q \wedge r) \vee (p \wedge \neg q \wedge r)
\vee (p \wedge q \wedge \neg r))$.
Putting it all together:
\[((\neg p \wedge \neg q \wedge \neg r) \vee
(p \wedge q \wedge r) \vee
(\neg p \wedge q \wedge r) \vee (p \wedge \neg q \wedge r)
\vee (p \wedge q \wedge \neg r))\]
}                                        
\end{problems}
\end{document}                            
