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