abstractmath.org 2.0
help with abstract math


Produced by Charles Wells     Revised 2015-10-02

Introduction to this website    website TOC    website index

Head of Math Reasoning Chapter   blog

CONTENTS

Contrapositive method

Proof by contradiction

Proof by cases

Other forms of proof

FORMS OF PROOF

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.

Proving conditional assertions: The direct method

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.

Example

Definition

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

Theorem

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

Narrative proof of the theorem by the direct method

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.

Remarks

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.

Narrative proof rewritten with bullet points

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.

Proof with reasons

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.

Coming up with direct proofs

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 usually happens is that you think of statements which imply $Q$, statements which imply them (backing up), and at the same time you think of statements which $P$ implies, statements which they imply (going forward), and so on, until your chain meets in the middle (if you are lucky).

Thinking up a proof is a CREATIVE ACT
not a mechanical one of grinding out conclusions from hypotheses

A very sad tale

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.

Why does this happen?

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.

References

How to Read and Do Proofs by Daniel Solow.

Proving conditional assertions: The contrapositive method

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.

Example

Theorem

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

Narrative proof by the contrapositive method

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.

Outline of the reasoning of the proof

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.

A clue is detected

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.

Proof by Contradiction

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.

Example

Theorem

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

Typical narrative proof

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.

Analysis of the proof

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.

Remarks

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.

Proof by cases

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.

Example

Theorem

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

Narrative proof by cases

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+6r+1)+1\] so you can take $k=3r^2+6r+1$ for the proof.

Analysis of 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$.
This argument is justification for the requirement that $n$ has to have at least one of the properties $A_1$ and $A_2$.
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.

References

Wikipedia.
Proof by Cases by Bruce Ikenaga has many good examples of proof by cases.

Example: Powerset theorem

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

Theorem

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.

Proof

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.

Other forms of proof

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

Proof by Induction

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.

Proofs of uniqueness

There are good examples in the Proof examples from Gordon College and in the Whitman College site.

Proofs of equivalence.

These site may be useful.

Proof examples from Gordon College.
My notes in Discrete Mathematics, pages 122-124.

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