Topics Mathematics

Question If we prove that a proof exists, why isn't this effectively the same as finding the actual proof?

Accepted:
February 9, 2008

Comments

To start with a story. Once upon a time, I used to teach introductory logic using Lemmon's textbook. And some exam questions would have the form "Use truth-tables to test the following arguments for validity; in the cases where the argument is valid, provide a proof from the premisses to the conclusion in Lemmon's system". Given that Lemmon's natural deduction system is complete, a student who correctly did a truth-table showing that a particular argument is valid thereby proved that there is a proof from the premisses to the conclusion. But of course, she had to do more to answer the second part of the question, and get the marks! She had to give an actual natural deduction proof.

This little story reminds us that, quite often, we aren't just looking for any old proof, but for a proof of a certain style S, a proof that uses certain kinds of resources. And proving that an S-proof of some result exists isn't in general to give an S-proof.

This sort of point applies outside the logic classroom too. For example, a number theorist may be quite convinced that there must be an "elementary", purely numerical, proof of some result about the prime numbers (for example) because she knows the result is true since there is a fancy heavy-duty proof of it calling on more exotic mathematics. Actually finding a more elementary proof itself be a hard problem.

But let's suppose now that we are approaching some problem with no particular presumptions about the general kind of proof we want. Then, in this sort of case, is proving that a proof exists as good as finding "the actual proof"?

Well, here's another story. The great mathematician Paul Erdös liked to talk of "The Book" in which God keeps the most beautiful mathematical proofs. And there's a lovely volume Proofs from The Book which gives us lots of really elegant proofs of the kind Erdös had in mind. The very first chapter -- which is pretty accessible even if you know just a smidgin of mathematics -- gives no less than six proofs (taken from a much longer list, say the authors) that there is an infinite number of primes. Which is a vivid reminder that there need be no such thing as "the actual proof" of a result, even if we are only looking at proofs worthy of being put into The Book.

So let's rephrase the question again. Suppose we are approaching some problem "is it the case that P?" with no particular presumptions about the kind of proof we want. Then could something describable as proving that there is a proof that P be one acceptable way of demonstrating that P is true?

To which the answer seems to be "Yes". (Perhaps some cases where we use a computer to validate an argument too long for us to check could be said to fall under that description.)

Question If we prove that a proof exists, why isn't this effectively the same as finding the actual proof? Accepted:February 9, 2008

Question If we prove that a proof exists, why isn't this effectively the same as finding the actual proof?

Accepted:
February 9, 2008