Produced by Charles Wells Revised 2017-02-15 Introduction to this website website TOC website index Head of Math Reasoning Chapter blog

CONTENTS |

A proof written in narrative form is very often arranged in one of a few basic forms. Authors don’t usually tell you which form they are using. To understand proofs, you need to recognize these forms. This chapter describes them and shows examples.

The section on mathematical reasoning and many other places in abstractmath.org describe particular rules of inference used in proofs, and in some of those passages the way the rules of inference are written up is discussed.

To prove “If $P$, then $Q$,”

- Assume that $P$ is true.
- Deduce that $Q$ must be true as well, using the fact that $P$ is true and any other facts that you have.

An integer $n$ is **even**
if there is an integer $m$ for which $n=2m$.

If $n$ is even, then ${{n}^{2}}$ is even.

Suppose that $n$ is even. Then $n=2m$ for some integer $m$. Then ${{n}^{2}}=4{{m}^{2}}=2\cdot (2{{m}^{2}})$. $2{{m}^{2}}$ is an integer because $m$ is an integer, so by definition of “even”, ${{n}^{2}}$ is even.

- This theorem, like many theorems in mathematics, is a universal conditional assertion, so the proof uses universal generalization to show that if $n$ is an arbitrary positive integer satisfying the hypothesis, then it must satisfy the conclusion.
- In this proof, $P$ is “$n$ is even” and $Q$ is “${{n}^{2}}$ is even”.
- The author does not
tell you that the proof of “If $P$, then $Q$” is by the direct method. But you can
*detect the pattern*when the proof starts with “Suppose that $n$ is even”, in other words, “Suppose $P$”. - The sentence "Then $n=2m$ for some integer $m$" follows from the definition of "even" by modus ponens, but the narrative proof does not point this out.
- The phrase "So by definition of 'even'" required pattern recognition: The $m$ required by the definition is $2m^2$, but the author does not specifically tell you that.
- A proof using the
direct method is called a
**direct proof.**You undoubtedly already knew how to give a direct proof. This article is intended*to raise your knowledge to a conscious level*(if it isn’t already there). - This is an example of a proof by rewriting according to the definition of the words in the theorem.

The proof given above is a short narrative proof written in one paragraph. It coulds be written in bullet points like this:

- Suppose that $n$ is even.
- Then $n=2m$ for some integer $m$.
- Then ${{n}^{2}}=4{{m}^{2}}=2\cdot(2{{m}^{2}})$.
- $2{{m}^{2}}$ is an integer because $m$ is an integer.
- So by definition of “even”, ${{n}^{2}}$ is even.

Bullet points are not commonly used in math proofs, and many mathematicians, perhaps most of them, object strongly to using them. I think bullet points make it easy to follow the argument.

For proof-newbies it would be helpful to give a reason for each bullet point:

- Suppose that $n$ is even. ("Assume that $P$ is true")
- Then $n=2m$ for some integer $m$. (Definition of "even".)
- Then ${{n}^{2}}=4{{m}^{2}}=2\cdot(2{{m}^{2}})$. (Algebra)
- $2{{m}^{2}}$ is an integer because $m$ is an integer. (Product of two integers is an integer)
- So by definition of “even”, ${{n}^{2}}$ is even.

In a more complicated situation, you might have to prove

If $P$ then ${{P}_{1}}$,

If ${{P}_{1}}$ then ${{P}_{2}}$,

…

If ${{P}_{k}}$ then $Q$

using a sequence of deductions.

Normally, although your final proof would be written up in
that order, * you would not think up the proof by thinking up ${{P}_{1}}$,
${{P}_{2}}$,… in order.* What

Thinking up a
proof is a CREATIVE ACT

not a mechanical
one

of grinding out conclusions from hypotheses

This has happened to my students many times:

- You are asked to prove “If $P$, then $Q$.”
- You assume $Q$.
- You prove statements “If $Q$, then $P_1$”, if $P_1$ then $P_2$”, …, if $P_k$ then $P$”.
- You triumphantly conclude “If $P$ then $Q$.”
- You get your paper back and that problem is marked wrong. Zero points. Zilch.

You constructed your proof backward. If
all the steps are right, you have proved “If $Q$ then
$P$”. But you were asked to prove “If $P$ then $Q$”. **How sad.**

In the case that $F$ and $G$ are algebraic expressions, we often prove that $F=G$ by proving $G = F_1$, $F_1 = F_2$, …, $F_k =F$.

Example: Prove $x^2+5x+6=(x+2)(x+3)$.

Proof: $(x+2)(x+3)=x(x+3)+2(x+3)=x^2+3x+2x+6= x^2+5x+6$.

This is perfectly correct, because the assertion "$F=G$" is symmetric in $F$ and $G$.
Unfortunately, for *assertions* $P$ and $Q$. “If $P$ then $Q$” is *not* symmetric in $P$ and $Q$.

Example: "If $n\gt2$ then $n\gt1$" is correct, but "If $n\gt1$ then $n\gt2$" is incorrect.

How to Read and Do Proofs by Daniel Solow.

Method: To prove “If $P$, then $Q$,”

- Assume that $Q$ is false.
- Deduce that $P$ must be false as well, using the fact that $Q$ is false and any other facts that you have.

This
method is the Direct Method applied to “If not $Q$, then not $P$.” That assertion is the contrapositive of “If $P$,
then $Q$”, but proving the contrapositive of a conditional assertion is the *same thing* as proving the assertion, since a conditional sentence and
its contrapositive always have the same truth value.

If ${{n}^{2}}$ is even, then $n$ is even.

Suppose $n$ is odd. Then for some integer $k$, $n=2k+1$. Then \[{{n}^{2}}=4{{k}^{2}}+4k+1=2(2{{k}^{2}}+2k)+1\] Thus ${{n}^{2}}=2h+1$ for some integer $h$, so ${{n}^{2}}$ is odd. QED.

- The proof of the contrapositive proceeds like any direct-method proof, by assuming the hypothesis ($n$ is odd) and deducing the conclusion (${{n}^{2}}$ is odd).
- It follows by the direct method that the contrapositive of the theorem as stated is true.
- Since a conditional assertion and its contrapositive always have the same truth value, the theorem as stated must be true.

If you didn't think of proving the contrapositive, you might be dumbfounded when
you saw that a proof of a theorem which says "if ${{n}^{2}}$ is even then n is even" begins with,
"Let $n$ be odd..." But that is a **clue** …

If a theorem has
the form “If $P$ then $Q$”

and the proof begins with “Assume $Q$ is false…”,

that is
a clue that the form of the proof

is by the contrapositive method.

See translation problem and rabbits.

To prove that an assertion $P$ is false,

- Prove
that “If $P$ then $Q$” is
**true** - Prove that $Q$ is false, using any facts that you have.

This method is called **proof by contradiction** or **reductio ad
absurdum**, sometimes abbreviated **r.a.a.**

The number ${{\log }_{10}}3$ is not rational.

Let ${{\log }_{10}}3=\frac{m}{n}$ where $m$ and $n$ are positive integers. Then ${{10}^{\frac{m}{n}}}=3$, so ${{10}^{m}}={{3}^{n}}$. This is impossible because every positive power of $10$ is even and every positive power of $3$ is odd. QED.

In this proof, $P$ is the statement “${{\log }_{10}}3$ is rational” and $Q$ is the statement “An even integer cannot equal an odd integer.”

- The proof proceeds by contradiction, which means it must start by proving “If $P$ then $Q$”.
- It proves “If $P$ then $Q$” by the direct method.
- Therefore it starts
with the
*assumption*(not stated explicitly) that ${{\log }_{10}}3$ is rational. - By rewriting according to the
definition of “rational”, we get ${{\log }_{10}}3=\frac{m}{n}$ where $m$ and
$n$ are positive integers. This is the
*first actual statement that occurs in the proof*. - Then the proof uses the definition of log (without saying so) to conclude that ${{10}^{\frac{m}{n}}}=3$.
- Using the algebra of exponents, it concludes that ${{10}^{m}}={{3}^{n}}$.
- The statement “Every positive power of 10 is even and every positive power of 3 is odd” is then made without proof (regarded as common knowledge).
- The proof then claims a contradiction, without stating the fact $Q$ (also regarded as common knowledge) that it contradicts.

The proof does
not say it is a proof by contradiction,

and neither $P$ nor
$Q$ is stated explicitly in the proof.

This is typical. GET OVER IT.

- This analysis of the proof is an example of the translation problem.
- Authors sometimes tell you they are doing a proof by contradiction, and sometimes don’t.
- In practice it frequently happens that $Q$ is
obviously false so that the work goes into proving “If $P$ then $Q$.”
Thus a proof that $P$ is false might begin, "Suppose $P$ is
true."
*That is a clue that you are reading a proof by contradiction.*

Also called **proof by exhaustion**.

To prove a statement $P(n)$ by cases,

- Prove that $n$ has to have at least one of the properties $A_1$, $A_2$, $\dots A_s$
- For each $i=1,2,\ldots s$, prove that if $P(n)$ has property $A_i$, the $P(x)$ is true.

If $n$ is not divisible by $3$, then there is an integer $k$ for which $n^2=3k+1$.

If $n$ is not divisible by $3$, then there must be an integer $r$ for which either $n=3r+1$ or $n=3r+2$.

If $n=3r+1$, then \[n^2=9r^2 +6r+1=3(3r^2+2r)+1\] so you can take $k=3r^2+2r$ for the proof.

If $n=3r+2$, then \[n^2=9r^2+12r+4=9r^2+12r+3+1=3(3r^2+4r+1)+1\] so you can take $k=3r^2+4r+1$ for the proof.

In this proof, $A_1$ is "$n=3r+1$" and $A_2$ is "$n=3r+2$".

- "If $n$ is not divisible by $3$" is a signal that the proof uses the Direct Method.
- The statement "There must be an integer $r$ for which either $n=3r+1$ or $n=3r+2$" follows from these facts:
- If you divide a positive integer by $3$, the remainder is $0$, $1$ or $2$.
- If the remainder is $0$ then the number must be divisible by $3$.

- The proofs for the two cases use only basic algebra.
- It is OK for the cases in a proof to overlap, but in most simple cases (like this one) they are in fact disjoint.

This is both a proof by contradiction and also a proof by cases. The proof uses the method of comprehension.

Let $S$ be a set and let $\mathcal{P}(S)$ be the power set (set of all subsets) of $S$. Then no function $F:S\to \mathcal{P}(S)$ is surjective.

Suppose $F:S\to \mathcal{P}(S)$ is a function. Let $A=\{x\in
S|x\notin F(S)\}$. Then $A$ is a subset of $S$, so it is an *element*
of $\mathcal{P}(S)$.

Now I will show that there is no element $x$ of $S$ for which $F(x)=A$. There are two cases:

- $x\in A$. Then if $F(x)=A$, then $x\notin A$ by the method of comprehension. This is a contradiction.
- $x\notin A$. Then if $F(x)=A$, then $x\in A$ by the method of comprehension. This is also a contradiction.

There is no other possibility, so there is no element $x$ of $S$ for which $F(x)=A$. Therefore $F$ is not surjective.

The powerset theorem uses Cantor’s Diagonal argument, which Georg Cantor discovered when trying to understand how infinity comes in different sizes.

There are many other forms of proof not covered in abstractmath.org.

This is covered in a Wikipedia article that has better coverage of the role of mathematical induction in logic than it does in its role in math. My Discrete Math notes has many examples in Chapter 103. I expect to adapt that material to make an abstractmath.org chapter.

There are good examples in the Whitman College site.

These site may be useful.

- My notes in Discrete Mathematics, pages 122-124.

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.