With the P=NP problem in the news, this seems like a good time to revisit the distinction between truth and provability.
Start with this P=NP-inspired question:
I don’t need you to answer that question. I just want you to answer an easier question:
If you said yes (as would be the case, for example, if you happen to be sane), then you have recognized that statements about arithmetic can be either true or false independent of our ability to prove them from some set of standard axioms. After all, nobody knows whether the standard axioms of arithmetic (or even the standard axioms for set theory, which are much stronger) suffice to settle Question 1. Nevertheless, pretty much everyone recognizes that Question 1 must have an answer.
Let’s be clear that this is indeed a question about arithmetic, not about (say) electrical engineering. A computer program is a finite string of symbols, so it can easily be encoded as a string of numbers. The power to factor quickly is a property of that string, and that property can be expressed in the language of arithemetic. So Question 1 is an arithmetic question in disguise. (You might worry that phrases like “quickly” or “substantially faster” are suspiciously vague, but don’t worry about that — these terms have standard and perfectly precise definitions.)
What’s true is not the same as what’s provable. This is an elementary observation, and I think you’d have to look long and hard to find a mathematician (or even a philosopher) who considers it controversial. So you might wonder why I’m bothering to harp on it. Answer: I’ve learned from the response to previous blog posts that there’s a small population of extremely vocal commenters who are both deeply confused and curiously passionate about this issue, and who have somehow talked themselves into believing that in mathematics, nothing is true unless it can be proved.
My usual response to these commenters is to pose a question along these lines:
Nobody knows the answer, but pretty much everyone agrees that there is an answer. And moreover, the answer is what it is regardless of whether our favorite axioms can prove it. In fact it’s entirely possible that our favorite axioms can’t settle the question either way.
That’s pretty clear to almost everyone. But occasionally, commenters will take the bizarre stance that Question 3 might have no answer — because, they say, numbers aren’t real anyway, so it makes no sense to ask questions about them (or something like that).
Maybe instead of pointing those commenters to Question 3, I should try pointing them to Question 1. Will they really want to argue that there might be no answer to the question of whether it’s possible to write a program that factors numbers quickly? That’s a pretty concrete question. We can all agree that as of today, nobody knows the answer, and a pessimist might believe that nobody ever will know. But to say that there might be no answer puts you on pretty strange metaphysical turf. I’m not even sure what it would mean for there to be no answer.
If there is an answer, then that answer is a truth that holds independent of what we can prove. If our axioms can’t determine that answer, then so much the worse for our axioms — but there’s still an answer.
This matters because it’s the first baby step toward understanding whether numbers were created or discovered, and why they could conceivably form the fabric of the Universe. Over the next couple weeks, I’ll make occasional blog posts about these issues. Of course you can learn a lot more by reading The Big Questions, but here I’ll stick to addressing simple confusions that have shown up in earlier blog comments.
I’ll try to stick to one simple observation per blog post. Today’s moral is that well formed statements about arithmetic are either true or false, regardless of whether they have proofs or disproofs. I expect that the mathematicians in the crowd will consider this too obvious even to mention, but my blogging experience tells me that it’s not obvious to everyone. I hope this post fixes that.