Proofs in mathematics

micromass

This FAQ is about proofs. Proofs are central to mathematics, and writing proofs is for many people a skill that is hard to master. There are actually two separate skills that one must master: finding the proof and communicating the proof. We will try to focus on the former here, but we will try to say something about the latter anyway.

What is a proof?
A proof is a convincing statement about why something is true. Furthermore, a proof can use only definitions, axioms, and previously proven theorems or lemmas. By its very nature, a proof uses deductive reasoning and not empirical arguments. For example, let's say you want to prove that [itex]n^2-n+41[/itex] is prime for all natural numbers n. One cannot prove such a thing by checking a few cases and noticing that it is true in these cases. Indeed, a proof must indicate why something is valid in all cases, no exceptions.

In logic, we often work with "formal proofs". These are proofs with a very rigid structure and contain only symbols and not words.
They are often quite difficult to read. In theory all proofs should be "formal proofs", but this would be unmanageable. Instead, mathematicians write informal proofs that are easy to read, but still convincing enough. Note, however, that every good informal proof can be written as a formal proof. It's not practical to do so, though. The site http://us.metamath.org/ offers a wide variety of formal proofs.

Why bother with proofs?
Why not follow the method of other sciences? Just make a large number of experiments and form a conclusion based on those experiments. Surely, if a statement has been shown for a large number of cases, then the statement should be true?

This reasoning goes against the heart of mathematics. In mathematics, we don't just want the statement to hold for "most cases", we want to make the statement work for "all cases". Mathematics tries to provide results that are 100% true or 100% false. A result that holds for "most cases" is uninteresting (unless one can rigorously define what "most cases" means).

In a previous paragraph we were asked to prove that [itex]n^2-n+41[/itex] is always prime. One could argue that we can just test the statement for a number of cases, for example

If n=1, then [itex]n^2-n+41=41[/itex]
If n=2, then [itex]n^2-n+41=43[/itex]
If n=3, then [itex]n^2-n+41=47[/itex]
If n=4, then [itex]n^2-n+41=53[/itex]
If n=5, then [itex]n^2-n+41=61[/itex]
If n=6, then [itex]n^2-n+41=71[/itex]
If n=7, then [itex]n^2-n+41=83[/itex]
If n=8, then [itex]n^2-n+41=97[/itex]
If n=9, then [itex]n^2-n+41=113[/itex]
If n=10, then [itex]n^2-n+41=131[/itex]

We can go on to n=20 or n=30 and find only primes. So one could say that this proves that we only get primes. But this is false. For n=41, we get something that is not a prime:

[tex]41^2-41+41=41^2.[/tex]

So the statement is in fact false. There are other statements that seem to hold for billions and billions of cases, but eventually fail.

What methods of proof are there.
There are several methods of proofs available. It takes practice and experience to know which method of proof one should actually use. Let's try to give the most important methods:

Direct proof:
This is the most simple method available. You start from your assumptions and end up with the conclusion.

As an example, let's prove that the square of an odd integer is always odd:

An odd integer has the form 2n+1. When we square this, we get [itex](2n+1)^2=4n^2+4n+1=2(2n^2+2n)+1[/itex]. This has the form 2m+1 (with [itex]m=2n^2+2n[/itex] and thus is odd.

We did leave out some details, such as why anything of the form 2m+1 is odd. But overall, this proof should be convincing enough.

As another example, let's take a polynomial [itex]aX+b[/itex] and let's show that [itex]\frac{-b}{a}[/itex] is always a root of this polynomial (provided that [itex]a\neq 0[/itex]).

We must prove that
[tex]a\left(\frac{-b}{a}\right) + b=0[/tex]
Let's simplify the left-hand side
[tex]\begin{eqnarray*}
LHS
& = & a\left(\frac{-b}{a}\right) + b\\
& = & \frac{-ba}{a} + b\\
& = & -b+b\\
& = & 0\\
\end{eqnarray*}
[/tex]

As you can see, we just stated what we need to prove, made some calculations and ended up with the result. This is essentially what a direct proof is.

Proof by contradiction
The idea behind the proof of contradiction is that there are two possibilities: the things we are required to prove is correct or it is incorrect. Instead of directly proving that it is correct, we actually show that it cannot be incorrect. To show that it cannot be incorrect, assume that it is incorrect and derive a contradiction (an absurd statement).

Let us use a proof by contradiction to actually show the converse of what we proved the last section. That is: if n is an integer such that n² is odd, then n must be odd.

So assume that n is an integer such that n² is odd. There are 2 possible cases: n can be odd or n can be even. If we show that n cannot be even, then it must be odd.
So, assume that n is even, then it has the form n=2k. But then [itex]n^2=(2k)^2=4k^2=2(2k^2)[/itex]. This has the form 2m (with [itex]m=2k^2[/itex]), thus n² is even. But we made the assumption that n² was odd, so we have reached a contradiction. So, n cannot be even (otherwise n² must be even), hence n must be odd.

A proof by contradiction seems something farfetched, but it actually isn't. We do such a things every day, we just don't think about it. For example, let's say that we want to solve the following (very easy) sudoku:

[tex]\begin{array}{|c|c|} 1 & \\ \hline \\ & \\ \end{array}[/tex]

So, we have to write 1 and 2 in the above square, but we cannot have two identical numbers in the same row or in the same column. A reasoning we often apply is the following:

We can write a 0 or a 1 next to the 1 in the first row. But if we would write a 1, then we would have identical numbers in the first row. This is forbidden (i.e. this is a contradiction), thus we have to place a 0 next to the 1.
We can write a 0 or a 1 under the 1 in the first row. But if we were to write a 1, then we would have identical numbers in the first column. This is a contradiction, thus we have to place a 0 under the 1.

As you can see, we have actually used a proof by contradiction to solve the puzzle. So a proof by contradiction might not be as innatural as you might think.

Proof by induction
A proof by induction is often used when we have to proof something for all natural numbers. The idea behind the proof by contradiction is that of falling dominoes. If we set up a sequence of dominoes next to each other, and if we push the first domino, then all dominoes will fall. Indeed: the first domino falls because we push it, the second domino falls because it is pushed by the first domino, the third domino will fall because it is pushed by the second domino,...

The same idea is used by the proof of induction. In such a proof, we prove two things:

• The statement holds for a certain specific value a.
• If the statement holds for n, then it holds for n+1.

The result is that the statement must hold for all numbers larger than a. Indeed, the statement holds for a by the first point. But the second point says that if it holds for a, then it must hold for a+1. But since it holds for a+1, it must hold for a+2. And thus it must hold for a+3, a+4, a+5, etc. by applying the second point over and over again. In the end, it will hold for all numbers greater than a.

Let's give an example. Let's prove that [itex]1+2+3+...+n=\frac{n(n+1)}{2}[/itex]. This is a typical statement that uses a proof by induction.

• The statement certainly holds for n=1, since [itex]1=\frac{1(1+1)}{2}[/itex].
• Assume now that the statement holds for n, that is: we know that [itex]1+2+3+...+n=\frac{n(n+1)}{2}[/itex] (this is called the induction hypothesis). We must show that the statement holds for n+1. That is, we must show that
  
  [tex]1+2+3+...+n+(n+1)=\frac{(n+1)(n+2)}{2}[/tex]
  
  But this is easy, since we know the result for n:
  
  [tex]\begin{eqnarray*}
  1+2+3+...+n+(n+1)
  & = & \frac{n(n+1)}{2}+(n+1)\\
  & = & \frac{n^2+n}{2}+\frac{2n+2}{2}\\
  & = & \frac{n^2+3n+2}{2}\\
  & = & \frac{(n+1)(n+2)}{2}\\
  \end{eqnarray*}[/tex]
  

Let's do another example. Let's prove the inequality of Bernouilly. This states that [itex](1+x)^n\geq 1+nx[/itex] for positive integers n and x a real number greater than -1. So, let's do induction on n:

• The statement holds for n=0, since [itex]1=(1+x)^0=1+0x=1[/itex].
• Assume that the statement holds for n, that is: we know that [itex](1+x)^n\geq 1+nx[/itex]. We must show that it also holds for n+1. Thus we must show that
  
  [tex](1+x)^{n+1}\geq 1+(n+1)x[/tex]
  
  Indeed, we know that [itex](1+x)^n\geq 1+nx[/itex]. Because [itex]x+1\geq 0[/itex], we can multiplicate both sides by x+1. This yields
  
  [tex](1+x)^n(1+x)\geq (1+nx)(1+x)[/tex]
  
  or
  
  [tex](1+x)^{n+1}\geq 1+(n+1)x+x^2\geq 1+(n+1)x[/tex]
  
  since x² is always positive.

How to write down good proofs
Writing down and communicating proofs is a skill to master. First of all, you must keep in mind the level of the audience. Presenting a proof for a high-schooler is very different from presenting a proof for an audience of math professors. In the former case, you must go quite slow and explain everything. In the latter case, you can safely skip the boring or easy parts.

Contrary to what many beginning students think, it is not ok to write many symbols in proofs. A proof should mostly consist of texts and explanations of what you are doing. Calculations must still be made, but be sure to accompagny them with some texts and explanations.

For example, a bad proof for the statement "if n is odd, then n² is odd" is

[tex]n=2k+1 ~\Rightarrow~ n^2=(2k+1)^2=4k^2+4k+1 ~\Rightarrow~ \exists m:~n^2=2m+1[/tex]

Sure, this is correct, but it is quite intensive for the reader to see what you are doing. Better would be not to write symbols like [itex]\Rightarrow[/itex] or [itex]\exists[/itex]. And best would be to replace them with a guiding text.

Further reading
Be sure to check out wiki's page on mathematical proofs: http://en.wikipedia.org/wiki/Mathematical_proof
For a lot of tips on how to write proofs and mathematical texts, see tex.loria.fr/typographie/mathwriting.pdf

Contributors
bcrowell
mathwonk
micromass