Thursday, August 19, 2010

Proofs aren't meant to convince anyone

Everyone to whom it matters knows that P does not equal NP. If so, why is P vs. NP considered to be one of the most important open questions in mathematics? Why do we need to prove something everyone is already convinced is true?

This question arises from a misconception as to what it is that math does. Gian-Carlo Rota put it best:
Saying that a mathematician's job is to "prove theorems" is like saying that a novelist's job is to "write sentences."
The job of mathematics is not to verify which mathematical statements are true and which are not, but to search for reasons why true statements are true and false ones are not. The majority of original mathematical research is done not trying to settle open questions, but trying to find new and original ways of settling problems that have already been solved. Many interesting mathematical facts have been proven tens, sometimes even hundreds of times over, each time using a different method. If all mathematicians were interested in was if a statement is true, one proof would be sufficient. But when researchers are considering a mathematical statement, they are not just interested in finding out if it's true or not. They're interested in finding out exactly why it is true. Finding a proof is a necessary, though not sufficient, condition for this. In a way, for any open mathematical problem, the Holy Grail is to find the proof: one that would show both that a statement (or its negation) is true and why it is so. For example, everyone knew long time ago that polynomials of degree five are not solvable by radicals. But no one knew why until, in the process of proving this fact, Evariste Galois came up with a theory that determines a necessary and sufficient condition for a polynomial to be thus solvable, from which it becomes obvious why equations of degree greater than four are not.

Mathematicians don't know why P does not equal NP, and they are hoping that someday, one of the proofs of this proposition will answer that question. It may be unlikely that the first proof that is discovered will provide an answer; but what's certain is that there cannot be an answer without a proof of some sort. There's also another, indirect reason why proofs are important: Proofs are fruitful. They usually lead to new insights, new techniques, new theories.

For example, Gödel proved that no consistent system of axioms whose theorems can be listed by an algorithmic procedure is capable of proving all facts about the natural numbers. By proving the same fact using a very different method, Polish logician Alfred Tarski shed some light on the reason why this is true (essentially, he showed why in formal languages that are "rich enough" to contain arithmetic of natural numbers, the set of all true statements has a higher cardinality than the set of all provable statements. Since, if the notion of provability is to make any sense at all, provable statements must be true, there must exist true statements which are not provable). And by proving the same fact by yet another method, British mathematician Alan Turing came up with a brilliant formalization of the notion of computability using a profound concept of Turing machine; his new theory turned out to have a huge impact on both theory and practice of computer science.

No comments:

Post a Comment