Video : Proof theory foundations (2013) by Franck Pfenning [
1 |
2 |
3 |
4 ]

What's a Proof ?

(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, in the above adage, the very word "negative" lacks clear meaning as well
(since most statements could be cast in either "positive"
or "negative" forms).
To play along, we should 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...
That affirmation can only be supported by a piece of reasoning,
since a lack of solutions can never be demonstrated by many failed attempts.

To the author of the above infamous proverb,
such a thing was clearly inconceivable.
Yet, it's precisely what mathematicians call a proof.
Once you've seen and understood just one such proof, you'll know better.

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!

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

(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 are not 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 probablyinfinitely 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 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.

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