What is a proof? Well that is a

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 each step can be individually examined to see whether it is valid -- if each step is small enough one should be able to easily determine whether it is correct. When each 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

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 modules are small enough and well circumscribed enough they can easily be tested and documented. An error in any one of the modules, on the other hand can make a program behave in an arbitrary bad way! This should make one suspect that there is a close relationship between proofs and developing programs .... and there absolutely is. These connections have been made quite 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 programming system so a proof belongs to a particular proof system. In mathematics there are a number of well-known proof systems: equational proofs, propositional 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 able to decompose proofs into basic steps and then form the proof by composing these steps. This is a

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 axioms for set theory, the development of proof theory, and indeed the theory computability. The 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 paradoxes were developed as signpost to the boundaries of where set theory and logic becomes degenerate. Famously some of the early attempts at "set theory" turned out to be degenerate but fortunately for mathematics were corrected ...

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

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 turned out to be undecidable. Brower had been right! Godel's results ultimately led to a much better understanding of the link between computability and provability. 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 felt: the hubris of results of 20th century mathematics built on these foundations made it even more difficult to "leave the paradise".

Well you probably are no further along in answering the question "what is a proof?" but I hope the discussion and historical remarks make you mighty curious!

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 have to understand the system in which you are working. Can you determine why the proofs below are

- Let
*a*=*b*. - Then ,
- ,
- ,
- ,
- and .
- This can be written as ,
- and cancelling the from both sides gives 1=2.

**The proof:**

- -1/1 = 1/-1
- Taking the square root of both sides:
- Simplifying:
- In other words,
*i*/1 = 1/*i*. - Therefore,
*i*/ 2 = 1 / (2*i*), -
*i*/2 + 3/(2*i*) = 1/(2*i*) + 3/(2*i*), -
*i*(*i*/2 + 3/(2*i*) ) =*i*( 1/(2*i*) + 3/(2*i*) ), - ,
- (-1)/2 + 3/2 = 1/2 + 3/2,
- and this shows that 1=2.

Common sense tells us this can't possibly be true, but can you
find
the flaw in the following supposed "proof" of this claim?

**The proof:**

- 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 triangle, .
- Therefore, .
- 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**

The conclusion follows from that statement by lettingStatement: In any group ofS(n)npeople, everyone in that group has the same age.

**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*. These people form a group of*k*people, so they must all have the same age (since we are assuming that, in any group of*k*people, everyone has the same age). - Consider everybody in
*G**except**Q*. Again, they form a group of*k*people, so they must all have the same age. - 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*are 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
a
surprise quiz. A clever student in his class reasoned as
follows
(using the principle of strong induction see below):

- 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 teacher 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*U(n)*holds. - The principle of strong induction now says that
*U(n)*must hold for all*n*!

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 sentences that 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 proof:**

- 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 led to 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
effects ...

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
is below).
Unfortunately for him it wasn't until much later, when
Eudoxus
developed
a theory of irrational ratios, that Greek mathematicians accepted
irrational
numbers. Pythagoras, in particular, believed in the
absoluteness
of
numbers and 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
wrong) he
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
divides

*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

To state it more informally: suppose you have been collecting
numbers and the number 0
is
in your
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
difficult to
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

- 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
(as 1
= 1(1+1)/2), and whenever it's true for one number *n*,
that
means
1+2+3+· · ·+*n *= *n*(*n*+1)/2,
so 1+2+3+·
· ·+*n*+(*n*+1) = *n*(*n*+1)/2 + (*n*+1)
= (*n*+1)(*n*+2)/2, so it's also true for *n*+1.
These
two
facts, combined with the principle of induction, mean that it's
true
for
all *n*.

Complete induction:

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
the set.

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
a subset
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
is
in the original set
and so k+1 is in the
subset. But this means the subset contains
all
numbers whence the original set did!

An example of the use of strong induction is to derive the
Fibonacci
formula:

*fib(n) =( G^n -
(-1/G)^n)/
sqrt(5)
*where

G = (1+ sqrt(5))/2

and the Fibonacci sequence is given by

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:

G^2 -G -1 = 0

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
proof by
*minimal counterexample*: given a set which does not
contain
all
numbers there must be a least number not in the set. Suppose
you
can
show that there is no minimal counterexample (typically by using
the
fact
that it is a counterexample to construct another smaller
counterexample) then
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.

**Picks theorem:**

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

The result was first described by Georg Alexander Pick in 1899.
It
can be generalized to three dimensions and higher with Ehrhart
polynomials.
The formula also generalizes to surfaces of polyhedra.

**Proof:
**Every polygon must involve at least three grid points.
We
shall suppose that there is a polygon which is a counterexample
which
involves
a minimum number of grid points. Either the polygon
involves
only
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
two
smaller polygons by drawing a cord across the polygon. The
sum of
the
areas of the two smaller polygons is then the area of the
original.
If the path across the polygon involves

i = i1 + i2 + d - 2 b = b1- d + b2 - d + 2 = b1 + b2 - 2d + 2

whence

= i1 + i2 + ½

= (i1 + i2 + d - 2) + ½( b1 + b2 - 2d +2) - 1

= i + ½

so this cannot be a counterexample unless one of the smaller polygons is already a counterexample. So there are no minimal counterexamples!

A neat application of Pick's theorem is to show:

*It is impossible to draw an equilateral triangle with its
vertices
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 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

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 and relations for which arguments by (well-founded) induction work are 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 well-founded or not.

Fundamental 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 factorization.

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
and s
have prime factorizations, and therefore n has one too.

Structural induction:

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 to arguments:

data D(a) = C1 T11(a,D(a)) T12(a,D(a)) ... T1m_1(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) < Succ(Succ(Zero)) ...

thus structural induction in this case is mathematical induction.

For lists:

data List a = Nil | Cons a (List a)

the relation gives t < Cons(a,t) which then allows
us
to
do structural inductive proofs using the principle of structural
induction for lists:

- 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 datatype by:

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 for trees:

- if a property holds for Tip
- and whenever the property holds for t1 and t2 it holds for Node a t1 t2

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 induction

- leaves Tip = 1 = 1+0 = 1 + nodes Tip
- leaves (Node a t1 t2) = leaves t1 + leaves t2 = 1+ nodes t1 + 1 + nodes t2 = 1 + nodes (Node a t1 t2).