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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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!". $\endgroup$– Kevin BuzzardCommented Nov 7, 2009 at 9:16
-
$\begingroup$ '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 $\endgroup$– pinakiCommented Nov 8, 2009 at 3:52
-
8$\begingroup$ 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. $\endgroup$– David E SpeyerCommented Nov 8, 2009 at 16:34
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
12
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.
My computation is seemingly incompatible with the paper of Calude and Jurgensen cited by Konrad. I sent some time trying to figure out why and my view is that I am right and Calude and Jurgensen are wrong but, of course, I could be doing something dumb.
This answer is getting discussed again, so let me mention a way that one might be able to salvage this, though. There is extensive literature on the behavior of random boolean statements, of which the most common model is "random $3$-SAT". The way that this works is that you have $n$ boolean variables $x_1$, $x_2$, ..., $x_n$. A "three-term clause" is a statement of the form $p_1 \vee p_2 \vee p_3$ where each $p$ is either $x_i$ or $\neg(x_i)$ for some $i$. One samples $k$ of the three-term clauses independently at random and asks whether they can all be satisfied at once. Generally, one takes $k = cn$ for fixed $c$ and asks about behavior as $n \to \infty$.
When I first heard this problem, my intuition was that the probability would be bounded away from $1$, for the same sort of reason as this answer: Some positive density of $3$-SAT instances would be of the form $P \wedge Q$, where $P$ was some explicit finite list of incompatible $3$-term clauses. (For example, $P$ could be the AND of the eight $3$-term clauses involving $(x_1, x_2, x_3)$.) But this is wrong! Because all of the $n$ variables are equally likely, for any finite number of $3$-term clauses, the probability that they will have any variables in common goes to $0$.
The flaw in this answer's argument, when it comes to random $3$-SAT, is the following: Because the size of our alphabet is allowed grow with the length of the statement, the number of $3$-SAT instances with $cn$ clauses and $n$ variables grows like $n^{3cn}$, not like an exponential! It is actually really important whether writing down "$x_i$" counts as $O(1)$ characters, or as $O(\log i)$ characters!
So this makes me wonder whether some similar phenomenon might occur for decidability in first order logic. I dug around a little, but I couldn't find any research.
answered Dec 5, 2009 at 21:42
-
3$\begingroup$ 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). $\endgroup$ Commented Dec 5, 2009 at 22:18
-
2$\begingroup$ I have e-mailed Calude. I'll report back if I get a reply. $\endgroup$ Commented Dec 7, 2009 at 14:18
-
13$\begingroup$ 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. $\endgroup$ Commented Dec 8, 2009 at 3:36
-
11$\begingroup$ 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. $\endgroup$ Commented Dec 9, 2009 at 19:36
-
8$\begingroup$ No, I have heard nothing more on this. $\endgroup$ Commented Apr 19, 2011 at 18:43
$\begingroup$
$\endgroup$
6
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.
answered Nov 8, 2009 at 19:05
-
1$\begingroup$ 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. $\endgroup$ Commented Nov 8, 2009 at 19:22
-
$\begingroup$ "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) $\endgroup$ Commented Nov 8, 2009 at 19:31
-
$\begingroup$ "(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." $\endgroup$ Commented Nov 8, 2009 at 19:31
-
$\begingroup$ My last statement is suspicious; it's probably wrong. I've rewritten the answer. @Boris: good point. $\endgroup$ Commented Nov 8, 2009 at 19:47
-
$\begingroup$ 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! $\endgroup$– pinakiCommented Nov 9, 2009 at 21:44
$\begingroup$
$\endgroup$
1
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.
answered Dec 5, 2009 at 9:21
-
7$\begingroup$ David's answer mathoverflow.net/questions/4454/… convinced me that this answer is wrong. $\endgroup$ Commented Dec 9, 2009 at 19:19
$\begingroup$
$\endgroup$
3
I was reading Michael Freedman's paper "topological views on complexity", where the following relevant conjecture is proposed:
-
$\begingroup$ Pure alphabetical order will not usually have order type $\mathbb{Z}^+$. For example, see my essay infinitelymore.xyz/p/the-book-of-numbers for an analysis and discussion of the numbers in alphabetical order, which have order type $\mathbb{N}\cdot(1+\mathbb{Q})+1$. $\endgroup$ Commented Jul 27, 2023 at 12:17
-
3$\begingroup$ But also, that conjecture seems to be refuted by David's answer above, which shows that a certain nonzero constant proportion of the sentences are provable, so it can't be less than the square root in the limit. $\endgroup$ Commented Jul 27, 2023 at 13:53
-
$\begingroup$ @JoelDavidHamkins I agree, I don't think that Freedman's conjecture is correct - despite how pleasing his topological heuristics he presents are. $\endgroup$ Commented Jul 28, 2023 at 8:38
$\begingroup$
$\endgroup$
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
answered Nov 8, 2009 at 18:51
-
$\begingroup$ 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! $\endgroup$– pinakiCommented Nov 9, 2009 at 21:37