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

Proof systems

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 requirement on the proof system and 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 basic steps from which every proof can be constructed: there are definitely proof systems which fail to have this property.  A proof system with this property is said to be finitely presented.  Finally, the system should have information content: that is it should have some things which are provable and other things which are not provable.  A system with 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 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 ...

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

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 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 not proofs!!!  These are examples of some absolutely classic fallacious proofs ...


1=2 (a proof using algebra)

The proof: Where was the mistake?

1=2 (a proof using complex numbers)

This supposed proof uses complex numbers.

The proof:

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?


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

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:

So what is wrong?  This is an example of blindly using math in science!  Can you see the error?



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 numbers n:
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):


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

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?

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

  1. Suppose there is some natural number which cannot be unambiguously described in fourteen words or less.
  2. Then there must be a smallest such number. Let's call it n.
  3. But now n is "the smallest natural number that cannot be unambiguously described in fourteen words or less".
  4. 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!
  5. 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.
  6. Therefore, all natural numbers can be unambiguously described in fourteen words or less!
The flaw in this proof is much more subtle ...  here is a discussion of it.



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



Mathematical 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, whenever n is in the set, n+1 is also in the set. Then every natural number is in the set.

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

  1. The statement is true when n=0.
  2. Whenever the statement is true for one number n, then it's also true for the next number n+1.
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 0 is in the set, and item 2 says that, whenever one number n is in the set, n+1 is also in the set. Therefore, all numbers are in the set).

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!


The golden ratio:

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 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) = fib(n)+fib(n+1).

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


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.

A simple polygon

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 d  points then the two polygons must satisfy (so d-2 interior points):
        i = i1 + i2 + d - 2            b = b1- d + b2 - d + 2 = b1 + b2 - 2d + 2
whence
       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 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!


Well-founded Induction:
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 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:

  1. If n is prime, then n is its own factorization into primes, so the assertion is true for the division-minimal elements.
  2. 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:

  1. if a property holds for Nil  (the minimal element)
  2. and whenever the property holds for t then the property holds for Cons a t) (well-founded relation t < Cons a t)
THEN the property holds for all elements of the list.

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:
  1. if a property holds for Tip
  2. and whenever the property holds for t1 and t2 it holds for Node a t1 t2
THEN the property holds for all trees.

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
  1. leaves Tip = 1 = 1+0 = 1 + nodes Tip
  2. leaves (Node a t1 t2) = leaves t1 + leaves t2 = 1+ nodes t1 + 1 + nodes t2 = 1  + nodes (Node a t1 t2).