home | index | units | counting | geometry | algebra | trigonometry | calculus | functions
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2021   Gérard P. Michon, Ph.D.

Mathematical Proofs
( Utter Removal of Doubt )

What's asserted without proof
can be denied without proof
.
Euclid of Megara  (c.450-374 BC)
 Voltaire  
The interest I have to believe a thing
is no proof that such a thing exists
.
François-Marie Arouet, known as  Voltaire  (1691-1778)
 
Absence of proof is not proof of absence.
Attributed to William Cowper (1731-1800).
Also in a  letter  to  Humbholdt  by  Friedrich Bessel.
 
When you've eliminated the impossible, whatever
remains, however improbable, must be the truth
.
Sherlock Holmes, in  "The Sign of the Four"  (1890)
by  Sir Arthur Conan Doyle  (1859-1930)
 
Mathematical works do consist of proofs,
just as poems do consist of characters
.
Vladimir Arnold  (1937-2010)
 
An ordinary proof is for experts.
A Bourbaki proof is for everybody.

Jean-Pierre Serre  (1926-)
 border
 border
 Gerard Michon

Related articles:


Related Links (Outside this Site)

Proof Wiki
Proofs in Mathematics  by  Alexander Bogomolny.
Fermat's Last Theorem for Cubes  by  Kevin S. Brown.
Patterns That Eventually Fail  by  John C. Baez (2018-09-20).
Theorem of the Day  (related sites)  by  Robin Whitty.
The Hundred Greatest Theorems  (of Paul and Jack Abad)  by  Nathan W. Kahl.

Video :   Proof theory foundations (2013) by  Franck Pfenning   [ 1 | 2 | 3 | 4 ]
Misleading Patterns in Mathematics (7:52)  by  Zach  (MajorPrep, 2019-01-04).
Zero-Knowledge Proof (33:37)  by  Avi Wigderson  (Numberphile2, 2021-02-09).
ZKP: Zero-Knowledge Proof (10:17)  Xavier Decuyper  =  Savjee  (2019-01-14).
Zero-Knowledge Proofs (10:17)  by  Scott Twombly  for CSC555  (2016-04-28).

 
border
border

What's a  Proof ?


(2018-01-10)   Proof by Inspection:  The most elementary type of proofs.
This can be invoked only if there are  finitely many  cases to check.

An example is no proof.   (Yiddish proverb)

In ordinary mathematical discourse, we may say that something is true  by inspection  when there are only finitely many possible instances and the statement is easily checked for every single one of them.

In the past,  we'd only make the claim when there were only a few cases to check;  possibly too many to list,  possibly a tedious task but not an overwhelming one.  In the computer era,  we may also claim that something is true  by inspection  when a  (relatively simple)  computer program has checked all the possible cases.

Arguably,  proper mathematics consists in producing proofs of statements applicable to infinitely many things,  not  statements true  by inspection.

Infinity marks the beginning of proper mathematics.


(2007-01-09)   Only "negatives" are worth proving.
"You can't prove a negative"  is a proverb about  tests,  not proofs.

To a mathematician,  proofs  are not restricted to mere  tests.  Arguably,  the aforementioned word  negative  doesn't mean much,  since grammatical form is only incidental.  To play along,  we'll dub the first of the following sentences  positive  and the second one  negative :

  • A square  can  be the sum of two nonzero squares.
  • A cube  cannot  be the sum of two nonzero cubes.

Both statements are true in the realm of  integers.  The first one can be  proved  by just one example  (the most popular of many is 25 = 16+9).  On the other hand,  the second statement tells that counterexamples do not exist...  The evidence for such an affirmation can only be a detailed piece of rigorous reasoning;  a proper proof.  A lack of solutions can't be established by many failed attempts.  That's probably what was meant by whoever coined the above proverb,  which doesn't apply to  mathematical proofs.

A proof that a cube can't be the sum of two cubes can be given using the  Method of Infinite Descent  due to  Pierre de Fermat (1601-1665).  A simpler example of that method is a clever 2-line proof  (which repays study)  that  there's no rational whose square is  2 :

Since 1 < Ö2 < 2,  if a positive integer  n  was making  nÖ2  an integer, the  smaller positive integer  m = (Ö2-1) n  would make  mÖ2  an integer also!  QED

Another proof  invokes the concept of divisibility.  It may be easier and more intuitive, but it's less  elementary  (it relies on more  previous  knowledge).


(2012-06-11)   Proof by induction   (Gersonides, 1321)
The basic way to prove a statement about infinitely many things.

The elementary type of induction  (as taught at the high-school level)  pertains to integers:  To establish that some statement  P(n)  is true for all nonnegative integers, you only have to show that:

  • P(0)  is true.
  • Assuming the truth of  P(i)  for every  i < n  (the so-called  induction hypothesis)  it can be proved that  P(n)  is true.
Although the first part is pleonastic  (it's only a special case of the second part with  n=0, with a vacuous induction hypothesis)  it's useful to keep it, since the proof of the second part would otherwise almost always start with a distinction between  n=0  and the other cases.

That type of elementary induction could be reformulated to apply to the elements of any  countable  set.

However, the general concept of induction  (sometimes known as  structural induction )  has no such restrictions.  Loosely stated:

If something is true of the simplest things and can be shown to hold true of more complex things by assuming it's true of simpler ones, then it holds true of the most complex things.

In this context, it's just assumed that those "most complex things" are structually composed of simpler ones in a predefined way.  For example, Conway's surreal numbers are simply built from simpler surreal numbers.  Structural induction can thus be used to establish the validity of a statement about all surreal numbers  (there are uncountably many of them)  in a way that does not reduce to simple induction on integers.

The Peano axioms   |   Transfinite induction


(2007-01-16)   Stochastic proofs are wrong with  vanishing  probability.
Sometimes, an elusive truth is reinforced by many failures to attack it.

One celebrated example is the iterated Rabin-Miller test which tells (beyond the shadow of a doubt) whether a large number is prime or not, without actually  proving  anything when that number happens to be prime...  For a composite number, each iteration stands a substantial chance (over 75%) of proving it's not prime.  Thus, if several iterations fail to provide such a proof, we may be very confident that the number is indeed prime  (the probability of error decreases  exponentially  with the number of iterations).

Another example consists in determining whether a (large) finite group is cyclic  (knowing the factorization into primes of its order).  A finite group is cyclic if and only if it has a primitive root.  It turns out that a random element of a cyclic group is primitive with a fairly large probability  (and it can be proved to be primitive very efficently if the prime factors of the group's order are known).  Thus, if many random elements turn out not to be primitive, then the group is "almost surely" not cyclic. 


(2007-01-16)   Heuristic Arguments
Establishing the likelihood of a conjecture with an approximative proof.

For example, I argue (against the dominant opinion) that there are probably infinitely many Wieferich primes, although only two of them are known  (in spite of great efforts to find a third).

A proper heuristic argument is not a hasty generalization.  It's actually a strict mathematical proof about a modified problem, where part of the original mathematical structure is substituted with a probabilistic model.  Quantitative conclusions from such a model can be enlightening while an exact solution to the original problem remains elusive.  This may be construed as "relaxing" some mathematical constraints while retaining the problem's essential aspects.

A good heuristic argument must be supported with convincing  justifications  of the probabilistic assumptions underlaying the model.  A heuristical argument is never foolfproof (or else it would be a proper mathematical proof) but it should be nearly so...  The qualifier "heuristic" shouldn't be an excuse for sloppiness !

The accepted heuristic arguments gave the  wrong  answer for a paradoxical result which has now been proved rigorously:  Maier's theorem (1985).


(2013-05-01)   Computer-Assisted Proofs
Appel & Haken used a computer to prove the 4-color theorem (1976).

They were able to reduce the general case to 1936 special cases that could not be reliably checked by hand.  The fact that a legitimate proof of a major theorem had not been verified by a human being raised eyebrows at the time.

At a more modest level,  I once produced  (2002-07-08)  a satisfying proof of a long-standing conjecture of mine by reducing it to  1172  very simple computations.  In that case,  it would have taken only a few hours to do so  by hand,  but I must confess that I never did.  There was no need for that,  as I could write a  tiny  computer program to do it for me.

The fact that I had previously enlisted the help of a computer to  find  the magic modulus  1171  (and other larger suitable ones)  is irrelevant to the final proof.  The creativity involved,  if you must call it that,  resides entirely in the  idea  that such a modulus might exist.

Such proofs are getting more and more common these days.  Admittedly,  they ultimately rely on the proper working of a computer.  However,  the correctness of the computerized procedure has to be established the old-fashioned way.  Therein lies the crux of the proof.

The four-color theorem  (historical perspective)  by  John J. O'Connor  and  Edmund F. Robertson.
Kenneth Appel (1932-2013)   |   Wolfgang Haken (1928-)


(2009-06-21)   Ruling out proofs
Facts which can't be established by some or  all  types of proofs.

Generations of mathematicians have attempted to prove Euclid's fifth postulate of plane geometry from the other four axioms of Euclidean geometry.  It is now known that such a proof is not possible.  The reason why this is so is rather subtle:

If Euclidean geometry  (including the fifth postulate about parallel lines)  is at all consistent, then it can serve as a framework to describe other surfaces besides a plane.  One such surface is the sphere...

The geometry of the surface of a sphere provides one example where the first four axioms of Euclid are verified with suitable redefinitions of the concepts involved  ("points" are actually pairs of diametrically opposite locations and "lines" are great circles).  Yet, the fifth postulate is not verified, as all "lines" intersect  (there is no such thing as two "parallel" great circles).

Therefore, the fifth postulate  cannot  be a consequence of the other four.  Note that this conclusion can be reached without settling the question of whether the Euclidean postulates are consistent or not.  We just note that  if  they are consistent, then a consistent "model" can be constructed  (spherical geometry)  where the fifth one is false.  Hence, that fifth postulate is truly an independant axiom which may be assumed to be true or false.

In examples of lesser historical significance, similar arguments can be used to rule out some types of proofs for a given statement.  For example, "Fermat's last theorem" can be shown to be false within certain "models"  (involving beasts like p-adic integers).  This shows that it is a so-called  global  statement whose proof must involve some peculiar property of the rational integers besides ordinary algebra, ordering and divisibility by finitely many prime numbers.  The proof must involve something very specific to the integers, like the validity of Fermat's own infinite descent method...


(2016-01-30)   Power Tools
The worth of some general theorems is in the proofs of other theorems.

In mathematics, any proven result can be called a theorem.  However, that name is best reserved to general results which give rise to interesting proving techniques.  Here are a few examples:

  • Pigeonhole principle (Dirichlet, 1834):   If there are fewer drawers than items stored in them, there is a drawer with several items in it.
  • Fundamental theorem of arithmetic :   Factoring into primes.
  • Fubini's theorem (1907):   Switching the order of integration in a double integral  (also applicable to  absolutely  convergent series).
  • Cauchy's residue theorem.  A contour integral in the complex plane equals the sum of the residues at the singular points it encloses.
  • Stokes' theorem :   The integral of a form's derivative over some domain equals the integral of the form over that domain's border.
  • Feit-Thompson theorem (1963):   All finite groups of odd order are solvable.  This led to the full  classification theorem  (1982).

The Most Overpowered Theorems (Mathematics Stack Exchange, Nov. 2013)


(2018-09-22)   Treacherous Patterns
Some  obvious  generalizations may not be true...

Inspired by  Greg Egan  (2018-09-16John Baez  remarked  (2018-09-21)  that the following equality holds when  n  is below  9.8 1042  but surely  fails  when it's above  7.4 1043.

 Come back later, we're
 still working on this one...

Greg soon proved that this equality holds if and only if:

n   <   15341178777673149429167740440969249338310889   =   1.534... 1043

Patterns that eventually fail  by  John Baez  (2018-09-20).


(2019-05-17 13:00 PDT)   A botched proof of  Fermat's last theorem.
Fermat  himself most likely had in mind an  invalid  argument like this.

Famous  open problems  have always attracted the attention of people poorly equipped to tackle them.  Well,  the very fact that a problem remains open long enough to become famous shows that  almost nobody  is up to it!

If  you  ever find an  easy  solution to something which has resisted the attacks of the best mathematicians for decades  (or centuries)  you can be  dead sure  that you've made a mistake somewhere.  Problems with easy solutions get solved before they become famous.

Legend has it that a prestigious mathematics department once entrusted graduate students to fill out a  pre-printed form  in reply to proposed proofs of Fermat's last theorem,  just pointing out the location of the  first mistake.

As I received one such claim again  in print  a couple of days ago.  It looked at first like a classical mistake.  I was wrong  (it was something even more trivial)  but the mistake I had in mind is interesting enough to discuss as an example of  what not to do.  Here we go:


We only have to consider odd values of the exponent  n,  since a solution for any other exponent beyond  2  would translate into a solution either for exponent 4  (a well-known impossibility)  or for such an odd exponent  n :

c n   =   a n  +  b n             (a > 0,  b > 0,  n ≥ 3  is odd)

In this,  c n  must be divisible by  s = a+b > 1  since,  for any  odd  n :

c n   =   a n + b n   =   a n - (-b)n   =   (a+b)  
n-1
å
i = 0
  a n-1-i  (-b)i

Let   x  =  a + b - c.  We have  c  =  s - x  and,  by the  binomial theorem :

c n   =   ( s - x )n   =    
n
å
i = 0
  (  n 
i
)   s n-i  (-x)i

As this sum and its first terms are divisible by  s,  so is the last term  (i = n).  That means that  x n  is divisible by  s > 1.  (So,  x  and  s  aren't coprime.)

Let  w  be the  greatest common divisor  of  x  and  s,  which is to say that we have two  coprime  positive integers  u  and  v  such that:

x  =  w u       and       s  =  w v       (where  u < v   since  x < s).

As we knew both sides of our last equation to be divisible by  v w,  we may cancel  one  w  and obtain an equation whose two sides are divisible by  v:

w n-1  ( v - u )n   =   w n-1  
n
å
i = 0
  (  n 
i
)   v n-i  (-u)i

The last term of the rightmost sum is  -u n,  which is coprime with  v  because  u  is.  As  v  divides its other terms,  that sum is coprime with  v.

Therefore,  the overall divisibility by  v  (only)  proves that  v  divides  wn-1

The mistake would have been to ignore that possibility and carelessly cancel all factors of  w  leading to a contradiction and a fake "proof".

border
border
visits since January 15, 2007
 (c) Copyright 2000-2021, Gerard P. Michon, Ph.D.