\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{graphicx}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.9in}
\setlength{\textwidth}{6.5in}

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}
\newcommand{\divides}{\,\Big|\,}
\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 2510} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill February $23^{\mathrm{rd}}$, 2010}

\vspace{0.3in}

\noindent {\large\bf Name:} \underline{\large \sc Answer Key}\\
Don't merely state answers, prove your statements. {\bf Be sure to show your work!}

\noindent
{\bf \large 1. (12 points)} Consider theorem L10: $\vdash (\neg B \to \neg A) \to (A \to B)$
\begin{enumerate}[(a)]

   \item Show L10 is a tautology using by filling out an abbreviated truth table.

\vspace{0.1in}


$\displaystyle{
\begin{array}{ccccccccc} 
(\neg & B & \to & \neg & A) & \to & (A & \to & B) \\
           & T &      &          & T   &      &  T  &      & T   \\   
           & T &      &          & F   &      &  F  &      & T   \\   
           & F &      &          & T   &      &  T  &      & F   \\   
           & F &      &          & F   &      &  F  &      & F   
\end{array} 
\qquad \Longrightarrow \qquad
\begin{array}{ccccccccc} 
(\neg & B & \to & \neg & A) & \to & (A & \to & B) \\
    F    & T &      &    F    & T   &      &  T  &  T  & T   \\   
    F    & T &      &    T    & F   &      &  F  &  T  & T   \\   
    T    & F &      &    F    & T   &      &  T  &  F  & F   \\   
    T    & F &      &    T    & F   &      &  F  &  T  & F   
\end{array}
}$

\vspace{0.1in}

\hspace*{-0.575in}
$\displaystyle{
 \Longrightarrow \qquad
\begin{array}{ccccccccc} 
(\neg & B & \to & \neg & A) & \to & (A & \to & B) \\
    F    & T &  T  &    F    & T   &      &  T  &  T  & T   \\   
    F    & T &  T  &    T    & F   &      &  F  &  T  & T   \\   
    T    & F &  F  &    F    & T   &      &  T  &  F  & F   \\   
    T    & F &  T  &    T    & F   &      &  F  &  T  & F   
\end{array}
\qquad \Longrightarrow \qquad
\begin{array}{ccccccccc} 
(\neg & B & \to & \neg & A) & \to & (A & \to & B) \\
    F    & T &  T  &    F    & T   &  {\bf T}  &  T  &  T  & T   \\   
    F    & T &  T  &    T    & F   &  {\bf T}  &  F  &  T  & T   \\   
    T    & F &  F  &    F    & T   &  {\bf T}  &  T  &  F  & F   \\   
    T    & F &  T  &    T    & F   &  {\bf T}  &  F  &  T  & F   
\end{array}
}$

\vspace{0.1in}

   \item Prove L10 in system L. [You may use the deduction theorem and theorems L1 -- L9.]

\vspace{0.1in}

{}[Textbook theorem's proof omitted.]

\vspace{0.1in}

\end{enumerate}

\noindent
{\bf \large 2. (12 points)} Flawed proof\\

I am in the middle of proving ``$A \to B, \neg A \to B \vdash B$''. First, show (using an abbreviated truth table) that
            this is indeed a theorem of L. Then explain why I know I've made a mistake if I have the following lines in my proof:
            
            \begin{tabular}{llcc}
            \vdots & \vdots & & \vdots \\
            10 & $A$         &  & M.P. (lines 5 and 9) \\
            11 & $\neg \neg B \to \neg A$ & & M.P. (lines 2 and 7) \\
            12 & $(\neg \neg B \to \neg A) \to (A \to \neg B)$ & & L10 \\
            \vdots & \vdots & & \vdots 
            \end{tabular}

\vspace{0.1in}

To use a truth table to see that this theorem holds, we must convert it to a statement with no assumptions:
 
\hfill ``$((A \to B) \wedge (\neg A \to B)) \to B$'' \hfill \hfill

\vspace{0.1in}

\hspace*{-0.25in}
$\displaystyle{
\begin{array}{cccccccccc}
((A & \to & B) & \wedge & (\neg & A & \to & B)) & \to & B \\
   T &       & T  &               &            & T &       & T   &       & T \\
   F &       & T  &               &            & F &       & T   &       & T \\
   T &       & F  &               &            & T &       & F   &       & F \\
   F &       & F  &               &            & F &       & F   &       & F
\end{array}
\qquad \Longrightarrow \qquad
\begin{array}{cccccccccc}
((A & \to & B) & \wedge & (\neg & A & \to & B)) & \to & B \\
   T &  T  & T  &               &      F    & T &       & T   &       & T \\
   F &  T  & T  &               &      T    & F &       & T   &       & T \\
   T &  F  & F  &               &      F    & T &       & F   &       & F \\
   F &  T  & F  &               &      T    & F &       & F   &       & F
\end{array}
}$ 

\vspace{0.1in}

\hspace*{-0.755in}
$\displaystyle{
\Longrightarrow \qquad
\begin{array}{cccccccccc}
((A & \to & B) & \wedge & (\neg & A & \to & B)) & \to & B \\
   T &  T  & T  &               &      F    & T &   T  & T   &       & T \\
   F &  T  & T  &               &      T    & F &   T  & T   &       & T \\
   T &  F  & F  &               &      F    & T &   T  & F   &       & F \\
   F &  T  & F  &               &      T    & F &   F  & F   &       & F
\end{array}
\qquad \Longrightarrow \qquad
\begin{array}{cccccccccc}
((A & \to & B) & \wedge & (\neg & A & \to & B)) & \to & B \\
   T &  T  & T  &      T       &      F    & T &   T  & T   &       & T \\
   F &  T  & T  &      T       &      T    & F &   T  & T   &       & T \\
   T &  F  & F  &      F       &      F    & T &   T  & F   &       & F \\
   F &  T  & F  &      F       &      T    & F &   F  & F   &       & F
\end{array}
}$ 

\vspace{0.1in}

\hspace*{-0.755in}
$\displaystyle{
\Longrightarrow \qquad
\begin{array}{cccccccccc}
((A & \to & B) & \wedge & (\neg & A & \to & B)) & \to & B \\
   T &  T  & T  &      T       &      F    & T &   T  & T   &  {\bf T }  & T \\
   F &  T  & T  &      T       &      T    & F &   T  & T   &  {\bf T }  & T \\
   T &  F  & F  &      F       &      F    & T &   T  & F   &  {\bf T }  & F \\
   F &  T  & F  &      F       &      T    & F &   F  & F   &  {\bf T }  & F
\end{array}
\qquad \Longrightarrow \qquad
}$ This is a theorem of L.

There are several ways to see that the proof is flawed. One of the easiest ways is to note that M.P. (lines 11 and 12) gives ``$A \to \neg B$''
then M.P. this and line 10 gives $\neg B$. So if the theorem were true (which it is), we would have both $B$ and $\neg B$ (which is impossible).
Therefore, I must have made a mistake.

\noindent
{\bf \large 3. (10 points)} Construct models whose objects are $\mathbb{Z}$ (integers) to show that 
    $$\forall x \forall y \, (P(x,y) \to P(f(y),f(x)))$$ is satisfiable but not logically valid. [Note: $P(x,y)$ is a predicate and $f(x)$ is a function.]

\vspace{0.1in}

To show a statement is statisfiable we need to come up with a model in which the statement is true. If the statement were logically valid, it would need
to be true in all models, so we also need to come up with a model in which the statement is not true. There are infinitely many models which make this
statement true and infinitely many which falsify this statement. Fortunately, we just need one of each. I'll give two of each just for ?fun?.

\begin{description}
\item[Satisfiable] Our objects are $\mathbb{Z} = \{ \dots, -2,-1,0,1,2, \dots \}$ (the integers). Let $P(x,y)$ be the predicate $x < y$ (less than) and
let $f(x)=-x$ ($f$ negates $x$). Then the statement reads: ``$\forall x \forall y (x<y \to -y<-x)$'' which is true since multiplying both sides of an inequality
by a negative number ``flips'' it around.

Alternatively, let $P(x,y)$ be the predicate $x$ is positive (which has nothing to do with $y$, but this doesn't matter). Let $f(x)=1$ (the constant function 
which sends everything to $1$). Then the statement reads: ``$\forall x \forall y (x \mbox{ is positive} \to 1 \mbox{ is positive})$'' which is true since the
conclusion ``1 is positive'' is always true.
{}[Note: $P(f(y),f(x)) \leftrightarrow f(y) \mbox{ is positive} \leftrightarrow 1 \mbox{ is positive}$.]

\item[Not Logically Valid] Again, our objects are $\mathbb{Z} = \{ \dots, -2,-1,0,1,2, \dots \}$ (the integers). Let $P(x,y)$ be the predicate $x < y$ (less than)
and let $f(x) = x$ (the identity function). Then the statement reads: ``$\forall x \forall y (x<y \to y<x)$'' which isn't true since $0<1$ does not imply that
$1<0$. So the statement is not true in this model.

Alternatively, let $P(x,y)$ be the predicate ``$x+y$ is odd'' and let $f(x)=2x$. Then the statement reads: ``$\forall x \forall y (x+y \mbox{ is odd } \to 2y+2x \mbox{ is odd }$'' which is false. Consider the case $x=1$ and $y=0$. Then $x+y=1+0=1$ which is odd. However, $2y+2x=2(0)+2(1)=2$ which is not odd.
So the statement fails in this model as well.
\end{description}

\vspace{0.1in}

\noindent
{\bf \large 4. (14 points)} Proofs in K.
   
   \begin{enumerate}[(a)]
      \item Prove theorem K13: $\vdash \forall x A(x) \to \exists x A(x)$

\vspace{0.1in}

{}[Textbook theorem's proof omitted.]

\vspace{0.1in}

      \item Prove theorem K31: $\vdash \exists x (A(x) \wedge B(x)) \to (\exists x A(x) \wedge \exists x B(x))$

\vspace{0.1in}

{}[Textbook theorem's proof omitted.]

\vspace{0.1in}
   \end{enumerate}   

\noindent
{\bf \large 5. (14 points)} How about...more proofs?
   
   \begin{enumerate}[(a)]
      \item Use induction to show that $1+4+7+\cdots+(3n-2) = \frac{1}{2}n(3n-1)$ for all positive integers $n$. 
      
\begin{description}
\item[Base Case] We need to show that $1+4+7+\cdots+(3n-2) = \frac{1}{2}n(3n-1)$ holds when $n=1$ (the smallest positive integer).
When $n=1$, the left hand side is $1$ and the right hand side is $\frac{1}{2}(1)(3(1)-1) = (1/2)(2) = 1$. Therefore, the statement holds
when $n=1$. We have established the base case.
\item[Inductive Step] We need to show that if $1+4+7+\cdots+(3n-2) = \frac{1}{2}n(3n-1)$, then 
 $1+4+7+\cdots+(3n-2) + (3(n+1)-2) = \frac{1}{2}(n+1)(3(n+1)-1)$. So we assume that  $1+4+7+\cdots+(3n-2) = \frac{1}{2}n(3n-1)$ holds (this is our inductive hypothesis). Then $1+4+7+\cdots+(3n-2) + (3(n+1)-2) = \dots$

\vspace*{-0.2in}

\begin{eqnarray*}
& = & [1+4+7+\cdots+(3n-2)] + (3(n+1)-2) \\
& = & \left[\frac{1}{2}n(3n-1)\right] + (3(n+1)-2) \qquad \mbox{(using our inductive hypothesis)}\\
& = & \frac{1}{2}(3n^2-n) + (3n+1) = \frac{1}{2}(3n^2-n+6n+2) = \frac{1}{2}(3n^2+5n+2) 
\end{eqnarray*}

\vspace*{-0.05in}

On the other hand, $\frac{1}{2}(n+1)(3(n+1)-1)$ $=\frac{1}{2}(n+1)(3n+2)$ $=\frac{1}{2}(3n^2+5n+2)$. Therefore, $1+4+7+\cdots+(3n-2) + (3(n+1)-2) = \frac{1}{2}(n+1)(3(n+1)-1)$. So we have shown that if this equation holds for
some value $n$, then it also holds for $n+1$.
\end{description}

We have established the base case and inductive step. Therefore, by induction
the equation holds for all positive integers.

\newpage

      \item Prove that $\sqrt{2}$ is irrational. [Recall: $x$ is rational means $\exists$ integers $p,q$, $q \not= 0$ such that $x=p/q$.]
      
      {\it Hint:} Proof by contradiction.

\vspace{0.1in}

Let's suppose that $\sqrt{2}$ is a rational number then show that this is impossible. Suppose $\sqrt{2} = p/q$ where $p$ and $q$ are integers.
Without loss of generality, let's assume that $p/q$ is a reduced
fraction ($p$ and $q$ have no common factors other than $\pm 1$).

In this case, $(\sqrt{2})^2 = (p/q)^2$ so that $2 = p^2/q^2$
and therefore, $2q^2 = p^2$. Notice that the left hand side of this
equation is even. Therefore, $p^2$ is even. Thus $p$ must be even (otherwise,
$p$ odd implies $p^2$ odd since odd times odd is odd). Since $p$ is even,
there exists an integer $k$ such that $p=2k$. Therefore, $2q^2=(2k)^2 = 4k^2$
and thus $q^2=2k^2$. Now by the same reasoning as with $p$, we can conclude
that $q$ must be even. So both $p$ and $q$ are even. Thus the fraction $p/q$
is {\bf not} reduced which contradicts our assumption. 

Since the hypothesis that $\sqrt{2}$ is rational leads to a contradiction,
we must conclude that $\sqrt{2}$ is not rational (i.e. it's irrational).

{}[{\it Note:} It's not too hard to generalize this argument to show that $\sqrt{p}$ is irrational for any prime $p$.]

\vspace{0.3in}

   \end{enumerate}   


\noindent
\parbox{1.5in}{\bf Math 2510} 
\hfill {\Large \bf Test \#1 -- TAKE HOME} \hfill
\parbox{1.5in}{\bf \hfill Due: Feb. $24^{\mathrm{th}}$, 2010}

\vspace{0.3in}

\noindent {\large\bf Name:} \underline{\sc Answer Key}\\
You may use notes and your textbook, but no help from other people especially your classmates.
 
\vspace{0.2in} 
   
\noindent
{\bf \large 6. (12 points)}  A few more proofs in L
   \begin{enumerate}[(a)]
      \item Prove theorem L7: $A \to (B \to C) \vdash B \to (A \to C)$. You may use the deduction theorem and theorems L1 -- L6.

\vspace{0.1in}

{}[Textbook theorem's proof omitted.]

\vspace{0.1in}

      \item Prove $\vdash (A \wedge \neg A) \to B$. You may use the deduction theorem and theorems L1 -- L15.

\vspace{0.1in}

Before we begin our proof, let's consider what this theorem ``says''.
$A \wedge \neg A$ says that both $A$ and not $A$ hold. This means $A$ is both
true and false (which is impossible). So $A \wedge \neg A$ is always false.
We know ``false implies anything'' is true. That is why this theorem holds.
Now let's prove it formally.

The deduction theorem, will allow us to replace our theoerem with:
``$A \wedge \neg A \vdash B$''.

\noindent Proof:\\
\begin{tabular}{clcl}
1. & $A \wedge \neg A$ & \hspace*{0.5in} & Assumption \\
2. & $\neg(A \to \neg \neg A)$ & & Unabbreviate Line 1 \\
3. & $A \to \neg \neg A$ & & Theorem L12 with $B:=A$ \\
4. & $\neg(A \to \neg \neg A) \to ((A \to \neg \neg A) \to B)$ & & Theorem L15 with $A:=(A \to \neg \neg A)$ and $B:=B$ \\
5. & $(A \to \neg \neg A) \to B$ & & M.P. Lines 2 and 4 \\
6. & $B$ & & M.P. Lines 3 and 5 
\end{tabular}
Therefore, we have established that $(A \wedge \neg A) \vdash B$. So
by the deduction theorem, $\vdash (A \wedge \neg A) \to B$ holds as well.

\vspace{0.2in}

      \item Prove $A \vee B \vdash B \vee A$. You may use the deduction theorem and theorems L1 -- L12.

\vspace{0.1in}

This will show that the ``or'' operator is commutative. 

First, unabbreviating $B \vee A$, gives us $\neg B \to A$, so we need to
prove $A \vee B \vdash \neg B \to A$. The deduction theorem will allow us to
replace this with $A \vee B, \neg B \vdash A$ (this statement says that
if $A$ or $B$ is true and $B$ is false, then $A$ must be true -- which seems
quite reasonable). Again, unabbreviating $A \vee B$, gives us $\neg A \to B$.
So our goal is to prove: ``$\neg A \to B, \neg B \vdash A$''.

\noindent Proof:\\
\begin{tabular}{clcl}
1. & $(\neg A \to \neg \neg B) \to (\neg B \to A)$ & \hspace*{0.5in} & Theorem L10 with $A:=\neg B$ and $B:=A$ \\
2. & $B \to \neg \neg B$ & & Theorem L12 \\
3. & $\neg A \to B$ & & Assumption \\
4. & $\neg A \to \neg \neg B$ & & Theorem L8 with $A:=\neg A$, $B:=B$, and $C:=\neg\neg B$ \\
5. & $\neg B \to A$ & & M.P. lines 1 and 4 \\
6. & $A$ & & M.P. assumption and line 5
\end{tabular}

Therefore, $\neg A \to B, \neg B \vdash A$ which abbreviates $A \vee B, \neg B \vdash A$. Applying the deduction theorem, we have that $A \vee B \vdash \neg B \to A$ which in turn abbreviates $A \vee B \vdash B \vee A$.

\vspace{0.2in}

   \end{enumerate}

\noindent
{\bf \large 7. (15 points)}  A few more proofs in K.  Prove (at least) 5 of the theorems K27 -- K37.

\vspace{0.1in}

{}[Textbook theorems' proofs omitted.]

\vspace{0.1in}

\noindent
{\bf \large 8. (12 points)}  More proofs !?!
   \begin{enumerate}[(a)]
      \item Prove that $1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n! = (n+1)! - 1$ for all positive integers $n$.

\vspace{0.1in}

\begin{description}
\item[Base Case] We need to establish this equation when $n=1$ (the smallest positive integer). When $n=1$ the left hand side reads $1 \cdot 1! = 1$ and
the right hand side reads $(1+1)! - 1 = 2!-1=1$. Therefore, the base case
holds.
\item[Inductive Step] We need to show that if $1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n! = (n+1)! - 1$, then $1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n! + (n+1) \cdot (n+1)! = (n+2)! - 1$. So we assume that $1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n! = (n+1)! - 1$ holds (this is our inductive hypothesis). Then 
$1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n! + (n+1) \cdot (n+1)! = \dots$

\vspace{-0.2in}

\begin{eqnarray*}
& = & [1 \cdot 1! + 2 \cdot 2! + \cdots n \cdot n!] + (n+1) \cdot (n+1)! \\
& = & [(n+1)! - 1] + (n+1) \cdot (n+1)! \qquad \mbox{(using our inductive hypothesis)}\\
& = & 1 \cdot (n+1)! + (n+1) \cdot (n+1)! - 1 = (n+2)(n+1)! - 1 = (n+2)! - 1
\end{eqnarray*}
So we have shown that if this equation holds for
some value $n$, then it also holds for $n+1$.
\end{description}

We have established the base case and inductive step. Therefore, by induction
the equation holds for all positive integers.

\vspace{0.1in}

      \item Let $n$ be an odd integer. Prove that $n^2-1$ is a multiple of 4.

\vspace{0.1in}

$n$ is odd implies that there exists an integer $k$ such that $n=2k+1$.
Then $n^2-1 = (2k+1)^2-1 = 4k^2+4k+1-1 = 4k^2+4k = 4k(k+1)$ which is evidently
a multiple of 4. 

\vspace{0.1in}

{\it Remark:} More can be said. Notice that one if $k$ is odd, then $k+1$ is even (and vice-versa). Thus either $k$ or $k+1$ is even. Therefore, $k(k+1)$ is even (even times odd is even). Thus $n^2-1$ is 4 times an even number, so it's a multiple of 8.

\vspace{0.1in}

      \item Let $r$ be an irrational number and $m$ be an integer. Prove that $mr$ is irrational.

\vspace{0.1in}

This problem is flawed. If $m=0$, then $mr=0$ (which is rational). I meant to say ``\dots and $m$ be a non-zero integer.''

We will use ``contradiction''. Suppose that $mr$ is rational, say, $mr=p/q$ for some integers $p$ and $q$. Then $r=p/(mq)$ which is rational since $mq$ is an
integer (an integer times an integer is an integer). This is a contradiction
since $r$ is irrational. Therefore, our assumption that $mr$ is rational must
be false. Thus $mr$ is irrational.

\vspace{0.1in}

      \item Let $a$, $b$, and $c$ be integers. Show that if $a \,\Big|\, b$ and $b \,\Big|\, c$, then $a \,\Big|\, c$.

\vspace{0.1in}

Since $a$ divides $b$, there exists an integer $k$ such that $ak=b$. Also, since
$b$ divides $c$, there exists an integer $\ell$ such that $b\ell=c$. Therefore,
$c = b\ell = (ak)\ell = a(k\ell)$ where $k\ell$ is an integer. So $c$ is an integer multiple of $a$ and thus $a$ divides $c$.

   \end{enumerate}

\end{document}
