Reminiscent of Freeman Dyson’s 2005 answer to the question: “what do you believe is true even though you cannot prove it?”:
Since I am a mathematician, I give a precise answer to this question. Thanks to Kurt Gödel, we know that there are true mathematical statements that cannot be proved. But I want a little more than this. I want a statement that is true, unprovable, and simple enough to be understood by people who are not mathematicians. Here it is.
Numbers that are exact powers of two are 2, 4, 8, 16, 32, 64, 128 and so on. Numbers that are exact powers of five are 5, 25, 125, 625 and so on. Given any number such as 131072 (which happens to be a power of two), the reverse of it is 270131, with the same digits taken in the opposite order. Now my statement is: it never happens that the reverse of a power of two is a power of five.
The digits in a big power of two seem to occur in a random way without any regular pattern. If it ever happened that the reverse of a power of two was a power of five, this would be an unlikely accident, and the chance of it happening grows rapidly smaller as the numbers grow bigger. If we assume that the digits occur at random, then the chance of the accident happening for any power of two greater than a billion is less than one in a billion. It is easy to check that it does not happen for powers of two smaller than a billion. So the chance that it ever happens at all is less than one in a billion. That is why I believe the statement is true.
But the assumption that digits in a big power of two occur at random also implies that the statement is unprovable. Any proof of the statement would have to be based on some non-random property of the digits. The assumption of randomness means that the statement is true just because the odds are in its favor. It cannot be proved because there is no deep mathematical reason why it has to be true. (Note for experts: this argument does not work if we use powers of three instead of powers of five. In that case the statement is easy to prove because the reverse of a number divisible by three is also divisible by three. Divisibility by three happens to be a non-random property of the digits).
It is easy to find other examples of statements that are likely to be true but unprovable. The essential trick is to find an infinite sequence of events, each of which might happen by accident, but with a small total probability for even one of them happening. Then the statement that none of the events ever happens is probably true but cannot be proved.
How does the randomness of the digits imply that the statement cannot be proven? Superficially the quote seems to use two different notions of randomness, namely “we cannot detect any patterns” (i.e. a pure random generator is the best predictor we have) and “we have shown that there can be no patterns” (i.e. we have shown no other predictor can do any better). Is this a known result from Ergodic Theory?
I was about to type out a rebuttal of this, but halfway through I realized I actually agree with you. The “some non-random property” of the digits of the powers of two is that they are all digits found in order inside of powers of two. I would even go so far as to say that if the statement really can’t be proven (even taking into account the fact that the digits aren’t truly random) then there’s a sense in which it isn’t true. (And if it can’t be proven false, then I’d also say it isn’t false.)
If it can’t be proven false, then it definitely isn’t false!
Equivalently: If it’s false, then it can be proven false.
Why do I say that? Well, if it’s false, then there exists a power of two that is the reverse of a power of five. But that has a very short proof: just write down the smallest example.
As to the case where it can’t be proven either way: I would say that it has to be true in that case, but this might be one of those things that sufficiently diehard constructivists would agree with you on.
“If it can’t be proven false, then it definitely isn’t false” Hmm, if you are applying that to mathematical conjectuire, then those statements dont seem compatible with Godel’s theorem to me.
You need to add some assumptions to make it work. For example, I believe the following works:
“In second order arithmetic, we can prove that NP1 implies NF, where NP1 is the statement ‘there exists no first order proof of the conjecture’ and NF is the statement ‘the conjecture isn’t false’.”
I meant this specific conjecture, not all conjectures. More generally it applies to all conjectures of the form “there is no number n such that Q(n)” where Q is straightforward to check for a particular n.
Reminiscent of Freeman Dyson’s 2005 answer to the question: “what do you believe is true even though you cannot prove it?”:
How does the randomness of the digits imply that the statement cannot be proven? Superficially the quote seems to use two different notions of randomness, namely “we cannot detect any patterns” (i.e. a pure random generator is the best predictor we have) and “we have shown that there can be no patterns” (i.e. we have shown no other predictor can do any better). Is this a known result from Ergodic Theory?
I was about to type out a rebuttal of this, but halfway through I realized I actually agree with you. The “some non-random property” of the digits of the powers of two is that they are all digits found in order inside of powers of two. I would even go so far as to say that if the statement really can’t be proven (even taking into account the fact that the digits aren’t truly random) then there’s a sense in which it isn’t true. (And if it can’t be proven false, then I’d also say it isn’t false.)
If it can’t be proven false, then it definitely isn’t false!
Equivalently: If it’s false, then it can be proven false.
Why do I say that? Well, if it’s false, then there exists a power of two that is the reverse of a power of five. But that has a very short proof: just write down the smallest example.
As to the case where it can’t be proven either way: I would say that it has to be true in that case, but this might be one of those things that sufficiently diehard constructivists would agree with you on.
“If it can’t be proven false, then it definitely isn’t false”
Hmm, if you are applying that to mathematical conjectuire, then those statements dont seem compatible with Godel’s theorem to me.
You need to add some assumptions to make it work. For example, I believe the following works:
“In second order arithmetic, we can prove that NP1 implies NF, where NP1 is the statement ‘there exists no first order proof of the conjecture’ and NF is the statement ‘the conjecture isn’t false’.”
I meant this specific conjecture, not all conjectures. More generally it applies to all conjectures of the form “there is no number n such that Q(n)” where Q is straightforward to check for a particular n.