What is a proof?
What is a proof? Well that is a much harder question than
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 you
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 it
step is valid then the whole argument will be valid!
If there is an error in the proof then it will become apparent because
one of the small steps into which you have broken the argument must be
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 problem
Errors of this nature are a normal occurrence in the
process of developing mathematical ideas .... but it is worth remember
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 can
a program behave in an arbitrary bad way! This should make one
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 of
proofs. Just as a program is developed in a particular
so a proof belongs to a particular proof system. In mathematics
are a number of well-known proof systems: equational proofs,
and predicate logic proofs, inductive proofs, coinductive proofs, etc.
So this raises an interesting question: what does a good proof system
look like? Clearly a rather crucial aspect is that one should be
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 requirement
fails. A proof system with this property is called compositional.
It is also important that there are a small (finite) number of
steps from which every proof can be constructed: there are definitely
systems which fail to have this property. A proof system with
property is said to be finitely presented. Finally, the
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 non-trivial
task. In the beginning of the 20th century there was a
significant effort to try to establish the foundations of mathematics.
This culminated in various axiomatizations of set theory, the
development of proof theory, and indeed the theory computability.
fact that these developments were not straightforward is indicated by
the litter of "paradoxes" (Russell's paradox, the liar paradox,
...) 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 attempts
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 mathematician's
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 subsequently
greatly influenced the development of mathematics itself.
Hilbert believed that by steadily breaking any problem down one could
with diligence determine whether it was true or false. Undecidability
had no role in his world. Brower, who was also a well-known
Dutch mathematician, had a philosophically rather different view which
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 not
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 that
everything was either true of false make perfect sense but also it was
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 the
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 that
Hilbert's philosophical view of mathematics was wrong.
Significantly even some of the problems he described in the very same
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 didactic
reasons: set theory is consistent even if is not the whole story and,
as a foundation, it is more easily explained (or at least more widely
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 "what
is a proof?" but I hope the discussion and historical remarks
The "proofs" below are to help you realize how easily one can come off
the rails. Great care is needed when you are proving something and that
you must really understand the individual steps. Furthermore, you
understand the system in which you are working. Can you determine
the proofs below are not proofs!!! These are examples of
absolutely classic fallacious proofs ...
1=2 (a proof using algebra)
Where was the mistake?
- Let a=b.
- This can be written as ,
- and canceling 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 the
ladder horizontally away from the wall, at constant speed v.
The claim is that this causes the top of the ladder to fall infinitely
Common sense tells us this can't possibly be true, but can you find
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 of
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 with
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 nonzero, while
the denominator approaches zero.
- Therefore, y' approaches as x approaches L. In
other words, the top of the ladder is falling infinitely fast by the
time the bottom has been pulled a distance L away from the wall.
The next two fallacious proof uses proof by induction. This is a
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 (which
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
the number of people in Calgary.
The proof of Statement S(n):
- In any group that consists of just one person, everybody in the
group has the same age, because after all there is only one person!
- 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),
it 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 that, in
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 age.
- 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 the same
(since we are assuming that, in any group of k people, everyone
the same age).
- Consider everybody in G except Q.
Again, they form a group of k people, so they must all have the
- Let R be someone else in G other than P
or Q. Since Q and R belong to a group in which
the ages are the same (all the people except P) they are the same age.
- Similarly, since P and R belong to such a group
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 that
everyone in G has the same age.
- The proof is now complete: we have shown that the statement is
true for n=1, and we have shown that whenever it is true for n=k
it is also true for n=k+1, so by induction it is true
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 give
surprise quiz. A clever student in his class reasoned as follows
(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 class
which will be day 0.
- Say that U(n) holds when n is a day on which the
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 after
a given day then a test that day will not be a surprise (because the
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
- The principle of strong induction now says that U(n) must
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" means
an ordinary English word, such as you or i might find in a dictionary.
You know this can't be true. After all, there are only finitely many
words in the English language, so there are only finitely many
can be built using fourteen words or less. So it can't possibly
be true that every natural number can be unambiguously described by
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 be
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 supposed not
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 or less
a contradiction, it must be an incorrect assumption.
- Therefore, all natural numbers can be unambiguously described in
fourteen words or less!
When is a
proof a proof?
I am not going to tell you the answer to this. However, what I
do wish to mention is that even a short proof can demonstrate something
quite surprising. So surprising that it can have significant
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 Hippasus
discovered irrational numbers
when trying to represent the square root of 2 as a fraction (the proof
Unfortunately for him it wasn't until much later, when Eudoxus
a theory of irrational ratios, that Greek mathematicians accepted
numbers. Pythagoras, in particular, believed in the absoluteness
numbers and would did not accept the existence of irrational numbers.
However, neither could he find the fallacy in Hippasus's proof.
As he could
not accept the conclusion (and admit that his philosophical ideas were
sentenced Hippasus to death by drowning!
Please do not let this cautionary tale discourage you from getting
your proofs right! The power of life and death over students is
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 the
initial assumption must be wrong.
Can you think of other proofs that have been just as controversial?
Principles of induction
The principle of mathematical induction says this: suppose you
have a set of natural numbers (natural numbers are the numbers 0, 1, 2,
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 is
collection, but also you notice that for each number k that you
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, you
will eventually get to every number.
The principle of induction is extremely important because it allows
one to prove many results that are much more difficult, or impossible,
to prove in
other ways. The most common application is when one has a statement one
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 n.
In that case, one appeals to the principle of induction by showing
If you can prove those two things, then the principle of induction says
that the statement must be true for all natural numbers. (Reason: let S
be the set of numbers for which the statement is true. Item 1 says that
is in the set, and item 2 says that, whenever one number n is
set, n+1 is also in the set. Therefore, all numbers are in the
- 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 be
true). However, it is easy to prove by induction: it's true when n=1
= 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. These
facts, combined with the principle of induction, mean that it's true
A consequence of mathematical induction is course-of-values
induction (also known as complete induction or strong
induction) which says, given a set of natural numbers, if you
know n is in the set whenever each i < n is in the
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 set. Define
of the set, namely those number for which all predecessors are in the
set. O is certainly in
this subset. Let k be
any number in
this set, as all of its predecessors are in the original set, then it
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 Fibonacci
fib(n) =( G^n - (-1/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 formula.
Now suppose fib(k) for every k < n+2 satisfies
the formula (we have dealt with 0 and 1) then
fib(n+2) = fib(n) + fib(n+1)
= (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 quadratic
G^2 -G -1 = 0
for which G as defined is a root! This is how Fibonacci found
Least number principal:
The least number principle says that any non-empty set of
numbers has a least element. This can be used to do a
minimal counterexample: given a set which does not contain
numbers there must be a least number not in the set. Suppose you
show that there is no minimal counterexample (typically by using the
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 smaller
m not in the set then,
whenever everything smaller
than the given element n is
in the set, n must be in the
set. So one can apply complete induction to conclude the
set is all natural numbers.
Given a simple polygon constructed on a 2-dimensional grid of points
with integer coordinates such that all the polygon's vertices are grid
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 contain
The result was first described by Georg Alexander Pick in 1899. It
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. We
shall suppose that there is a polygon which is a counterexample which
a minimum number of grid points. Either the polygon involves
three grid points (in which case it is straight forward to check Pick's
formula actually holds) or it is possible to split the polygon into
smaller polygons by drawing a cord across the polygon. The sum of
areas of the two smaller polygons is then the area of the original.
If the path across the polygon involves d points then the
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 polygons
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 is an
integer, is an irrational number!
Let S be a
non-empty set, and R be a binary
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 element.
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 divides
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
element of X must be in S as there are no elements
below such an element so all of them are in S!
Now in fact a relation for which this principle of induction is holds
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 the
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 order
is not the successor or the usual ordering on numbers, consider the
fundamental theorem of arithmetic: every natural number has a prime
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 induction, r
have prime factorizations, and therefore n has one too.
In a programming language, such as Haskell, programming is done using
datatypes. For doing proofs over datatypes a form of mathematical
induction called structural induction is often used. It is an
instance of well-founded induction which relies on the fact that there
is a well-founded relation
on all (inductive) datatypes.
Given an (inductive) datatype which is built by applying constructors
data D(a) = C1 T11(a,D(a)) T12(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 given by
t2 < t1 whenever t1 is a (strict subterm) of t2 and there are to subterms of the
datatype between t1 and t2
t1 = s[t2/x] means t2 < t1
whenever the term \x -> s(x) has type X ->Ti(a,X).
For the natural numbers defined
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 induction.
data List a = Nil | Cons a
the relation gives t < Cons(a,t) which then allows us
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
(the minimal element)
- 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 < Node
a t1 t2 so that we get the following structural induction scheme
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 Node a
The number of "leaves" of a
binary tree is defined by
leaves Tip = 1
leaves (Node a t1 t2) = (leaves t1) + (leaves t2)
the number of "nodes" of a binary tree is defined by
nodes Tip = 0
nodes (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) = leaves
t1 + leaves t2 = 1+ nodes t1 + 1 + nodes t2 = 1 + nodes (Node a