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

Direct method

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$,”

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

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:

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:

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 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$,”

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

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,

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

Proof by cases

Also called proof by exhaustion

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

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$".

References

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:

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.



Creative Commons License

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