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.
Since I am obviously one of these that your “blogging experience tells [you] that it’s not obvious to” I’d better get stuck in.
(If I am just annoying you be repeating idiotic statements and should know better, please just delete my comment and I will use that as a signal to go away).
You have based your argument on the idea that “true” is a rock-solid, well-formed concept, even though you have left it undefined. Maybe it isn’t.
As you have pointed out and I think everybody knew already, efforts to define “true” as “derivable mechanistically from axioms” have failed, and are proven to be impossible without leaving an unexcluded middle (propositions which we really want to say are true but can’t prove mechanistically).
“But to say that there might be no answer puts you on pretty strange metaphysical turf.”
It’s pretty strange turf to say “clearly propositions are either true or false” without saying what “true” and “false” means first.
Here are some options:
1. Generally accepted as true by professional mathematicians (socially constructed, yuck).
2. Derivable from axioms (leaves an unexcluded middle, Prof. Lansburg rejects this option)
3. It’s just obviously true, dammit! (intuitive)
4. something else?
You seem to be going for 1 or possibly 3.
If your definition is not formal, thats fine. At least you have one — most people don’t, including me.
But it would advance the discussion to at least say what it is.
You say mathematicians will hold to this, but what about constructivists? And ultrafinitists like Doron Zeilberger? I don’t hold to those views necessarily, but mathematicians don’t speak with a single voice on this point.
Ben: You ask what “true” means. None of your options 1, 2 or 3 comes close to the right answer.
Take the statement “It is not possible to write a computer program that factors numbers quickly”. This statement is true if and only if it is not possible to write a computer program that factors numbers quickly. It is false if it *is* possible to write a computer program that factors numbers quickly. (Of course we need to specify exactly what we mean by “quickly”, etc, but I’m assuming we’ve done all that.)
Is there something about this criterion that is not clear to you?
PS: You are not annoying and I appreciate your being here.
Is it a requirement that we *prove* it can factor any number quickly, or that it just does it for all the numbers we have tried?
4. Empirically/experimentally true, i.e we have done a good, best-effort search of the problem space, found many confirming examples, and no disconfirming examples, and have good theoretical reasons for thinking our search adequate. (Induction, not in the mathematical sense)
I’m guessing that won’t do either?
Or is the requirement that it *actually would work for all numbers* regardless of whether we can prove it?
5. The proposition is true of objects in an underlying reality (a platonic world of arithmetic). I.e the terms used in the proposition correspond to objects and relations in the platonic world, in the same way that ordinary statements correspond to physical objects and relations (or fail to, if false). (Metaphysical)
I would favour 4 if I had to go for one. I have a feeling that you would favour 5, or a better-phrased variation?
(By “faster”, I assume you mean deterministic polynomial time without a quantum computer, since Shor’s algorithm is deterministic.)
Ben:
Is it a requirement that we *prove* it can factor any number quickly, or that it just does it for all the numbers we have tried?
Neither. It’s a requirement that it *can* factor any number quickly.
In other words, this: it *actually would work for all numbers* regardless of whether we can prove it
The answers to questions 1 and 2 are Yes. There are computer programs that factor integers in subexponential time, whereas naive trial-and-error takes exponential time. Eg, see Integer factorization.
Are there three ways we can classify true statements: provable (proven), not provable, and not yet proven? In the first case, statements are true and provable from axioms. In the third, such as Steve’s example of even numbers being the sum of two primes, we believe them to be true (or perhaps I should say there is no evidence to the contrary), but they haven’t been proven yet. And aren’t there also some statements that are known to be true, but it is also known they can’t be proven? I’m not very knowledgeable in this area, but I thought that’s what Godel’s incompleteness theorems explained.
It strikes me that you’re trying to fix a particular instance of the problem “people on the Internet are being wrong.” I admire your fortitude even as I doubt your probability of success.
Roger Schlafly: I am taking “substantially faster” to mean “in polynomial time”.
Prof. Landsburg, thank you for the reply.
What I am struggling with is, what does it mean to say “it actually would work for all numbers” if
1. you can’t prove it from axioms (definition 2), and
2. you can’t accept an empirical proof (definition 4), and
3. you can’t *actually* try it for all numbers?
I guess we could say: “It means that for any number I picked, it would work”.
And that seems to work just fine for your one example question 1. So in that sense, it seems that *this* question 2 must have an answer, whether we can prove it or not.
But is there a way to understand the statement “for any number I picked, it would work”, other than as a proposition about what might happen in the future?
By appealing to future results to justify a metaphysical truth, have I folded definition 5 into definition 4?
I am asking that in a genuine spirit, I am not just trying to split hairs. It certainly looks, and feels, like the statement “for any number I picked, it would work” has to be true or false.
But when I try to ask “what does it actually mean”, except as an empirical proposition, it slips away.
Ben:
I am asking that in a genuine spirit, I am not just trying to split hairs.
I understand this. And I’m still glad you’re here. :)
Your 1,2, and 3 confuse the question “What does it *mean* to say it would actually work for all numbers?” with the question “How could we *know* it would actually work for all numbers?”. Your 1,2, and 3 address the latter question, not the former.
But is there a way to understand the statement “for any number I picked, it would work”, other than as a proposition about what might happen in the future?
It is a statement about what will happen in any *possible* future. It has nothing to do with what the actual future might or might not hold.
Your argument is that there are some statements that must be either true or false, even if we can have no way of ever finding out. Do you say the same about other statements, such as: God exists, Schroedinger’s cat is alive, there were other universes before the big bang, electrons have free will, Buddha was enlightened, Obama is the antichrist, the chicken came before the egg, there is a singularity in a black hole?
Truth and provability may be even more complicated than that because the assumption that truth is a constant may not be correct.
As far as I can tell, the answer to Questions 1, 2 and 3 are yes. Each of the questions is in the form of “X or not X.” Such propositions would seem to obtain under any truth-value of X.
2?
Never underestimate the power of a determined mind to miss the point of the discussion….
Roger Schlafly: Any statement is either true or false. Only a string of well-defined words counts as a statement. So “God exists” becomes either true or false once you tell me what you mean by God. “There were other universes before the Big Bang” becomes true or false once you tell me what you mean by “before”, which is not so obvious in this context. Et cetera.
I think that some people (me, maybe other people, maybe just me) are confused about how something can be simultaneously true and unprovable. For instance, say I discover a way to factor large numbers substantially faster than by trial-and-error. Have I not then proved that there is a way to factor large numbers substantially faster than by trial-and-error?
Is the issue proving that there is NOT a way to do this? If the statement is “there is no way to factor large numbers substantially faster than by trial-and-error”, and it is true, are we to just go by induction–no one has found a way, so there must not be a way? Is that what is meant by true and unprovable–true and only inducible?
Colin: Suppose you find a way to factor large numbers substantially faster than by trial and error. Suppose that this method always works. (By which I mean that it works no matter what number you feed it, and always will, for any number, not just the numbers you’ve already tried.)
It does not follow that you can *prove* that your method always works. Perhaps there is no proof. (By which I mean that no sequence of symbols constitutes a proof of this proposition, including the sequences you’ve tried and the sequences you haven’t tried.)
If this were the case — and it perfectly well could be — then it would be true but unprovable that your method factors large numbers quickly.
Ohhhhhhh. That was a lightbulb.
In that case though, hypothetically, would it be possible for me to say, in genuine honesty, “it is true but unprovable that there is a way to factor any number quickly”, or would I have to say “I am pretty sure that there is a way to factor any number quickly, based on the fact that I’ve tried this with a billion numbers and it has worked for all of them, but it still might not work for all numbers”.
Scott Aaaronson says much the same about the P vs. NP question at the end of his essay is P vs NP formally independent:
http://www.scottaaronson.com/papers/pnp.pdf
“So I’ll state, as one of the few definite conclusions of this survey, that P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.”
Colin: you may or may not be able to *say* “it is true but unprovable that XXXX” – as Aaronson suggests, it may be impossible even to prove that it’s unprovable! But that wouldn’t stop it being true nevertheless. The algorithm doesn’t care what you can prove.
“Your 1,2, and 3 confuse the question “What does it *mean* to say it would actually work for all numbers?” with the question “How could we *know* it would actually work for all numbers?”. Your 1,2, and 3 address the latter question, not the former.”
I do appreciate that, honestly!
The point of 1, 2 and 4 is that “what is true” can, by choice, be defined in terms of “what we can know” — so that unknowable things are neither true nor false (cf Logical Positivism).
If you do that, you are left with the possiblity that question 2 does not *have* a valid answer, because “true” for question 1 is meaningless if it is unknowable.
That is *If* you accept that “true” is a term in need of a definition, rather than something obvious, either instinctive or metaphysical (3 or 5).
–
“It is a statement about what will happen in any *possible* future. It has nothing to do with what the actual future might or might not hold.”
What is the difference between saying:
“for any n, f(n) is 1”
and
“for any choice of n I might make, when I calculate f, f(n) will be 1”
The one is a statement about all possible worlds. The other is a conjecture about this world.
But aren’t they the same?
Colin:
would I have to say “I am pretty sure that there is a way to factor any number quickly, based on the fact that I’ve tried this with a billion numbers and it has worked for all of them, but it still might not work for all numbers”.
That’s one possibility. Here’s another:
Start with a set of standard axioms for arithmetic (the usual choice is the so-called Peano Axioms). There are two completely different senses in which you might or might not be able to “prove” that your method always works.
The first sense is that you might (or might not) be able to write down a series of statements, each of which is either an axiom or follows from previous statements on your list, ending up with the statement that your method always works.
The second sense is that you might (or might not) be able to give an airtight argument that your method always works, invoking only principles that pretty much everyone agrees are correct. For example, you might need to invoke the principle that the Peano Axioms are consistent. On the one hand, that’s uncontroversial. On the other hand, it is not something you can prove in the first sense above.
So it’s possible that the absolute reliability of your method might be provable in the second sense, but not in the first.
John Faben:
“So I’ll state, as one of the few definite conclusions of this survey, that P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.”
This, as stated (though perhaps not as intended) is not the same as what I was trying to say.
This says “we may not be able to prove it”, which can be read as a statement about our intellectual capabilities. I wanted to say “it may not be provable”, which is a statement about whether any string of symbols — whether or not we can find it — would serve as a proof.
Steve – the whole paper is about whether or not P vs NP is formally independent of the ZF axioms, so Aaronson definitely did mean “we may not be able to prove” in the sense of “it may not be provable”.
What would Schroedinger have to say about this? Is the strich-nine fed cat in this box alive or dead? Until the proof, are not all possibilities true?
But I think that’s a good framework for this question, not a contest between true and provable but between possible and provable.
You seem very sure that there is only one answer to each of your questions. Is such a position provable? Is that proof durable?
How old is the study of mathematics? How old is the zero? Is it possible that someday we will throw the zero back into the dustbin of history?
“A great deal more is known than has been proved.” Richard Feynman, quoted in Marcus du Sautoy’s The Music of the Primes: Searching to Solve the Greatest Mystery of Mathematics (2003).