What is a proof?
What is a proof? Well that is a much harder question
one might at first suspect! Indeed it is a subject both of
philosophical discussion (i.e. there is probably no answer) and
mathematical investigation (logic, type theory, proof theory, etc.).
Proof as well-structured thought
The first basic strategy behind writing a proof is common sense: if
want to make an argument that something is true you should break the
argument down into smaller steps. Once one has broken it into
small steps then
can be individually examined to see whether it is valid -- if
step is small enough one should be able to easily determine whether
step is valid then the whole argument will be valid!
If there is an error in the proof then it will become apparent
one of the small steps into which you have broken the argument must
wrong. Just one slip is enough to invalidate the whole proof
mathematics in this sense is completely unforgiving!
Mathematicians read each others proofs to detect these false
steps and there are many famous instances when slips in proofs have
been made (e.g.
the early "proofs" of Fermat's last theorem, of the four color
Errors of this nature are a normal occurrence in the
process of developing mathematical ideas .... but it is worth
that we hear of successes: usually we don't hear about it when the
were simply wrong!
To a programmer this should make perfect sense: to develop a big
program one breaks it down into modules. When all the modules
work one can put them together to make the big program. If the
small enough and well circumscribed enough they can easily be tested
An error in any one of the modules, on the other hand
a program behave in an arbitrary bad way! This should make
that there is a close relationship between proofs and developing
.... and there absolutely is. These connections have been made
explicit by proof theorists: the Curry-Howard isomorphism is one
well-known way in which they are connected.
The analogy with programming should also alert you to another aspect
proofs. Just as a program is developed in a particular
so a proof belongs to a particular proof system. In
are a number of well-known proof systems: equational proofs,
and predicate logic proofs, inductive proofs, coinductive proofs,
So this raises an interesting question: what does a good proof
look like? Clearly a rather crucial aspect is that one should
to decompose proofs into basic steps and then form the proof by
these steps. This is a requirement on the proof system
there are definitely systems out there for which this basic
fails. A proof system with this property is called compositional.
It is also important that there are a small (finite) number
steps from which every proof can be constructed: there are
systems which fail to have this property. A proof system with
property is said to be finitely presented. Finally,
should have information content: that is it should have some things
are provable and other things which are not provable. A system
this property is said to be non-degenerate.
Constructing a proof theory with all these properties is a
task. In the beginning of the 20th century there was a
significant effort to try to establish the foundations of
This culminated in various axioms for set theory, the
development of proof theory, and indeed the theory computability.
fact that these developments were not straightforward is indicated
the litter of "paradoxes" (Russell's paradox, the liar
...) which accompanied the development of set theory. These
developed as signpost to the boundaries of where set theory
and logic becomes degenerate. Famously some of the early
theory" turned out to be degenerate but fortunately for mathematics
were corrected ...
Provability and computability
Even more philosophically dramatic than the foundational problems in
the development of set theory was the collapse of Hilbert's
program. Hilbert was one of the most influential
of the beginning of the 20th century. In 1900 he gave a famous
lecture to the International Congress of Mathematicians in which he
outlined a number of unsolved mathematical problems. These
problems came from many different areas of mathematics and
greatly influenced the development of mathematics itself.
Hilbert believed that by steadily breaking any problem down one
with diligence determine whether it was true or false.
had no role in his world. Brower, who was also a well-known
Dutch mathematician, had a philosophically rather different view
became known as "intuitionistic" mathematics: this allowed for
propositions which where neither true or false (i.e. from a modern
perspective one might say undecidable -- although this notion was
developed until much
later). Hilbert found Brower's intuitionistic view of
mathematics "unscientific", furthermore, he carried most of the
mathematical establishment with him. Not only did the view
everything was either true of false make perfect sense but also it
reflected in the set theoretic foundations for mathematics which, of
course, had been the major achievement of 19th century
mathematics. Hilbert comment that "no one shall expel us from
paradise that Cantor has created for us" won the day. Brower
famously lost a
very public argument for his more complex intuitionistic reality to
Hilbert's onslaught which extended far beyond mere mathematical
In the 1931's Godel proved his incompleteness theorem which showed
Hilbert's philosophical view of mathematics was wrong.
Significantly even some of the problems he described in the very
speech (1900) in which he put forward his philosophy of provability
out to be undecidable. Brower had been right! Godel's
results ultimately led to a much
better understanding of the link between computability and
The set theoretic foundations of mathematics have endured for
reasons: set theory is consistent even if is not the whole story
as a foundation, it is more easily explained (or at least more
exposed) than intuitionist or constructive mathematics.
In this regard Hilbert's influence on mathematics is still
the hubris of results of 20th century mathematics built on these
foundations made it even more difficult to "leave the paradise".
When is a Proof not a Proof?
Well you probably are no further along in answering the question
is a proof?" but I hope the discussion and historical remarks
The "proofs" below are to help you realize how easily one can come
the rails. Great care is needed when you are proving something and
you must really understand the individual steps. Furthermore,
understand the system in which you are working. Can you
the proofs below are not proofs!!! These are examples
absolutely classic fallacious proofs ...
1=2 (a proof using algebra)
Where was the mistake?
- Let a=b.
- This can be written as ,
- and cancelling the from both sides gives 1=2.
1=2 (a proof using complex numbers)
This supposed proof uses complex numbers.
This is what might be called a proof by intimidation: it relies
on you being a little frightened of the complex numbers! Can you
find the mistake?
- -1/1 = 1/-1
- Taking the square root of both sides:
- In other words, i/1 = 1/i.
- Therefore, i / 2 = 1 / (2i),
- i/2 + 3/(2i) = 1/(2i) + 3/(2i),
- i (i/2 + 3/(2i) ) = i (
1/(2i) + 3/(2i) ),
- (-1)/2 + 3/2 = 1/2 + 3/2,
- and this shows that 1=2.
Ladders fall infinitely fast when pulled!
Consider a ladder of length L leaning against a frictionless
wall which is at right angles to the ground. You pull the bottom of
ladder horizontally away from the wall, at constant speed v.
The claim is that this causes the top of the ladder to fall
Common sense tells us this can't possibly be true, but can you
the flaw in the following supposed "proof" of this claim?
So what is wrong? This is an example of blindly using math in
science! Can you see the error?
- Let x denote the horizontal distance from the bottom
the ladder to the wall, at time t.
- Let y denote the height of the top of the ladder from
the ground, at time t.
- Since the ladder, the ground, and the wall form a right
- Differentiating, and letting x' and y'
(respectively) denote the derivatives of x and y
respect to t, we get that
- Since the bottom of the ladder is being pulled with constant
speed v, we have x' = v, and therefore
- As x approaches L, the numerator in this
expression for y' approaches -Lv which is
the denominator approaches zero.
- Therefore, y' approaches as x approaches L.
other words, the top of the ladder is falling infinitely fast by
time the bottom has been pulled a distance L away from
The next two fallacious proof uses proof by induction. This is
rather important proof principle and I have provided a brief primer
below (after the fallacies).
All People in Calgary are the Same Age
This "proof" will attempt to show that all people in Calgary are the
same age, by showing by induction that the following statement
we'll call "S(n)" for short) is true for all natural
Statement S(n): In any group of n
people, everyone in that group has the same age.
The conclusion follows from that statement by letting n be
the number of people in Calgary.
The proof of Statement S(n):
- In any group that consists of just one person, everybody in
group has the same age, because after all there is only one
- Therefore, statement S(1) is true.
- The next stage in the induction argument is to prove that,
whenever S(n) is true for one number (say n=k),
is also true for the next number (that is, n = k+1).
- We can do this by (1) assuming that, in every group of k
people, everyone has the same age; then (2) deducing from it
every group of k+1 people, everyone has the same age.
- Let G be an arbitrary group of k+1 people; we
just need to show that every member of G has the same
- To do this, we just need to show that, if P and Q
are any members of G, then they have the same age.
- Consider everybody in G except P.
people form a group of k people, so they must all have
(since we are assuming that, in any group of k people,
the same age).
- Consider everybody in G except Q.
Again, they form a group of k people, so they must all
- Let R be someone else in G other than P
or Q. Since Q and R belong to a group in
the ages are the same (all the people except P) they are the same age.
- Similarly, since P and R belong to such a
they are the same age.
- Since Q and R are the same age, and P
and R are the same age, it follows that P and Q
the same age.
- We have now seen that, if we consider any two people P
and Q in G, they have the same age. It follows
everyone in G has the same age.
- The proof is now complete: we have shown that the statement
true for n=1, and we have shown that whenever it is true
it is also true for n=k+1, so by induction it is
for all n.
Well I am probably not the same age as you! So what went wrong?
The surprise quiz:
A teacher announces that before the end of class he is going to
surprise quiz. A clever student in his class reasoned as
(using the principle of strong induction see below):
He concludes it is impossible to set a surprise quiz!
Unfortunately the student was
surprised when the quiz happened the very
next day! So what went wrong?
- Number the days of the class backward from the last day of
which will be day 0.
- Say that U(n) holds when n is a day on which
cannot set a surprise quiz.
- On the last day the test will not be a surprise, so U(0) holds.
- If it is impossible to set a surprise test on all the days
a given day then a test that day will not be a surprise (because
test has not happened so far so the students will know it must happen
that day). Thus if for all i < n we have U(i)
then U(n) holds.
- The principle of strong induction now says that U(n)
hold for all n!
All numbers can be described in fourteen words or less
The claim is that any natural number can be completely and
unambiguously identified in fourteen words or less. Here a "word"
an ordinary English word, such as you or i might find in a
You know this can't be true. After all, there are only finitely
words in the English language, so there are only finitely many
can be built using fourteen words or less. So it can't
be true that every natural number can be unambiguously described
such a sentence as there are infinitely many natural numbers,
and only finitely many such sentences!
And yet, here's a "proof" of that claim:
The flaw in this proof is much more subtle ... here is a discussion of it.
- Suppose there is some natural number which cannot be
unambiguously described in fourteen words or less.
- Then there must be a smallest such number. Let's call it n.
- But now n is "the smallest natural number that cannot
unambiguously described in fourteen words or less".
- This is a complete and unambiguous description of n in
fourteen words, contradicting the fact that n was
to have such a description!
- Since the assumption (step 1) of the existence of a natural
number that cannot be unambiguously described in fourteen words
a contradiction, it must be an incorrect assumption.
- Therefore, all natural numbers can be unambiguously described
fourteen words or less!
proof a proof?
I am not going to tell you the answer to this. However,
do wish to mention is that even a short proof can demonstrate
quite surprising. So surprising that it can have
Perhaps one of the most famous (and yet simple) proofs is of the
irrationality of the square root of 2. The proof is attributed to
Hippasus of the Pythagorean school. The story goes that
discovered irrational numbers
when trying to represent the square root of 2 as a fraction (the
Unfortunately for him it wasn't until much later, when
a theory of irrational ratios, that Greek mathematicians accepted
numbers. Pythagoras, in particular, believed in the
numbers and did not accept the existence of irrational numbers.
However, neither could he find the fallacy in Hippasus's
As he could
not accept the conclusion (and admit that his philosophical ideas
sentenced Hippasus to death by drowning!
Please do not let this cautionary tale discourage you from
your proofs right! The power of life and death over students
nowadays no longer given to professors ...
Here is the proof:
Suppose sqrt(2) = n/m, where n and m are natural numbers
with no common divisors. Then 2m^2 = n^2 so that 2
n. But then it immediately follows that 2 also divides m
so they have a common divisor contrary to the assumption! So
initial assumption must be wrong.
Can you think of other proofs that have been just as
Principles of induction
The principle of mathematical induction says this: suppose
have a set of natural numbers (natural numbers are the numbers 0, 1,
3, 4, . . . ). Suppose that 0 is in the set. Suppose also that,
n is in the set, n+1 is also in the set. Then every
number is in the set.
To state it more informally: suppose you have been collecting
numbers and the number 0
collection, but also you notice that for each number k
have in your
collection, you also have the number k+1.
Then you have
a very large collection as it consists of all the natural numbers!
Intuitively, the idea is that if you start with the number 0, and
keep on adding 1 to it,
will eventually get to every number.
The principle of induction is extremely important because it
one to prove many results that are much more difficult, or
to prove in
other ways. The most common application is when one has a
wants to prove about each natural number. It may be quite
prove the statement directly, but easy to derive the truth of the
statement about n+1 from the truth of the statement about
In that case, one appeals to the principle of induction by showing
If you can prove those two things, then the principle of induction
that the statement must be true for all natural numbers. (Reason:
be the set of numbers for which the statement is true. Item 1 says
is in the set, and item 2 says that, whenever one number n
set, n+1 is also in the set. Therefore, all numbers are in
- The statement is true when n=0.
- Whenever the statement is true for one number n, then
it's also true for the next number n+1.
As an example, consider proving that 1+2+3+· ·
·+n = n(n+1)/2. To try to prove that
equality for a general, unspecified n just by algebraic
manipulations is difficult (though it may be easy to see it must
true). However, it is easy to prove by induction: it's true
= 1(1+1)/2), and whenever it's true for one number n,
1+2+3+· · ·+n = n(n+1)/2,
· ·+n+(n+1) = n(n+1)/2 + (n+1)
= (n+1)(n+2)/2, so it's also true for n+1.
facts, combined with the principle of induction, mean that it's
A consequence of mathematical induction is course-of-values
induction (also known as complete induction or
induction) which says, given a set of natural numbers,
know n is in the set whenever each i < n is in
set then every number is in
Here is a proof of this principle: notice that as there are no
numbers less than 0 so
that 0 must be in the
of the set, namely those number for which all predecessors are in
set. O is certainly
this subset. Let k
any number in
this set, as all of its predecessors are in the original set, then
in the original set
and so k+1 is in the
subset. But this means the subset contains
numbers whence the original set did!
The golden ratio:
An example of the use of strong induction is to derive the
fib(n) =( G^n -
where G is the Golden Ratio:
G = (1+ sqrt(5))/2
and the Fibonacci sequence is given by
fib(0) = 0, fib(1)=1, fib(n+2) =
First we note that fib(0) and fib(1) satisfy the
Now suppose fib(k) for every k < n+2
the formula (we have dealt with 0 and 1) then
fib(n+2) = fib(n) +
= (G^n - (-1/G)^n +G^(n+1) - (-1/G)^(n+1))/sqrt(5)
= (G^(n+1)(1+1/G) -(-1/G)^(n+1)(1-G)/sqrt(5)
= (G^(n+2) - (-1/G)^(n+2)
where the last step uses the two equations:
1+1/G = G and
1 - G
= - 1/G
which are really the same equation and simplified give the
G^2 -G -1 = 0
for which G as defined is a root! This is how Fibonacci
Least number principal:
The least number principle says that any non-empty
numbers has a least element. This can be used to do a
minimal counterexample: given a set which does not
numbers there must be a least number not in the set. Suppose
show that there is no minimal counterexample (typically by using
that it is a counterexample to construct another smaller
it must be that the set of counterexamples is empty.
This is actually the contrapositive of complete
induction! If you can prove that for any n not in the set there is a
m not in the set then,
whenever everything smaller
than the given element n
in the set, n must be in
set. So one can apply complete induction to conclude
set is all natural numbers.
Given a simple polygon constructed on a 2-dimensional grid of
with integer coordinates such that all the polygon's vertices are
points, Pick's theorem provides a simple formula for
calculating the area
A of this polygon in terms of the number i of interior
points located in the polygon and the number b of boundary
points placed on the polygon's perimeter:
- A = i + ½b − 1.
Note that the theorem is only valid for simple polygons,
i.e. ones that consist of a single connected piece and do not
The result was first described by Georg Alexander Pick in 1899.
can be generalized to three dimensions and higher with Ehrhart
The formula also generalizes to surfaces of polyhedra.
Every polygon must involve at least three grid points.
shall suppose that there is a polygon which is a counterexample
a minimum number of grid points. Either the polygon
three grid points (in which case it is straight forward to check
formula actually holds) or it is possible to split the polygon
smaller polygons by drawing a cord across the polygon. The
areas of the two smaller polygons is then the area of the
If the path across the polygon involves d points
polygons must satisfy (so d-2
= i1 + i2
+ d - 2
b = b1- d +
b2 - d + 2 = b1 + b2 - 2d + 2
A = A1 + A2 = i1 + ½b1
− 1 + i2 + ½b2 − 1
= i1 + i2 + ½(b1
+ b2) - 2
= (i1 + i2 + d - 2) + ½( b1 +
b2 - 2d +2) - 1
= i + ½b - 1
so this cannot be a counterexample unless one of the smaller
is already a counterexample. So there are no minimal
A neat application of Pick's theorem is to show:
It is impossible to draw an equilateral triangle with its
on grid points.
As the area of an equilateral triangle of base B has area sqrt(3)
B^2/2 which, as B^2
integer, is an irrational number!
Let S be a
non-empty set, and R be a
relation on S. Then R
is said to be a well-founded
relation if and only if every nonempty subset X
of S has an R-minimal
Note that R is by no means required to be a
total order. A classical example of a well-founded set that is not
totally ordered is the set of natural
numbers ordered by
division, i.e. (a,b) is in
R if and only if a
b, and a is not 1.
Let S be a subset of a set X with a well-founded relation
R. The principle of
well-founded induction states that if the following is true :
For every a,
if for every x such that (x,a)
in R we have x in
S then a in S
then S is the whole set X.
Notice that every R-minimal
of X must be in S as there are no
below such an element so all of them are in S!
Now in fact a relation for which this principle of induction is
is, necessarily, a well-founded relation! So that well-founded
relations for which arguments by (well-founded) induction work
one and the same thing.
Mathematical induction is obtained by asserting (as an axiom) that
successor relation is well-founded!
Complete induction is obtained by the assertion that the usual order
(the transitive closure of the successor relation) is well-ordered.
Thus well-founded induction is the most general inductive scheme.
The difficulty is rather to determine whether a relation is
theorem of arithmetic:
For an example of the use of well-founded induction, when the
is not the successor or the usual ordering on numbers, consider
fundamental theorem of arithmetic: every natural number has a
First note that the division relation on natural numbers is
well-founded and division-minimal
elements are exactly
the prime numbers. We detail the proof by splitting it into
considering the minimal elements and the non-minimal elements:
- If n is prime, then n is its
own factorization into primes, so the assertion is true for
the division-minimal elements.
- If n is not prime, then n has a
non-trivial factorization: n = rs, where r,
s are not one. By
have prime factorizations, and therefore n has one too.
In a programming language, such as Haskell, programming is done
datatypes. For doing proofs over datatypes a form of
induction called structural induction is often used. It is an
instance of well-founded induction which relies on the fact that
is a well-founded relation
on all (inductive) datatypes.
Given an (inductive) datatype which is built by applying
data D(a) = C1 T11(a,D(a))
| Cr Tr1(a,D(a)) Tr2(a,D(a)) ... Trm_r(a,D(a)).
then the terms of these datatypes have a well-founded relation
t2 < t1 whenever t1 is a (strict subterm) of t2 and there are to subterms
datatype between t1 and
t1 = s[t2/x] means t2 < t1
whenever the term \x -> s(x) has type X
For the natural numbers
as a datatype by:
data Nat = Zero | Succ Nat
we have the usual well-founded relation
Zero < Succ(Zero), Succ(Zero)
thus structural induction in this case is mathematical
data List a = Nil | Cons a
the relation gives t < Cons(a,t) which then allows
do structural inductive proofs using the principle of structural
induction for lists:
THEN the property holds for all elements of the list.
- if a property holds for Nil
- and whenever the property holds for t then the property holds for Cons a t) (well-founded
relation t < Cons a t)
For binary trees defined as a
data Tree a = Tip | Node a
(Tree a) (Tree a)
the relation gives t1 <
Node a t1 t2 and t2 <
a t1 t2 so that we get the following structural induction
THEN the property holds for all trees.
- if a property holds for Tip
- and whenever the property holds for t1 and t2 it holds for
The number of "leaves"
binary tree is defined by
leaves Tip = 1
(Node a t1 t2) = (leaves t1) + (leaves t2)
the number of "nodes" of a binary tree is defined by
nodes Tip = 0
(Node a t1 t2) = 1+ (nodes t1) + (nodes t2)
we shall prove that for any tree
leaves t = 1+ nodes t
Proof: By structural
- leaves Tip = 1 = 1+0 = 1 +
- leaves (Node a t1 t2) =
t1 + leaves t2 = 1+ nodes t1 + 1 + nodes t2 = 1 + nodes