\documentclass[12pt]{article}

%Page set up
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\textheight}{9in}

\newtheorem{thm}{Theorem}
\newtheorem{ex}[thm]{Example}
 %Packages
\usepackage{amssymb,amsmath,pstricks}
\usepackage{array}
\usepackage{color}
\usepackage{colortbl,xcolor}
\usepackage{fancybox,framed}
\usepackage{url}

\renewenvironment{framed}[1][\hsize]
  {\MakeFramed{\hsize#1\advance\hsize-\width \FrameRestore}}%
  {\endMakeFramed}

% Start document
\setcounter{page}{1}
\begin{document}
\begin{center}
{\Large \bf Proofs} \\
(Establishing the Truth of Propositions) \\
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rules of inference
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Rules of inference} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rules of inference
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{What is a rule of inference?}

In mathematical logic, an \textbf{argument} or \textbf{proof} is a sequence that starts from a list of statements called \emph{premises}, \emph{assumptions}, or \emph{hypotheses}
and returns a \emph{conclusion}.

\vspace{0.1in}
\noindent Such a proof is only valid when the sequence of rules needed to validate the conclusion (i.e. to show that it is true) is complete and sound.

\vspace{0.1in}
\noindent Let us use an example. Assume that we are given the following hypotheses,
\begin{center}
\textit{``If John is a poet, then he is poor"}\\
\textit{``John is a poet"}
\end{center}
and that we know that those premises are true. Can we conclude that \textit{``John is poor"}? In other words, can we say that:
\begin{center}
\textit{((If John is a poet then he is poor) and (John is a poet)) then John is poor.}
\end{center}

\noindent Let us express the same phrase using the language of logic. We first define the two propositions
\begin{center}
$p: $ John is a poet\\
$q: $ John is poor
\end{center}

\noindent The phrase becomes then
\begin{equation*}
((p\rightarrow q) \land p)\rightarrow q 
\end{equation*}

\vspace{0.1in}
\noindent We want to know if this statement is a ``valid", i.e. that it is always true,namely a tautology. We use a truth table to show that it is indeed the case:

\begin{center}
\begin{tabular}{| c | c | c | c | c |}
\hline
$p$ & $q$ & $p\rightarrow q$ & $(p\rightarrow q)\land p$ & $((p\rightarrow q)\land p)\rightarrow q$\\ 
\hline
T & T & T & T & \textcolor{red}{T}\\ 
T & F & F & F & \textcolor{red}{T}\\ 
F & T & T& F & \textcolor{red}{T}\\ 
F & F & T & F& \textcolor{red}{T}\\ 
\hline
\end{tabular}
\end{center}
This ``valid" statement ($((p\rightarrow q)\land p)\rightarrow q$) is called a \textbf{rule of inference}. It is usually written as
\begin{center}
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \to q$ \\
			\arrayrulecolor{blue} & $p$ \\
			\cline{2-2}
    			$\therefore$         & $q$ \\
  	\end{tabular}
\end{center}
where the symbol $\therefore$ can be interpreted as \emph{therefore}. 

Do we have to build a truth table for all arguments that we try to validate? Thankfully no, as we can usually follow one of the rules of inference that have been established in logic. A list of such rule is provided in the next subsection.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% List of Rules of inference
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Rules of inference}

\vspace{0.1in}
\begin{center}
	\begin{tabular}{c | c | c}
	\textbf{Rule} & \textbf{Corresponding tautology} & \textbf{Name} \\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \to q$ \\
			\arrayrulecolor{blue} & $p$ \\
			\cline{2-2}
    			$\therefore$         & $q$ \\
  	\end{tabular} & $((p\rightarrow q)\land p)\rightarrow q$ & Modus Ponens \\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \to q$ \\
			\arrayrulecolor{blue} & $\lnot q$ \\
			\cline{2-2}
    			$\therefore$         & $\lnot p$ \\
  	\end{tabular} & $((p\rightarrow q)\land \lnot q)\rightarrow \lnot p$ & Modus Tollens \\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \to q$ \\
			\arrayrulecolor{blue} & $q \to r$ \\
			\cline{2-2}
    			$\therefore$         & $p \to r$ \\
  	\end{tabular} & $((p \to q) \land (q \to r)) \to (p \lnot r)$ & Syllogism (transitivity) \\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \lor q$ \\
			\arrayrulecolor{blue} & $\lnot p$ \\
			\cline{2-2}
    			$\therefore$         & $q$ \\
  	\end{tabular} & $((p \lor q) \land \lnot p) \to q$ & Disjunctive Syllogism\\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p$ \\
			\arrayrulecolor{blue} \cline{2-2}
    			$\therefore$         & $p \lor q$ \\
  	\end{tabular} & $p \to (p \lor q) $ & Addition\\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p \land q$ \\
			\arrayrulecolor{blue} \cline{2-2}
    			$\therefore$         & $p$ \\
  	\end{tabular} & $ (p \land q) \to p$ & Simplification\\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p$ \\
			\arrayrulecolor{blue} & $q$ \\
			\cline{2-2}
    			$\therefore$         & $p \land q$ \\
  	\end{tabular} & $((p)\land(q))\to (p\land q)$ & Conjunction \\
	&&\\
	\hline
	&&\\
	\begin{tabular}{c@{\,}l@{}} 
                         & $p\lor q$ \\
			\arrayrulecolor{blue} & $\lnot p \lor r$ \\
			\cline{2-2}
    			$\therefore$         & $q \lor r$ \\
  	\end{tabular} & $((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$ & Resolution \\
	&&\\
	\hline
	\end{tabular}
\end{center}

\begin{framed}
The rules of inference give us the tools to validate a conclusion from a set of hypotheses
\end{framed}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% List of Rules of inference
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Examples}

\subsubsection*{Example 1}

\textit{Let us consider the following assumptions:}
\begin{itemize}
\item [a)] \textit{If it rains today, then we will go on a canoe trip}
\item [b)] \textit{If we do not go on a canoe trip today, then we will go on a canoe trip tomorrow}
\end{itemize}
\textit{Can we conclude that}
\begin{center}
\textit{If it rains today, then we will go on a canoe trip tomorrow?}
\end{center}

\vspace{0.1in}
\noindent \textbf{\textit{Proof:}}

\vspace{0.1in}
\noindent Let us define the propositions:
%\begin{center}
\begin{align*}
p: & \text{ It rains today} \\
q: & \text{ We will not go on a canoe trip today}\\
r: & \text{ We will go on a canoe trip tomorrow}
\end{align*}
%\end{center}
\noindent Then
\begin{center}
\begin{tabular} {c | c}
\textbf{Step} & \textbf{Reason} \\
\hline
$p \to q$ & Hypothesis (a) \\
$q \to r$ & Hypothesis (b) \\
\cline{1-1}
$\therefore p \to r$ & Transitivity (rule of inference) \\
\hline
\end{tabular}
\end{center}

\subsubsection*{Example 2}

\textit{Let us consider a more complex set of assumptions:}
\begin{itemize}
\item [a)] \textit{It is not sunny today and it is colder than yesterday}
\item [b)] \textit{If we go swimming then it is sunny}
\item [c)] \textit{If we do not go swimming, then we will have a barbecue}
\item [d)] \textit{If we have a barbecue, then we will be home by sunset}
\end{itemize}
\textit{Can we conclude that}
\begin{center}
\textit{We will be home by sunset?}
\end{center}

\vspace{0.1in}
\noindent \textbf{\textit{Proof:}}

\vspace{0.1in}
\noindent Let us define the propositions:
%\begin{center}
\begin{align*}
p: & \text{ It is sunny today} \\
q: & \text{ It is colder than yesterday}\\
r: & \text{ We will go swimming} \\
s: &\text{ We will have a barbecue} \\
t: &\text{ We will be home before sunset}
\end{align*}
%\end{center}
\noindent Then
\begin{center}
\begin{tabular} {l | c | l}
\textbf{Line \#} & \textbf{Step} & \textbf{Reason} \\
\hline
1 & $\lnot p \land q$ & Hypothesis (a) \\
2 & $\lnot p$ & Simplification rule applied to step 1 \\
3  &$r \to p$ & Hypothesis (b) \\
4 & $\lnot r$ & Modus Tollens rule applied to steps 2 and 3 \\
5 &$\lnot r \to s $ & Hypothesis (c) \\
6 & $s$ & Modus Ponens rule applied to steps 4 and 5 \\
7 & $s \to t$ & Hypothesis (d) \\
8 & $\therefore t$ & Modus Ponens applied to steps 6 and 7\\
\hline
\end{tabular}
\end{center}

\subsubsection*{Example 3}

\textit{Let $p_1$, $p_2$, and $r$ be three propositions. }

\noindent \textit{Show that}
\begin{equation*}
 ((p_1\rightarrow q)\land (p_2 \rightarrow q))\rightarrow ((p_1\lor p_2)\rightarrow q)
 \end{equation*}
\textit{ is a tautology.}
 
 \vspace{0.1in}
\noindent \textbf{\textit{Proof:}}


\vspace{0.1in}
\noindent Our hypothesis are that:
%\begin{center}
\begin{align*}
\text{a) } & p_1 \to q \\
\text{b) } & p_2 \to q
\end{align*}
\noindent are both true. Then
\begin{center}
\begin{tabular} {l | c | l}
\textbf{Line \#} & \textbf{Step} & \textbf{Reason} \\
\hline
1 & $p_1 \to q$ & Hypothesis (a) \\
2 & $\lnot p_1 \lor q$ & Property of implications \\
3  &$p_2 \to q$ & Hypothesis (b) \\
4 & $\lnot p_2 \lor q$ & Property of implications \\
5 & $(\lnot p_1 \lor q) \land (\lnot p_2 \lor q) $ & Conjunction rule applied to steps 2 and 4 \\
6 &$(\lnot p_1 \land \lnot p_2) \lor q $ & Distributivity law \\
7 & $(\lnot(p_1 \lor p_2)) \lor q$ & De Morgan's law \\
8 & $(p_1\lor p_2)\to q$ & Property of implications\\
\hline
\end{tabular}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Methods of proof
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Methods of proof} 

\begin{framed}[\textwidth]
\noindent {\bf Definition} \\
A theorem is a statement that can be shown to be always true
\end{framed}

\noindent We demonstrate that a theorem is true with a sequence of statements that forms an argument, or proof, as described in the previous section. Possible elements in such arguments / proofs include:

\begin{center}
\begin{tabular}{l | c}
\textbf{Statement} & \textbf{Type} \\
\hline
& \\
\begin{tabular}{@{}l@{}}Axioms, postulates \\ Proved theorems \end{tabular} & Underlying assumptions \\
& \\
\hline
& \\
Hypotheses / premises & \\
& \\
\hline
& \\
Body of the proof & Rules of inference \\
& \\
\hline
& \\
$\therefore$ Conclusion &\\
& \\
\hline
\end{tabular}
\end{center}

\begin{framed}
\noindent \textit{In many of the examples of proof shown below, we will use the concepts of odd and even for integers. Those concepts are defined here:}

\vspace{0.1in}
\noindent {\bf Definition 1} \\
``An integer number $n$ is even if and only if it is divisible by 2"\\
or \\
``An \textbf{integer number} $n$ is even if and only if there exists an \textbf{integer number} $k$ such that $n = 2k$".

\vspace{0.1in}
\noindent {\bf Definition 2} \\
``An integer number $n$ is odd if and only if it is not divisible by 2"\\
or \\
``An \textbf{integer number} $n$ is odd if and only if there exists an \textbf{integer number} $k$ such that $n = 2k+1$".
\end{framed}

\break
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proofs for implications}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Methods of proof for implications}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $p$ and $q$ be two propositions. Suppose that we wish to prove the implication $p \to q$. To understand the strategies that are available to us, it is useful the recall the truth table for an implication:

\vspace{0.1in}
\begin{center}
\begin{tabular}{| c | c | c |}
\hline
$p$ & $q$ & $p\rightarrow q$\\ 
\hline
T & T & \textcolor{red}{T}\\ 
T & F & \textcolor{red}{F}\\ 
F & T & \textcolor{red}{T}\\ 
F & F & \textcolor{red}{T}\\ 
\hline
\end{tabular}
\end{center}

The possible strategies are then:

\vspace{0.1in}

\noindent$\fbox{\rule[-0pt]{0pt}{10pt}\textbf{1. Trivial proof of $P\to Q$:} }$

\vspace{0.1in}
If we know that $Q$ is true, then $P\to Q$ is always true, independent of the truth value of $Q$

\vspace{0.1in}
\begin{center}
\doublebox{
\begin{minipage}{3in}
\begin{center}
Prove $P \to Q$ is true: \\
We know $Q$ is true \\
$\therefore P \to Q$ is true
\end{center}
\end{minipage}
}
\end{center}

\vspace{0.1in}
\noindent$\fbox{\rule[0pt]{0pt}{10pt}\textbf{2. Vacuous proof of $P\to Q$:} }$

\vspace{0.1in}
If $P$ is false, then $P \to Q$ is always true, regardless of the truth value of $Q$

\vspace{0.1in}
\begin{center}
\doublebox{
\begin{minipage}{3in}
\begin{center}
Prove $P \to Q$ is true: \\
We know $P$ is false \\
$\therefore P \to Q$ is true
\end{center}
\end{minipage}
}
\end{center}

\vspace{0.1in}
\noindent$\fbox{\rule[0pt]{0pt}{10pt}\textbf{3. Direct proof of $P\to Q$:} }$

\vspace{0.1in}
We assume $P$ (i.e. that $P$ is true), and then we use the rules of inference, axioms, definitions, and logical equivalences to prove that $Q$ is true.

\vspace{0.1in}
\begin{center}
\doublebox{
\begin{minipage}{3in}
\begin{center}
Assume $P$ \\
$\ldots$ \\
{[Logical deductions]} \\
$\ldots$ \\
Therefore $Q$.
\end{center}
\end{minipage}
}
\end{center}

\vspace{0.1in}

\noindent$\fbox{\rule[0pt]{0pt}{10pt}\textbf{4. Indirect proof of $P\to Q$ (\textit{also called proof by contrapositive}):} }$

\vspace{0.1in}
Remember that an implication $p \to q$ is logically equivalent to its contrapositive, namely $\lnot q \to \lnot p$. We use then a direct proof of this contrapositive: we assume $\lnot q$, and we use an argument to show that $\lnot p$. 

\vspace{0.1in}
\begin{center}
\doublebox{
\begin{minipage}{3in}
\begin{center}
Assume $Q$ is false \\
$\ldots$ \\
{[Logical deductions]} \\
$\ldots$ \\
Therefore $P$ is false\\
Hence $\lnot Q \to \lnot P$.\\
By contraposition, this proves $P \to Q$
\end{center}
\end{minipage}
}
\end{center}

\vspace{0.1in}

\noindent$\fbox{\rule[0pt]{0pt}{10pt}\textbf{5. Proof by contradiction of $P\to Q$:} }$

\vspace{0.1in}
The implication $p \to q$ is false only when $p$ is true and $q$ is false. We assume that this is possible and we derive a contradiction $F$. 
In logic term, if $S$ is the statement to prove and we have proved that $\lnot S \to F$ is true, based on the truth table above this is only possible if $\lnot S$ is false, namely if $S$ is true.


\vspace{0.1in}
\begin{center}
\doublebox{
\begin{minipage}{3in}
\begin{center}
Assume $P$ is true, AND that $Q$ is false \\
$\ldots$ \\
{[Logical deductions]} \\
$\ldots$ \\
Contradiction \\
Therefore our assumption that $P$ is true and $Q$ is false does not hold\\
By contradiction, this proves $P \to Q$
\end{center}
\end{minipage}
}
\end{center}

\vspace{0.1in}

\noindent$\fbox{\rule[0pt]{0pt}{10pt}\textbf{6. Proof by cases:} }$

\vspace{0.1in}
If the statement $P$ can be separated into a set of cases $P_1 \lor P_2 \ldots \lor P_k$, we prove each of the propositions $P_1 \to Q$, $P_2 \to Q$, $\ldots$, $P_k \to Q$ separately. Note that this comes from the fact that
\begin{equation*}
((p_1 \lor p_2 \ldots \lor p_k) \to q ) \leftrightarrow (p_1 \to q) \land (p_2 \to q) \ldots \land (p_k \to q)
\end{equation*}
is a tautology.

\vspace{0.1in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Examples}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent We will now look at examples for all strategies.

\begin{itemize}
\item[a)] \textbf{Trivial proof of $P \to Q$}

\textit{Prove the statement: If there are 100 students in this class this quarter, then $5^2 = 25$}

\noindent \textbf{Proof}: Let us define $P:$ ``there are 100 students in this class" and $Q:$ ``$5^2 = 25$". We want to show $P \to Q$. This assertion is \emph{trivially} true, since $Q$ is always true, independent of the truth value of $P$ (which may, or may not be true, based on the actual enrollment in the class).

\item[b)] \textbf{Vacuous proof of $P \to Q$}

\textit{Prove the statement: If 9 is a prime number, then $1=2$}

\noindent \textbf{Proof}: Let us define $P:$ ``9 is a prime number" and $Q:$ ``2=1". We want to show $P \to Q$. This assertion is \emph{vacuously} true, since $P$ is false. Note that when $P$ is false, $P \to Q$ is always true, independent of the truth value of $Q$ (in our example, $Q$ is false).

\item[c)] \textbf{Direct proof of $P \to Q$}

\textit{Prove the statement: Let $n$ be an integer. Show that if $n$ is even, then $n^2$ is even.}

\noindent \textbf{Proof}: Let $n$ be an integer and let us define 

\begin{align*}
P(n):&  \text{ $n$ is even} \\
Q(n): & \text{ $n^2$ is even}.
\end{align*}
We want to show $P(n) \to Q(n)$. In a direct proof, we start with the assumption that $P(n)$ is true. As $n$ is an even number, we know (see above) that there exists an integer $k$ such that
\begin{equation*}
n = 2k
\end{equation*}.
We compute $n^2$:
\begin{eqnarray*}
n^2 &=& n \times n \\
&=& (2k) \times (2k) \\
&=& 4 k^2 \\
&=& 2 (2k^2) 
\end{eqnarray*}
Let $k'=2k^2$. As $k$ is an integer, $k'$ is an integer, and $n^2$ is written as $2k'$. Therefore $n^2$ is even, and the statement $P(n) \to Q(n)$ is true.

\item[c)] \textbf{Indirect proof of $P \to Q$}

\textit{Prove the statement: Let $n$ be an integer. Show that if $n^2$ is even, then $n$ is even.}

\noindent \textbf{Proof}: Let $n$ be an integer and let us define 

\begin{align*}
P(n):&  \text{ $n^2$ is even} \\
Q(n): & \text{ $n$ is even}.
\end{align*}
We want to show $p \to q$. In the previous example, we started with $n$ even and we were able to define a property for $n^2$. In this case, however, the situation is more complicated. Let us try a direct proof, and assume that $p$ is true, namely that there exists an integer $k$ (in fact, positive integer) such that
\begin{equation*}
n^2 = 2k
\end{equation*}.
Can we compute $n$ from this equation? This would involve taking a square root, but then we have no guarantee that the result, $\sqrt{2k}$ is an integer. We would then be stuck. We need a different approach and this is when an indirect proof becomes useful. Recall that the implication $P(n) \to Q(n)$ is logically equivalent to its contrapositive, $\lnot Q(n) \to \lnot P(n)$. Let us attempt a direct proof on the contrapositive. We assume that $\lnot Q(n)$ is true, namely that $n$ is not an even number, i.e. $n$ is odd. There exists an integer $k$ such that
\begin{eqnarray*}
n &=& 2k+1 \\
\end{eqnarray*}
We compute $n^2$:
\begin{eqnarray*}
n^2 &=& n \times n \\
&=& (2k+1) \times (2k+1) \\
&=& 4 k^2 +4k + 1\\
&=& 2 (2k^2+2k) +1
\end{eqnarray*}
Let $k'=2k^2+2k$. As $k$ is an integer, $k'$ is an integer, and $n^2$ is written as $2k'+1$. Therefore $n^2$ is even. We have shown that $\lnot Q(n) \to \lnot P(n)$ is true, therefore $P(n) \to Q(n)$ is true.

\item[d)] \textbf{Proof by contradiction}

\textit{Prove the statement: Let $x$ be a real number, $x\ne0$. Show that if $x > 0$, then $x+\frac{1}{x}\ge 2$.}

\noindent \textbf{Proof}: Let $x$ be a non-zero real number and let us define:

\begin{align*}
P(x):& x > 0 \\
Q(x): & a + \frac{1}{x} \ge 2
\end{align*}
We want to show $P(x) \to Q(x)$. We use a proof by contradiction, namely we assume that $P(x)$ is true AND $\lnot Q(x)$ is true.

Since $\lnot Q(x)$ is true, 
\begin{eqnarray*}
x + \frac{1}{x} < 2\\
\end{eqnarray*}.
Since $P(x)$ is true, $x >0$ and we can multiply the two sides of this inequality without changing its direction:
\begin{eqnarray*}
x \times x + \frac{x}{x} &<& 2x\\
x^2 - 2x + 1 &<& 0 \\
(x-1)^2 &<& 0
\end{eqnarray*}.
But $(x-1)^2$ is a square, and a square is always positive. We have reached a contradiction. This means that $P(x) \land \lnot Q(x)$ is a contradiction, and therefore using one of the complement laws, $\lnot P(x) \lor Q(x)$ is true, i.e. $P(x) \to Q(x)$ is true (property of implications).


\item[d)] \textbf{Proof by case}

\textit{Prove the statement: Let $n$ be a real number. Show that if $n$ is an integer, then $3n^2+n+1$ is an odd number.}


\noindent \textbf{Proof}: Let $n$ be a real number and let us define:

\begin{align*}
P(n):& n \text{ is an integer} \\
Q(n): & 3n^2 + n + 1\text{ is an even number.}
\end{align*}
We want to show $P(n) \to Q(n)$. Notice that $Q(n)$ refers to a number being odd, while $P(n)$ contains no information about $n$ being even or odd. However, an integer is either even or odd. Let us define:
\begin{align*}
P_1(n):& n \text{ is an even integer} \\
P_2(n): & n \text{ is an odd number.}
\end{align*}
We have $P(n) = P_1(n) \lor P_2(n)$. We use then a proof by case, namely we show that $P_1(n) \to Q(n)$ and $P_2(n) \to Q(n)$ are both true.
\begin{itemize}
\item [i)] We show $P_1(n) \to Q(n)$ is true 

We use a direct proof. Let us assume that $P_1(n)$ is true, i.e. that $n$ is an even number. There exists an integer number $k$ such that 
\begin{eqnarray*}
n &=& 2k \\
\end{eqnarray*}
We compute $3n^2+n+1$:
\begin{eqnarray*}
3n^2 + n + 1 &=& 3 (2k)(2k) + 2k + 1 \\
&=& 12k^2 + 2k + 1 \\
&=& 2(6k^2 +k) + 1\\
&=& 2k' +1 
\end{eqnarray*}
where we have defined $k'=7k^2+k$. As $k$ is an integer, $k'$ is an integer. Therefore $3n^2 + n + 1$ is odd. $P_1(n) \to Q(n)$ is true.

\item [ii)] We show $P_2(n) \to Q(n)$ is true 

We use a direct proof. Let us assume that $P_2(n)$ is true, i.e. that $n$ is an odd number. There exists an integer number $k$ such that 
\begin{eqnarray*}
n &=& 2k +1 \\
\end{eqnarray*}
We compute $3n^2+n+1$:
\begin{eqnarray*}
3n^2 + n + 1 &=& 3 (2k+1)(2k+1) + 2k+1 + 1 \\
&=& 12k^2 + 12k +3 + 2k + 2 \\
&=& 2(6k^2+7k+2) + 1\\
&=& 2k' +1 
\end{eqnarray*}
where we have defined $k'=6k^2+7k+1$. As $k$ is an integer, $k'$ is an integer. Therefore $3n^2 + n + 1$ is odd. $P_2(n) \to Q(n)$ is true.
\end{itemize}
As $P_1(n) \to Q(n)$ is true and $P_2(n) \to Q(n)$ is true, $P(n)\to Q(n)$ is true.

\end{itemize}

\vspace{0.1in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Choosing a proof technique}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{itemize}
\item \textbf{Trivial / Vacuous proofs:} Those are rare, but it is worth checking first if the premise $P$ is always false, or if the conclusion $Q$ is always true. In those cases, the proof is trivial!
\item \textbf{Direct proof:} In most cases, the best strategy is to try a direct proof first; this is the simplest and most natural proof technique. Only when it fails should you consider other methods of proof.
\item \textbf{Indirect proof:} This is the same as a direct proof, but applied to the contrapositive statement. It is worth considering when the direct proof does not seem to work.
\item \textbf{Proof by contradiction:} A proof by contradiction for an implication is logically more complicated and more prone to errors. It can be effective is some situations, especially if what we want to conclude \emph{does not} have a certain property (such as ``is not rational", ``is not a natural number", ``is not a perfect square"...). 
\item \textbf{Proof by case:} This is appropriate if the problem naturally breaks down into several cases.
\end{itemize}

\vspace{0.1in}
\noindent \textbf{\textit{A special note on proof by contradiction}}

\vspace{0.1in}
Most proofs mentioned above are specific to implications. A notable exception is the proof by contradiction. Let us assume we need to prove that a certain statement $P$ is true, where $P$ does not have to be an implication. If we can find a contradiction $Q$ such that $\lnot P \to Q$, then $\lnot \to F$ is true, which is only possible if $\lnot P$ is false, namely if $P$ is true. 

\vspace{0.1in}
\noindent \textit{\textbf{Example:} Show that $P: \sqrt{2}$ is irrational.}

\vspace{0.1in}
\noindent \textbf{Proof.} Let us assume that $P$ is false, i.e. that $\sqrt{2}$ is rational. There exists a pair $(a,b)$ of integers, with $b\ne 0$, such that
\begin{equation*}
\sqrt{2} = \frac{a}{b}
\end{equation*}
We can safely assume that $a$ and $b$ do not have any common factor. If such a common factor were to exist, it can be factored out.

After multiplication by $b$ and squaring:
\begin{eqnarray*}
a &=& \sqrt{2} b \\
a^2 &= &2 b
\end{eqnarray*}
Since $b$ is an integer, $a^2$ is even. We have seen above (see example of indirect proof) that this implies that $a$ \textbf{is even}. There exists an integer $k$ such that
\begin{eqnarray*}
a &=& 2k 
\end{eqnarray*}
Replacing in the equation above that defines $a^2$, we get:
\begin{eqnarray*}
a^2 &=& 2 b \\
4 k^2 &=& 2b \\
2k^2 &=& b
\end{eqnarray*}
Since $k^2$ is an integer, $b$ \textbf{is even.} As both $a$ and $b$ are even, they have a common factor, $2$. However, we stated that $a$ and $b$ do not have a common factor: we have reached a contradiction. Therefore the assumption that $\sqrt{2}$ is rational is false, and therefore $\sqrt{2}$ is irrational.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Proofs and quantifiers
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proofs and quantifiers} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existence proofs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Many theorems are assertions that (at least) one object $x$ of a particular type $\mathbb{D}$ satisfies a given predicate $P$ :
\begin{equation*}
	\exists x \in \mathbb{D}, P(x)
\end{equation*}
To prove such theorems, we do not need to find all values of $x$ that satisfy $P(x)$; we just needs to show the existence of one. There are two types of such existence proof:
\begin{itemize}
\item [a)] \textbf{Constructive proofs:} We find the object $x$ explicitly
\item [b)] \textbf{Non-constructive proofs:} We do not find $x$ explicitly; we only show that there must exists one such $x$.
\end{itemize}

\vspace{0.1in}
\textbf{\textit{Examples:}}
\begin{itemize}
\item [a)] \textbf{Constructive proofs:}

\textit{Prove that there exists a pair of consecutive integers such that one of them is a perfect square and the other is a perfect cube}

\noindent \textbf{Proof.} Let us recall first what is a perfect square and what is a perfect cube:
\begin{itemize}
\item An integer $a$ is a perfect square if there exists an integer $n$ such that $a = n^2$
\item An integer $a$ is a perfect cube if there exists an integer $n$ such that $a = n^3$
\end{itemize}
Let $a$ be one (possible) integer that satisfies the property in the problem. Then we know that there exists an integer $n$ such that $a=n^2$, and an integer $p$ such that $a+1=p^3$ or $a-1=p^3$. We observe that if we set $n=3$ and $p=2$, then $n^2=9$ and $p^3=8$, i.e. the pair $(8,9)$ satisfies the problem. As we only need to find one example, the assertion is true.

\item[b)] \textbf{Non-constructive proofs:} 

\textit{Show that there exists a pair of irrational numbers $a$ and $b$ such that $c = a^b$ is rational}

\noindent \textbf{Proof.} Let us recall first that an irrational number is a number that is not rational. We know one such number: $\sqrt{2}$. Let us define $c=\sqrt{2}^{\sqrt{2}}$. There are then two cases:
\begin{itemize}
\item [a)] $c$ is rational. We are done.
\item [b)] $c$ is irrational. Let us define then $d=c^{\sqrt{2}}$. Note that $d = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{\sqrt{2}\times \sqrt{2}}= \sqrt{2}^2 = 2$, i.e. $d$ is rational,
and we are done.
\end{itemize}
In both cases, we have shown that $a$ and $b$ exists: in the first case, $a=b=\sqrt{2}$, while in the second case, $a=\sqrt{2}^{\sqrt{2}}$ and $b=\sqrt{2}$. We know that one of these two cases is true, therefore the assertion is true. \textit{(We do not know, however, which of the two cases is true, but it does not matter for the proof! This is why this is a non constructive proof.)}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Uniqueness proofs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Some theorems assert the existence of a unique object within a domain $\mathbb{D}$ with a particular property $P$. Proofs of such theorems require two steps:
\begin{itemize}
\item \textbf{Existence}: find $x \in \mathbb{D}$ such that $P(x)$ is true
\item \textbf{Uniqueness}: Two options:
	\begin{itemize}
	\item For $y \in \mathbb{D}$, show that if $y\ne x$, then $P(y)$ is false
	\item For $(x,y) \in \mathbb{D}^2$, show that if $P(x)$ and $P(y)$ are both true, then $x=y$
	\end{itemize}
\end{itemize}

\vspace{0.1in}
\textbf{\textit{Example:}}

\vspace{0.1in}
\textit{Let $a$ be a real number not equal to zero, and let $x$ and $b$ be two real numbers. Show that there is a unique solution $x$ to the equation $ax+b=0$.}

\vspace{0.3in}
\noindent \textbf{Proof.}
\begin{itemize}
\item [a)] \textbf{Existence}

A solution $x$ to the equation satisfies,
\begin{eqnarray*}
ax+b &=& 0 \\
ax &=& -b \\
x &=& -\frac{b}{a}
\end{eqnarray*}
as $a \ne 0$. Therefore $x=-\frac{b}{a}$ is one solution to the equation. This proves the existence.

\item [b)] \textbf{Uniqueness}

Let $x$ and $y$ be two real numbers that are solutions to the equation. Then $ax+b=0$ and $ay+b=0$. Therefore,
\begin{eqnarray*}
ax+b &=& ay+b \\
ax &=& ay \\
x &=& y
\end{eqnarray*}
again as $a \ne 0$. This proves the uniqueness.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof by counter example}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To show that an expression of the form $[ \forall x \in \mathbb{D}, P(x) ]$ is false, it is enough to find one value of $x \in \mathbb{D}$ such that $P(x)$ is false.
This value is called a counter-example.


\vspace{0.1in}
\textbf{\textit{Example:}}

\vspace{0.1in}
\textit{Prove or disprove that}
\begin{equation*}
\forall n \in \mathbb{N}, 2^n+1 \text{ is prime}
\end{equation*}

\noindent \textbf{Proof.}

\noindent We try different values of $n \in \mathbb{N}$:
\begin{itemize}
\item [$n=1:$] $2^n+1 = 3$ which is prime
\item [$n=2:$] $2^n+1 = 5$ which is prime
\item [$n=3:$] $2^n+1 = 9$ which is not prime
\end{itemize}

Therefore the proposition is not true.




\end{document}