Let us enumerate all statements of PA or ZFC by length, upto n characters, then in the limit as $n\rightarrow\infty$, what proportion of statements are provably true, provably false, or independent?

Ok, no enumeration necessary, just count all of length less then n and take the limit.

Is it perhaps 50%,50%,0%?

What if we discard all statements which are simply the negation character in front of a shorter statement?

What is the asymptotic density of independent statements?

Is any non-trivial results of this sort known for any theory?

  • 1
    $\begingroup$ Since all three sets are countably infinite. So it amounts to how you are going to enumerate them. $\endgroup$ – Asaf Karagila Jan 2 '14 at 20:14
  • 9
    $\begingroup$ Negating a sentence changes its truth value so it seems that true and false percentages should be equal. $\endgroup$ – hot_queen Jan 2 '14 at 20:28
  • 1
    $\begingroup$ @MJD: Yes, your suggestion fails for $\forall x_1(x_1=x_1),\forall x_2(x_2=x_2)$ and so on; but that too can be easily corrected. This is just an example of ambiguity within this post. In the comments the OP also pointed out that $3$ is in the language, to my knowledge, $3$ is just a shorthand for $SSS0$, but the comment seemed to indicate something else. Therefore, I still wait for the OP to clarify and remove ambiguities like that. Ideally an enumeration which is not handwaved around like this one, will also be given. $\endgroup$ – Asaf Karagila Jan 2 '14 at 21:43
  • 2
    $\begingroup$ But the variables are not indexed by the language, but rather the meta-language. So writing $x_{SSS0}$ makes no sense. I still feel that you need to write down exactly what the language you are using it. Then perhaps we can formulate things slightly better (e.g. consider $\varphi\equiv\psi$ if and only if $\sf PA$ proves $\varphi\leftrightarrow\psi$; there are countably many equivalence classes, from each one choose the one which is both the shortest, and the variables appearing (quantified or not) appear in order (first $x_1$ then $x_2$ and so on) and without jumps), and then we can proceed. $\endgroup$ – Asaf Karagila Jan 3 '14 at 15:41
  • 1
    $\begingroup$ No need for being rude; insulting and dismissing researchers in the field is not the way to get help on your problem. Your question is ill-posed as it stands currently, pointing it out should actually be considered help. $\endgroup$ – Andrés E. Caicedo Jan 3 '14 at 21:04

Under certain reasonable assumptions, the independent statements are of full density. See https://www.cs.auckland.ac.nz/~cristian/aam.pdf

  • $\begingroup$ This doesn't answer the question; the proportion of true statements that are independent goes to $1$ according to the paper, but that's not the same as the proportion of all statements that are independent! $\endgroup$ – user21820 Jan 21 '17 at 16:33
  • $\begingroup$ @user21820: Each false statement corresponds to a true one, by prefixing a ¬, or by deleting an already prefixed ¬. So the false statements are, asymptotically with respect to statement length, of the same density as the true ones. A statement is independent if neither it nor its negation is provable. So, if the proportion of true statements that are independent is asymptotically $1$, then the proportion of false statements that are independent is asymptotically $1$ too. Hence the proportion of all statements, true or false, is asymptotically $1$. $\endgroup$ – John Bentin Jan 21 '17 at 20:48
  • $\begingroup$ Hmm it's not clear to me it's rigorously correct since you're basically using the assumption that on average a random true statement of length $n$ is equally likely to be a negation than not. That is maybe why it's stated as an open problem at the end of the very paper you linked to. But I intuitively buy the argument, though you should make clear what is proven by the paper. $\endgroup$ – user21820 Jan 22 '17 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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