Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\im}{{\mathrm{im}}}
\newcommand{\given}{{\, :\,}}
\newcommand{\hanoi}{\mathrm{hanoi}}
\newcommand{\lcm}{{\mathrm{lcm}}}
\newcommand{\ID}{{\mathrm{ID}}}
\newcommand{\chr}{{\mathtt{chr}}}
\newcommand{\ord}{{\mathtt{ord}}}
\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\seq}[2]{( #1 )_{#2}}
\newcommand{\gr}[1]{\left( #1 \right)}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\size}[1]{\# #1}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\ip}[1]{\left\langle #1 \right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil #1\right\rceil}
\newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}}
\renewcommand{\implies}{\to}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\lxor}{\oplus}
\newcommand{\cP}{\wp}
\newcommand{\pset}{\cP}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\barr}[1]{\overline{#1}}
\newcommand{\sage}{\textsc{Sage}}
\newcommand{\magma}{\textsc{Magma}}
\newcommand{\bob}{\text{Bob}}
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\ah}{\ahat}
\newcommand{\bhat}{\hat{b}}
\newcommand{\abar}{\bar{a}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\todo}[1]{{\color{red} TODO: #1}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\def\dbend{{!!!}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Subsection 1.4.2 Direct proof
Recall that the conditional \(p\implies q\) has the following truth table.
\begin{equation*}
\begin{array}{|*{2}{c|}|*{1}{c|}}
\hline
p\amp q\amp p \implies q\\
\hline
\true \amp \true \amp \true \\
\true \amp \false \amp \false \\
\false \amp \true \amp \true \\
\false \amp \false \amp \true \\
\hline
\end{array}
\end{equation*}
It follows that if we want to prove that
\(p\implies q\) is true, we need to show that the second row (
\(p = \true\) ,
\(q = \false\) ) does not occur.
In the approach called the
direct proof we start by assuming
\(p\) is true and then show that
\(q\) is true.
Proof Technique 1.4.2.1 . To show \(p\implies q\) with direct proof.
Suppose \(p\) and \(q\) are propositions, and we want to prove the conditional “if \(p\) then \(q\) ” by direct proof.
Deduce
\(q\) is true under the assumption.
Conclude
\(p\implies q\) .
Example 1.4.2.2 . The sum of two odd integers is even.
We prove that the sum of two odd integers is even.
Answer .
Let
\(a\) and
\(b\) be odd integers.
Since
\(a\) is odd, there exists an integer
\(k\) such that
\(a = 2k + 1\text{.}\)
Since
\(b\) is odd, there exists an integer
\(\ell\) such that
\(b = 2\ell + 1\text{.}\)
Compute \(a + b\) and simplify.
\begin{align*}
a + b \amp = 2k + 1 + 2 \ell + 1 \\
\amp =2k + 2 \ell + 2 \\
\amp =2(k + \ell + 1).
\end{align*}
Since \(k\) and \(\ell\) are integers, we have \(k + \ell + 1\) is an integer, and so \(a + b\) is even.
Solution .
We first develop a proof and the write down the actual proof as the answer to this problem.
First, we rewrite what we want to show in the form “if
\(p\) , then
\(q\text{.}\) ” Additionally, we will give friendly names to objects. Let’s name our odd integers
\(a\) and
\(b\text{.}\) Then the statement we wish to prove is:
“If
\(a\) and
\(b\) are odd integers, then
\(a + b\) is even.”
When we want to prove a statement of the form “if
\(p\) , then
\(q\) ” directly, we assume
\(p\) is true and try to show
\(q\text{.}\) This is commonly where we set some notation as well. Let
\(a\) and
\(b\) be odd integers.
Next we need to recall what an
odd integer is. An integer
\(n\) is
odd if there exists an integer
\(k\) such that
\(n = 2k + 1\) .
Now apply the definition to our situation. Since
\(a\) is odd, there exists an integer
\(k\) such that
\(a = 2k + 1\text{.}\)
Since
\(b\) is odd, there exists an integer
\(\ell\) such that
\(b = 2\ell + 1\text{.}\)
Check back above to be sure that the two integers whose existence is guaranteed have different names. They need different names because they need not be the same integer.
Now look back to the goal that we set in 1. Since we want to say something about \(a+b\) , it makes sense to compute \(a + b\) and simplify.
\begin{align*}
a + b \amp = 2k + 1 + 2 \ell + 1 \\
\amp =2k + 2 \ell + 2 \\
\amp =2(k + \ell + 1).
\end{align*}
The line above should prove
\(a+b\) is even, provided the bit in the parentheses is an integer. Make some remark noting that, and we are done. Since
\(k\) and
\(\ell\) are integers, we have
\(k + \ell + 1\) is an integer, and so
\(a + b\) is even.
Putting all that together yields the following.
Example 1.4.2.3 . The product of two even integers is even.
Prove that the product of two even integers is even.
Answer .
Let
\(m\) and
\(n\) be even integers.
Then there exist integers
\(k\) and
\(\ell\) such that
\(m = 2k\) and
\(n= 2\ell\text{.}\)
With the above we get
\begin{equation*}
mn = 2k \cdot 2 \ell = 4k \ell = 2(2k \ell).
\end{equation*}
Since \(k\) and \(\ell\) are integers, \(2k\ell\) is an integer. Thus \(mn\) is even.
Example 1.4.2.4 . Squares.
Let
\(m\) and
\(n\) be real numbers. Prove that
\(m^2 = n^2\) if and only if
\(m = n\) or
\(m = -n\text{.}\)
Answer .
To prove
“\(m^2 = n^2\) if and only if \(m = n\) or \(m = -n\text{.}\) ”
we first prove
“If \(m^2 = n^2\) then \(m = n\) or \(m = -n\text{.}\) ”
and then
“If \(m = n\) or \(m = -n\) then \(m^2 = n^2\text{.}\) ”
Suppose \(m\) and \(n\) are integers such that \(m^2 = n^2\text{.}\) Then
\begin{equation*}
0= m^2 - n^2 = (m + n)(m - n).
\end{equation*}
It follows that \(m + n = 0\) or \(m - n = 0\text{.}\) Thus \(m = -n\) or \(m = n\text{,}\) which proves that “if \(m^2 = n^2\) then \(m = n\) or \(m = -n\) ” is true.
Clearly, if
\(m = n\) then
\(m^2 = n^2\text{.}\)
Also, if
\(m = -n\) then
\(m^2=(-n)^2=n^2\text{.}\)
Thus “if
\(m = n\) or
\(m = -n\) then
\(m^2 = n^2\) ” is true.
Figure 1.4.2.5. Proof without Content by Randal Muroe (https://xkcd.com/3201
