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.3 Proof by contraposition
In
Theorem 1.2.1.10 we have shown that the contrapositive of
\(p\implies q\) is logically equivalent to
\(\lnot q \implies \lnot p\text{.}\)
Thus proving
\(p\implies q\) is true is the same as proving
\(\lnot q \implies\lnot p\) is true. This is called
proof by contraposition .
Proof Technique 1.4.3.1 . To show \(p\implies q\) by contraposition.
Let \(p\) and \(q\) be propositions. To prove the conditional “if \(p\) then \(q\) ” by contraposition, we:
State that it is sufficient to prove the contrapositive.
Assume
\(q\) is false, (or equivalently
\(\lnot q\) is true).
Deduce
\(p\) is false, (or equivalently
\(\lnot p\) is true) under the assumption.
Conclude
\(p\implies q\) .
Example 1.4.3.2 . Even square.
Let
\(n\) be an integer. Prove that if
\(n^2\) is even, then
\(n\) is even.
Answer .
To prove
“If
\(n^2\) is even, then
\(n\) is even.”
it is sufficient to prove the contrapositive
“If
\(n\) is odd, then
\(n^2\) is odd.”
Suppose
\(n\) is odd.
Then there exists an integer \(k\) such that \(n = 2k + 1\text{.}\) With this we get
\begin{equation*}
n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.
\end{equation*}
Since \(k\) is an integer, we have that \(m=2k^2 + 2k\) is an integer, and so
\begin{equation*}
n^2=2m+1
\end{equation*}
is odd.
We have proven “If
\(n\) is odd, then
\(n^2\) is odd” is true and thus the original proposition “If
\(n^2\) is even, then
\(n\) is even.” also is true.
Example 1.4.3.3 . If \(a\cdot b+ 6\) is odd.
Prove that if
\(a\cdot b+ 6\) is odd then both
\(a\) and
\(b\) are odd.
Answer .
We prove
“If \(a\cdot b+ 6\) is odd then both \(a\) and \(b\) are odd.”
by contrapositive, that is we prove
“If not both \(a\) and \(b\) are odd then \(a\cdot b+ 6\) is even.”
If not both
\(a\) and
\(b\) are odd we are in one of the following cases:
\(a\) is even and
\(b\) is even, or
\(a\) is even and
\(b\) is odd, or
\(a\) is odd and
\(b\) is even.
We consider each of the three cases separately.
Suppose
\(a\) is even and
\(b\) is even.
Then there are integers \(k\) and \(\ell\) such that \(a=2k\) and \(b=2\ell\text{.}\) We get
\begin{equation*}
a\cdot b+6=(2k)(2\ell)+6=2(2k\ell)+6=2(2k\ell+3).
\end{equation*}
Since
\(k\) and
\(\ell\) are integers
\((2k\ell+3)\) is also an integer. Thus by
Definition 1.4.1.1 we have that
\(a\cdot b+6\) is even.
Suppose
\(a\) is even and
\(b\) is odd.
Then there are integers \(k\) and \(\ell\) such that \(a=2k\) and \(b=2\ell+1\text{.}\) We get
\begin{equation*}
a\cdot b+6=(2k)(2\ell+1)+6=2k(\ell\cdot 1)+6=2(k(\ell+1)+3).
\end{equation*}
Since
\(k\) and
\(\ell\) are integers
\((k(\ell+1)+3)\) is also an integer. Thus by
Definition 1.4.1.1 we have that
\(a\cdot b+6\) is even.
Suppose
\(a\) is odd and
\(b\) is even.
Then there are integers \(k\) and \(\ell\) such that \(a=2k+1\) and \(b=2\ell\text{.}\) We get
\begin{equation*}
a\cdot b+6=(2k+1)(2\ell)+6=2(\ell\cdot(2k+1)+3).
\end{equation*}
Since
\(k\) and
\(\ell\) are integers
\((\ell\cdot(2k+1)+3)\) is also an integer. Thus by
Definition 1.4.1.1 we have that
\(a\cdot b+6\) is even.
Because in each of the three cases we found that \(a\cdot b+6\) is even, we have proven that “if not both \(a\) and \(b\) are odd \(a\cdot b+ 6\) is even”, which concludes our prove.
