\documentclass[12pt]{article}

%Packages Used%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts,setspace}
\usepackage{fullpage}
\usepackage[pdftex,pagebackref,hypertexnames=false, colorlinks, citecolor=black, linkcolor=blue, urlcolor=red]{hyperref}
\usepackage{comment}
\usepackage{enumitem}
\usepackage[margin=1in]{geometry}


\setlength{\abovedisplayskip}{3mm}
\setlength{\belowdisplayskip}{3mm}
\setlength{\abovedisplayshortskip}{0mm}
\setlength{\belowdisplayshortskip}{2mm}
\setlength{\baselineskip}{12pt}
\setlength{\normalbaselineskip}{12pt}

\newcommand{\blank}{\underline{~~~~~~~~~}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\cP}{\mathcal{P}}

\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bzero}{\mathbf{0}}
\DeclareMathOperator{\Nul}{Nul}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\tr}{tr}

\renewcommand{\And}{\wedge}
\newcommand{\Or}{\vee}
\newcommand{\Implies}{\Rightarrow}
\newcommand{\Not}{\sim}



\normalbaselines
\pagestyle{empty}
\raggedbottom
\begin{document}


\begin{center}
{
Math 2106-D, Foundations of Mathematical Proof \\
EXAM 1
\\
September 21, 2017
}
\end{center} 

\begin{center}SOLUTIONS \end{center}

All problems are worth 10 points. To obtain full credit, you {\bf must} show your work and write clearly in complete sentences. No calculators or other electronic devices are allowed.

\begin{enumerate}
\item Suppose that $P$, $Q$, and $R$ are logical statements. Fill out a complete truth table to show that $\sim(P\lor Q\lor R)$ is logically equivalent to $(\sim P)\land(\sim Q)\land(\sim R)$.

{\bf Solution:}
We first fill in the following truth table:

\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$P$ & $Q$& $R$ & $\sim P$& $\sim Q$& $\sim R$&  $(\sim P)\land(\sim Q)\land(\sim R)$& $P\lor Q\lor R$ &  $\sim(P\lor Q\lor R)$
\\
\hline 
$T$ & $T$ & $T$ &$F$&$F$&$F$&$F$&$T$&$F$
\\
\hline 
$T$ & $T$ & $F$ &$F$&$F$&$T$&$F$&$T$&$F$
\\
\hline 
$T$ & $F$ & $T$ &$F$&$T$&$F$&$F$&$T$&$F$
\\
\hline 
$T$ & $F$ & $F$ &$F$&$T$&$T$&$F$&$T$&$F$
\\
\hline 
$F$ & $T$ & $T$ &$T$&$F$&$F$&$F$&$T$&$F$
\\
\hline 
$F$ & $T$ & $F$ &$T$&$F$&$T$&$F$&$T$&$F$
\\
\hline 
$F$ & $F$ & $T$ &$T$&$T$&$F$&$F$&$T$&$F$
\\
\hline 
$F$ & $F$ & $F$ &$T$&$T$&$T$&$T$&$F$&$T$
\\
\hline
\end{tabular}

\noindent
As the $7$-th and $9$-th columns have the same entries for every possible truth value of the variables $P,Q,R$, the corresponding statements are logically equivalent, as claimed.

\item
Suppose that $x\in\mathbb R$. Show that if $x^2$ is irrational, then $x$ is also irrational.

{\bf Solution:}

We will show this using the contrapositive. Thus, suppose $x$ rational. Then we can write $x=a/b$ for integers $a$ and $b$ with $b\neq0$. Squaring this gives $x^2=a^2/b^2$, which is a ratio of two integers (with non-zero denominator), and thus rational. This establishes the contrapositive, and hence the original claim is true.

\item Show that if $A$ and $B$ are sets whose power sets are equal, that is, for which $\mathcal P(A)=\mathcal P(B)$, then we have $A=B$. (Hint: Use the fact that any set is a subset of itself.)

{\bf Solution:}

Suppose that $\mathcal P(A)=\mathcal P(B)$. Then since any set is a subset of itself, we have $A\subseteq A$. In terms of the power set, this means that $A\in\mathcal P(A)=\mathcal P(B)$. Again using the definition of power sets, $A\subset B$. By the same reasoning, $B\subseteq A$. Hence, $A=B$, as desired.


\item Show that there are infinitely many prime numbers of the form $6n+5$ for $n\in\mathbb N\cup\{0\}$ (Hint: Modify Euclid's proof that there are infinitely many primes. Instead of considering the number $N=p_1\cdot\ldots\cdot p_k+1$ as in Euclid's proof, consider the number $N=6\cdot p_1\cdot\ldots\cdot p_k-1$). 

Suppose that there are only finitely many primes of the form $6n+5$. Then we can list them as $p_1,\ldots,p_k$, where $k$ is the number of such primes. Consider the number $N=6\cdot p_1\cdot\ldots\cdot p_k-1$. Then no prime $p\in\{p_1,\ldots, p_k\}$ divides $N$, as if it did, then $p|(6\cdot p_1\cdot\ldots\cdot p_k)$ and $p|N$. But then $p$ also divides the difference of these two numbers, which is $1$, and this isn't possible for an integer which is at least $2$.

Thus, $N$ is not divisible by any prime on the list of {\it all} primes which are $5$ modulo $6$. Combining with the Fundamental Theorem of Arithmetic, we find that $N$ factors as a product of primes $q_1,\ldots,q_{\ell}$ which are all congruent to $0,1,2,3,$ or $4$ modulo $6$. If an integer is congruent to $0,2$, or $4$ modulo $6$, then it is even, and the only even prime is $2$. Similarly, the only prime which is $3$ mod $6$ is $3$ itself (as any number which is $3$ mod $6$ is divisible by $3$). Thus, 
$N=q_1\cdot\ldots\cdot q_{\ell}\equiv1\cdot\ldots\cdot1\cdot2^{m}3^{n}\pmod6$, where $m,n\geq0$ are the powers of $2$ and $3$ appearing in the prime factorization of $N$. Thus, $N$ is congruent to $0$ (if both $m,n>0$), $1$ (if $m=n=0)$), $2$ (if $n=0$ and $m$ is odd), $3$ (if $m=0$ and $n>0$), or $4$ (if $n=0$ and $m$ is positive and even), modulo $6$. In particular, $N$ can't be congruent to $5$ mod $6$. But from the definition of $N$, we find that $N\equiv-1\equiv5\pmod6$. This is a contradiction. Thus, there are infinitely many primes of the form $5n+6$. 

\item Show if $x$ is a positive real number, then 
\[
x+\frac 4x\geq4
.
\]

{\bf Solution:}

As $x$ is positive, we can multiply both sides of the inequality to find that $x+\frac 4x\geq4$ if and only if $x^2+4\geq4x$, which is equivalent to $x^2-4x+4\geq0$. 
Noting that $x^2-4x+4=(x-2)^2$, and that the square of any real number is positive, we find that the last inequality holds for all $x$. As this inequality is true for positive $x$ if and only if $x+\frac 4x\geq4$ (both of the reductions to this inequality were if and only if statements), this holds for all positive $x$ as well. 

\end{enumerate}










\end{document}




 





