[FOM] What is a proof?
John T. Baldwin
jbaldwin at uic.edu
Sun Oct 26 18:19:13 EST 2003
These thoughts were stimulated by some of the notes on Corfields book
but are independent enough that I am not going to search for the
inspiration. An alternative title is Why do we prove?
Position A. A proof is a means of establishing the truth of a proposition.
Position B. A proof is an explanation of why a proposition is true.
Position B requires more of a proof than does position A.
A proof in the sense of position B must be a proof in the sense of
Postion A. But not conversely.
I take Position A to be a part of traditional fom.
To raise some hackles: Principia Mathematica was an existence proof for
being able to prove all mathematical truths in Sense A; however, its
method of establishing A, completely defeated any chance of B.
(I deliberately ignore Godel; this statement simply glosses in a
provacative way the effect of PM on the Mathematical community at large
at the time. )
But my goal today is to point out that there are technical tools -
provided by ordinary logic to address Position B.
Standard Definition. 1. A proof is a sequence of propositions each of
which is either an axiom or follows from those earlier in the list by a
rule of inference.
2. A theorem is any line in a proof.
(2 is a commonplace to logicians, a strange convention to other
mathematicians.)
From the standpoint of Position B, the defect of Definition 1, is that
there is no criteria of relevance of the steps of the proof to the
result. If we interpolate a sequence of tautologies in a proof (maybe
many times the length of the original proof) it is still a proof by the
(inadequate) definition 1).
This problem could be addressed by
Definition. 1'. A proof is a sequence of propositions each of which is
either an axiom or follows from those earlier in the list by a rule of
inference and each line is a premise of some later step.
(I came to this conceit by trying to read a published paper which
contained a number of true but irrelevant statements making the actual
proof much harder to comprehend.)
Informally, a proof explains the truth of a proposition if the
hypotheses are adequate to imply the conclusion but not too strong.
(We can prove 2 + 2 =4 from 0 not equal 1; a better explanation is to
use appropriate axioms for arithmetic.) So we could make a criteria for
a proof that for A => B to be a step in the proof there should not
be an A' where A' is as well-established as A and we could equally well
use A' => B (where A=> A' but not conversely.)
One might give the notion of Theorem its usual mathematical use by
refining the notion of `proof' to include the actual practice of
collecting substrings into
Lemma's and applying Lemmas in other instances. Thus `theorems' are used
often, represent repeated submodules in the long proof. (Sorry, just
speculation here.)
The point of this note is that the idea of `proof as explanation' has
content beyond `proof as establishing truth'. Serious exploration of
this distinction would require new ideas. I list a couple of
trivialities simply to show that formal notions can apply.
More information about the FOM
mailing list