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

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.250in}
\setlength{\evensidemargin}{-0.250in}
\setlength{\topmargin}{-0.50in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.5in}
\setlength{\textwidth}{7in}

\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}}}

\newcommand{\force}{\mbox{$\,$}}

\begin{document}

%\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 2510} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill February $27^{\mathrm{th}}$, 2015}

\vspace{0.3in}

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

\begin{description}
   \item[\large 1. (10 points)] Consider theorem L15: $\vdash \neg A \to (A \to B)$
\begin{enumerate}[(a)]

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

$$ \force \hspace*{-0.5in}
\begin{array}{cccccc}
\neg & A & \to & (A & \to & B)\\
      & T &    & T &     & T\\
      & F &    & F &    & T\\
      & T &    & T &    & F\\
      & F &    & F &    & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{cccccc}
\neg & A & \to & (A & \to & B)\\
  F    & T &    & T &  T   & T\\
  T    & F &    & F &  T  & T\\
  F    & T &    & T &  F  & F\\
  T    & F &    & F &  T & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{cccccc}
\neg & A & \to & (A & \to & B)\\
  F    & T & {\bf T}   & T &  T   & T\\
  T    & F & {\bf T}   & F &  T  & T\\
  F    & T & {\bf T}   & T &  F  & F\\
   T   & F & {\bf T}   & F &  T & F\\
\end{array}
$$

   \item Prove L15 in system L. [You may use the deduction theorem and theorems L1 -- L14.]\\ {\it Hint:} I have a quick proof using the deduction theorem and lemmas L5 and L10 in mind.

   \medskip
   [Textbook theorem's proof omitted.]

\medskip


\end{enumerate}

   \item[\large 2. (10 points)] Still in System L\dots

\begin{enumerate}[(a)]
\item Is ``$A \vee B \vdash A$'' provable in $L$? What about ``$A \vdash A \vee B$''? Justify your answer(s).

\medskip
We know that the theorems of L (the statements provable in L) are exactly the tautologies. In particular, the ``soundness'' theorem for system L says that only tautologies can be proven in L. The ``completeness'' theorem for system L says that every tautology can be proven in L.  Hence, to determine whether ``$A \vee B \vdash A$'' and ``$A \vdash A \vee B$'' are provable in L we simply need to check to see if each statement is a tautology. Recall that $C \vdash D$ is equivalent to $\vdash C \to D$.
$$
\begin{array}{ccccc}
(A & \vee & B) & \to & A \\
T &    & T &     & T\\
F &    & T &    & F\\
T &    & F &    & T\\
F &    & F &    & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{ccccc}
(A & \vee & B) & \to & A \\
T &  T & T &     & T\\
F &  T  & T &    & F\\
T &  T  & F &    & T\\
F &  F  & F &    & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{ccccc}
(A & \vee & B) & \to & A \\
T &  T & T &    {\bf T} & T\\
F &  T  & T &   {\bf F} & F\\
T &  T  & F &   {\bf T} & T\\
F &  F  & F &   {\bf T} & F\\
\end{array}
$$
The above truth table shows that ``$(A \vee B) \to A$'' is not a tautology and hence, by soundness, not a theorem of L. We may conclude that ``$A \vee B \vdash A$'' {\bf is not} provable in L.

$$
\begin{array}{ccccc}
A & \to & (A & \vee & B)\\
T &    & T &     & T\\
F &    & F &    & T\\
T &    & T &    & F\\
F &    & F &    & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{ccccc}
A & \to & (A & \vee & B)\\
T &    & T &   T  & T\\
F &    & F &   T & T\\
T &    & T &   T & F\\
F &    & F &   F & F\\
\end{array}
\quad \Longrightarrow \quad
\begin{array}{ccccc}
A & \to & (A & \vee & B)\\
T &  {\bf T}  & T &   T  & T\\
F &  {\bf T}  & F &   T & T\\
T &  {\bf T}  & T &   T & F\\
F &  {\bf T}  & F &   F & F\\
\end{array}
$$
The above truth table shows that ``$A \to (A \vee B)$'' is a tautology and hence, by completeness, a theorem of L. We may conclude that ``$A \vdash A \vee B$'' {\bf is} provable in L.

%\newpage

\item Here is my proof of theorem L7:  $A \to (B \to C) \vdash B \to (A \to C)$\dots

\vspace{0.05in}

\begin{enumerate}[1:]
   \item $A \to (B \to C)$ \hfill \parbox{3.2in}{\underline{1: Given}}

   \item $B \to (A \to (B \to C))$ \hfill \parbox{3.2in}{\underline{2: L5 with $A:=B$ and $B:= A \to (B \to C)$}}

   \item $(A \to (B \to C)) \to ((A \to B) \to (A \to C))$ \hfill \parbox{3.2in}{\underline{3: Axiom 2}}

   \item $(A \to B) \to (A \to C)$ \hfill \parbox{3.2in}{\underline{4: Modus Ponens with Lines 1 and 3}}

   \item $B \to ((A \to B) \to (A \to C))$ \hfill \parbox{3.2in}{\underline{5:  L5 with $A:=B$ and $B:=(A \to B) \to (A \to C)$}}

   \item $B \to (A \to B)$ \hfill \parbox{3.2in}{\underline{6: Axiom 1 with $A:=B$ and $B:=A$}}

   \item $B \to (A \to C)$ \hfill \parbox{3.2in}{\underline{7:  L3 with $A:= B$,  $B:=A \to B$, and $C:= A \to C$}}

\end{enumerate}

{}[Fill in justifications for each line.]

\end{enumerate}


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

    \medskip
    To show this sentence is satisfiable we need to construct two models: one in which the statement holds and one in which the statement fails to hold.

    \smallskip
    {\bf Holds:} Let $P(x)$ be the predicate: $P(x)$ iff $x^2 \ge 0$. Let $\underline{c} = 0$ and $f(y) = 2 + y$. Let $Q(x,y)$ represent equality, {\it i.e.}~$Q(x,y)$ iff $x = y$.\par
    Note that in this model $(\forall x \, P(x))$ is true, as is $(\exists y \, Q(\underline{c},f(y)))$. The latter simply states that ``there exists an interger $y$ such that $f(y) = 2 + y = c$.'' As both the antecedent and consequent of the implication are true, the implication itself, and therefore the statement itself, is true.

    \medskip
    {\bf Does not hold:} Again let $P(x)$ be the predicate: $P(x)$ iff $x^2 \ge 0$. Let $\underline{c} = 0$ and $f(y) = \dfrac2y$. Let $Q(x,y)$ represent equality, {\it i.e.}~$Q(x,y)$ iff $x = y$.\par
    Note that in this model $(\forall x \, P(x))$ is true, but $(\exists y \, Q(\underline{c},f(y)))$ is not. We see this because there is no integer such that $\dfrac2y = \underline{c}=0$. In this case, the antecedent of the implication is true but the consequent is false. Hence, this implication is false.

    \smallskip
    We conclude that this sentence is satisfiable but not logically valid.

\medskip

   \item[\large 4. (10 points)] Proofs in K. You may use the deduction theorem and lower numbered theorems.
   
   \begin{enumerate}[(a)]
      \item Prove theorem K7: $\vdash \forall x (A(x) \to B(x)) \to (\forall x A(x) \to \forall x B(x))$
      
      \medskip
      [Textbook theorem's proof omitted.]
      
      \item Prove theorem K21: $\vdash \exists x A(x) \to \exists x (A(x) \vee B(x))$

      \medskip
      [Textbook theorem's proof omitted.]
   \end{enumerate}   

%\newpage
   \item[\large 5. (10 points)] How about...more proofs?
   
   \begin{enumerate}[(a)]
      \item Use induction to show that $1+2+\cdots+n = \frac{n(n+1)}{2}$ for all positive integers $n$. 
      
      \begin{proof}
      In any proof by induction, we first take care of any base cases. As we are using induction on the positive integers, our base case comes from setting $n = 1$, the first positive integer. So, if $n = 1$ note that
      $$ 1 = \frac{2}{2} = \frac{1(1+1)}2.$$
      Hence, the statement holds for $n = 1$. Now, as our inductive hypothesis, suppose that the statement holds for some $n \geq 1$, {\it i.e.}
      $$1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
      We show it must then hold for $n + 1$ as well:
      \begin{align*}
      1 + 2 + \cdots + n + (n + 1) &= (1 + 2 + \cdots + n) + (n + 1)\\
       &= \frac{n(n+1)}{2} + (n + 1) \mbox{\quad (by the inductive hypothesis)}\\
       &= \frac{n(n+1)}{2} + \frac{2(n+1)}{2}\\
       &= \frac{n(n+1) + 2(n+1)}{2}\\
       &= \frac{(n+1)(n+2)}{2} = \frac{(n+1)((n+1)+1)}{2}
      \end{align*}
      We see now that the statement holds for $n = 1$ and if it holds for $n$, it also holds for $n+1$. Hence, by induction, we have shown that the statement holds for all positive integers $n$.
      \end{proof}
      
      \item Use proof by contradiction to show: For all $x,y \in \mathbb{Z}$, if $xy$ is even, then either $x$ or $y$ is even. 

      \begin{proof}
      For sake of contradiction suppose not, that is that there exists two integers $x$ and $y$ such that their product $xy$ is even and neither $x$ nor $y$ is even. Hence, $x$ and $y$ must be odd, that is, there exist integers $i$ and $j$ such that 
      $$x = 2i + 1 \quad \mbox{ and } \quad y = 2j + 1.$$
      Let us consider their product:
      $$xy = (2i+1)(2j+1) = 4ij + 2i + 2j + 1 = 2(2ij + i + j) + 1 = 2\ell + 1,$$
      where $\ell$ is the integer $2ij + i + j$. We see that $xy$ is odd. But wait, $xy$ is even: we have reached the desired contradiction. Hence, if $xy$ is even we cannot have both $x$ and $y$ odd, that is, either $x$ or $y$ is even.

\medskip

A briefer version of this proof: Suppose $xy$ is even and $x$ and $y$ are odd. But an odd number times an odd number is odd, so $xy$ must be odd (contradiction). Thus either $x$ or $y$ is even.

      \end{proof}
   \end{enumerate}   

\end{description}

%\newpage
   
\vspace{0.5in}
 
\noindent
\parbox{1.5in}{\bf Math 2510} 
\hfill {\Large \bf Test \#1 -- TAKE HOME} \hfill
\parbox{1.5in}{\bf \hfill Due: Mar. $2^{\mathrm{nd}}$, 2015}

\vspace{0.1in}

\noindent {\large\bf Name:} \underline{\hskip .5 truein {\sc\Large\color{red} Answer Key} \hskip .5 truein}\\
You may use notes and your textbook, but no help from other people [except myself and Noah] especially your classmates.
 
\vspace{0.1in} 
   
\begin{description}
   \item[\large 6. (25 points)]  Redo the in-class portion of the test.
   
	See above.

   \item[\large 7. (15 points)]  A few more proofs in K.  Prove (at least) 5 of the theorems K27 -- K37.

	\medskip
    [Textbook theorems' proofs omitted.]

   \item[\large 8. (15 points)]  More proofs !?!
   \begin{enumerate}[(a)]
      \item Prove that $n! > 2^n$ for all integers $n \geq 4$.

		\begin{proof}
		We prove the statement by induction. As a base case, note that when $n = 4$ we have
		$$4! = 4\cdot3\cdot2\cdot1 = 24 > 16 = 2^4.$$
		Now, as our inductive hypothesis, suppose that for some $n \geq 4$ we have 
		$$n! > 2^n.$$
		We show that the same is then true for $n+1$. Consider the following:
		\begin{align*}
		(n+1)! &= (n+1)n!\\
		& > (n+1)2^n \qquad \mbox{(by the inductive hypothesis)}\\
		& > 2\cdot2^n \qquad \quad \;\;\,\, \mbox{(since $n \geq 4$, $n+1 > 2$)}\\
		& = 2^{n+1} 
		\end{align*}
		We see that the statement holds for $n + 1$. Hence, by induction, we have shown that the statement holds for all integers $n \ge 4$.
		\end{proof}

\newpage

      \item Prove that $\sqrt[3]{2}$ is irrational.

		\begin{proof}
		We prove the statement by contradiction. Suppose by way of contradiction that $\sqrt[3]{2}$ is rational, that is, we have
		$$\sqrt[3]{2} = \frac pq$$
		for $p$ and $q$ where $p$ and $q$ have no common divisors. This is saying that $p/q$ is the reduced form of the rational representation of $\sqrt[3]{2}$. Now, as
		$$\sqrt[3]{2} = \frac pq$$
		we must have
		$$2 = \frac{p^3}{q^3}.$$
		This implies that $2q^3 = p^3$, or that $p^3$ is even. Since $p^3$ is even, $p$ must be as well. So there exists and integer $k$ such that $p = 2k$. Note then that 
		$$2q^3 = p^3 \quad \Longrightarrow \quad 2q^3 = (2k)^3 \quad \Longrightarrow \quad q^3 = \frac{8k^3}{2} \quad \Longrightarrow \quad q^3 = 2(2k^3).$$
		We see that $q^3$ is even, and consequently that $q$ is even. This implies that both $p$ and $q$ are divisble by $2$ since they are both even. This contradicts the assumption that $p$ and $q$ shared no common divisors. Hence, we must have that $\sqrt[3]{2}$ is irrational.
		\end{proof}

      \item For any integer $n$, prove that $n^2+2$ is not divisible by 4.

      	\begin{proof}
	      Let $n$ be an integer. If $n$ is odd, {\it i.e.}~there exists a $i$ such that $n = 2i+1$, we have
        $$n^2 + 2 = (2i+1)^2 + 2 = 4i^2 + 4i + 1 + 2 = 2(2i^2 + 2i + 1) + 1 = 2j + 1$$
        where $j$ is the integer $2i^2 + 2i + 1$. We see that in this case $n^2 + 2$ is odd. Now, as $4$ is even, every integer multiple of $4$ must be even as well. That is, any number divisible by $4$ must be even. This implies that for odd integers $n$, $4$ cannot divide $n^2 + 2$ since $n^2+2$ is odd.\par
        Now, this leaves the case in which $n$ is even. So, for some $k$ we have $n = 2k$. Hence, $n^2 + 2 = 4k^2 + 2$. For sake of contradiction, suppose that $4$ {\it does} divide
        $n^2+2$. Then $n^2+2=4\ell$ for some integer $\ell$. But then $4k^2+2=n^2+2=4\ell$ so that $4(k^2-\ell)=2$. This means that $2(k^2-\ell)=1$. Here we have reached a contradiction since $2(k^2-\ell)$, a multiple of $2$, is even whereas $1$ is odd. Thus $n^2+2$ must not be divisible by $4$ if $n$ is even.\par
        This completes the proof.
      	\end{proof}
   \end{enumerate}


\end{description}
\end{document}
