MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
13

11

Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or not? By the word 'natural' I am trying to exclude measures defined in terms of the characteristic function of the set of true sentences.

flag
Does this question make sense? Won't PA contain statements which are true in some models but false in others? So, given one of these statements, you need to decide whether it's true in "the usual model of PA". But if you ask any model if it's "the usual model" won't it say "of course I am!". – Kevin Buzzard Nov 7 2009 at 9:16
'won't it say "of course I am!"' I guess it will :) In fact I don't really care much about the 'usual model' and would be more than happy to replace 'usual model' by 'any given model'. – auniket 0 secs ago – auniket Nov 8 2009 at 3:52
3 
 We can ignore any issues about models here. Consider any probability distribution on {statements of PA without unbound variables}, so that the probabilities of X and NOT(X) are equal. Let p be the proportion of statements that are undecidable. Then, for any given model, 1/2 of all statements will be true, and p/2 will be true but undecidable. So we can just ask what p is, and avoid all issues about choice of model. – David Speyer Nov 8 2009 at 16:34

4 Answers

1

There are an infinite number of true provable theorems in PA and an infinite number of true unprovable theorems. So any measure must go to zero for all but a finite number of sentences I think there will be a problem with knowing p in that one can search all the lower weighted sentences and find the percentage of true sentences so that a point may be reached where some sentences may have to be undecidable to make the probability work. If this is the case then then knowledge of the probability would make some sentences decidable so the probability can't be known and the proof would have to be non-constructive that it exists which could cause problems with some philosophies of mathematics like intuitionism. I recall a similar question about quantum computers in which the answer was 1/2.

I have found a reference that says that no halting probability is computable. If proof could be made into a process that either succeeds or never halts then that would provide evidence that the probability of an undecidable theorem is uncomputable

http://en.wikipedia.org/wiki/Chaitin%27s_constant#Interpretation_as_a_probability

link|flag
This is indeed very interesting. I am planning to read more on Chaitin's constant, when time permits, and get back later. Thanks a lot! – auniket Nov 9 2009 at 21:37
3

Update: in response to comment below, I'm not sure anymore the probability in question was 0.

Let's try the measure that gives an equal weight for any true statement of fixed length $N$ (written in mathematical English).

Then we have statements of the form "S or 1+2=3" which form more then $1/10^{20}$th of all true statements of a given length. On the other hand, the statements "S and Z" (where Z is an undecidable problem) form some positive (bounded below) measure subset in the statements of given length as well.

So, yes, for the measure described above the measure of provable statements is within some positive bounds $[a, b]$ for any $N$ greater than some $N_0$.

But that measure is proportional, for a fixed $N$, to the characteristic function of the set of all true statements, so, no, my answer doesn't give a "natural" measure.

I think the probability of "a random true statement is provable" is 0 in any good formalization of your problem.

Here's the reasoning: consider a true undecidable statement S. Now I would say that in any reasonable definition of probability the long statement will contain S with probabilitiy that goes to 1 as its length increases. One can't prove it until there's no definition of this probability, but the related fact for strings is straightforward:

Consider any string S. Then the probability $P(n) := \{$the random string of length $n$ contains S$\}$ goes to 1 as $n\to \infty$.

The proof can be done by considering the random strings of the form (chunk 1)(chunk 2)...(chunk N) where all chunks are of the same length as S.

link|flag
1 
 I disagree. 'Containment' has nothing to do with provability. For sake of argument, imagine, for example, that Fermat's Last Theorem was unprovable. That does not mean that the statement "FLT holds for (x,y,z) if x+y=z" is unprovable. By considering statement of the form "A and S" one can show that the density of provable statements is less than 1 though. – Boris Bukh Nov 8 2009 at 19:22
"Containment" is a well-defined operation for strings, but to formalize it for statements takes some work. However, I think the following will be a straightforward property of at least some (I'd say all manageable) definitions of what the probability on the set of statements is: (continued) – Ilya Nikokoshev Nov 8 2009 at 19:31
"(For any statement, e.g. FLT) There exists N such that it can be proven that from more than 1/2 of true statements of length N the FLT follows." – Ilya Nikokoshev Nov 8 2009 at 19:31
My last statement is suspicious; it's probably wrong. I've rewritten the answer. @Boris: good point. – Ilya Nikokoshev Nov 8 2009 at 19:47
I did not think it through when I said 'natural' to exclude anything in terms of the characteristic function of the set of provable sentences. Limit of the proportion of provable sentences of length n, as n goes to infinity, is certainly in a sense the most natural probability. I was hoping to get a statement like "most real numbers are irrational", or better yet, to know if the condition of non-provability is something like "Zariski open" (ie if you can find one, then you can find lots). Now that I think back, your answer certainly expresses something like this. Thanks! – auniket Nov 9 2009 at 21:44
show 1 more comment
2

Ilya had the right idea in his answer.

Firstly, the natural measure that is usually used when you have a discrete set of objects, each of some finite "complexity" n, and with only finitely many of complexity n, is to consider the probability for fixed n, and then let n go to infinity (cf. the theory of Random Graphs).

Secondly, the probability of a true statement of length n being provable indeed tends to 0 as n goes to infinity. This has been shown by Cristian Calude and Helmut Jürgensen (Adv Appl Math 35 (2005), 1-15).

Thank goodness our job is not to prove random statements!

Caveat: this holds for sound and consistent theories in which Peano arithmetic can be formalized.

link|flag
David's answer mathoverflow.net/questions/4454/… convinced me that this answer is wrong. – Konrad Swanepoel Dec 9 2009 at 19:19
7

It seems to me that the probability that a statement is provable and that it is undecidable should both be bounded away from 0, for any reasonable probability distribution.

Let $C_n$ be the number of grammatical statements of length $n$. For any statement $S$, the statement

$S$, or $1=1$

is a theorem. So the number of provable statements of length $n$ is bounded below by $C_{n-k}$, where $k$ is the number of characters needed to tag on "or $1=1$".

On the other hand, let $G$ be an undecidable sentence, and $S$ any sentence. Then

Either $S$ and $1 \neq 1$, or else $G$

is undecidable. So the number of undecidable sentences of length $n$ is bounded below by $C_{n-\ell}$, for some constant $\ell$. For any reasonable grammar, the ratios $C_{n-k}/C_n$ and $C_{n- \ell}/C_n$ should both be bounded away from 0.

I am currently trying to figure out why my computation is seemingly incompatible with the paper of Calude and Jurgensen cited by Konrad. I suspect that the answer is hidden in the definition of prefix free, on page 4, but I am trouble understanding it. Any help?

link|flag
1 
 Your computation seems fine. What worries me now after a closer look at the paper of Calude and Jürgensen is that when calculating the probability in their Proposition 5.1 they divide by $Q^n$, the total number of strings over an alphabet of size $Q$. But only a small fraction of these strings will be grammatical. This seems to be glossed over in their Theorem 5.2. What now? (The prefix free thing is a technicality in the definition of algorithmic complexity and should not influence the meaning of the statement of Theorem 5.2). – Konrad Swanepoel Dec 5 2009 at 22:18
1 
 I don't understand this paper at all. Their proof of Theorem 4.6 is essentially "because of syntactical constraints". Moreover I can replace T by the set of well-formed formulas without affecting any of their arguments--except possibly that one: who knows? In particular I can't imagine how they are using the assumption that the theory is consistent. – Reid Barton Dec 5 2009 at 22:58
1 
 I have e-mailed Calude. I'll report back if I get a reply. – David Speyer Dec 7 2009 at 14:18
1 
 Calude writes "You are right, there is a problem and together with Jim Cox we looked at ways to fix it; we are close to recovering the result." He said a bit about how he hopes to salvage the result, but I don't feel confident that I can summarize it effectively here. – David Speyer Dec 8 2009 at 3:36
2 
 Like I said, I don't feel like I understand what they are doing. I invited Calude to post here, and I hope he will. If I wanted to prove a result like this, I think I might try to invent a notion of trivial equivalence, so that I could say that "X and 0=1, or else Y" was trivially equivalent to "Y". I might then try to prove that almost all trivial equivalence classes of statements were undecidable. But I don't know if it is what they are doing. In any case, the authors definitely agree that the mistake is in their paper, not our reading of it. – David Speyer Dec 9 2009 at 19:36
show 3 more comments

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.