Gödel's First Incompleteness Theorem states that if we have a recursive and consistent set of axioms $A$ in $\mathcal{L}_{\text{NT}}$, then there is a true first order statement about natural numbers $\sigma$ such that $A \not \vdash \sigma$.

Thus, the set of provable statements about the natural numbers is a proper subset of the set of true statements about the natural numbers. I was wondering what can be said about the set of provable statements with regards to its size in comparison with the set of true statements. Clearly they are both infinite sets, but, in terms of measure theory, topology, or density, is there something that can be said?

  • 4
    $\begingroup$ You can’t really talk about the “percentage” of a countable set. You can talk about the density. $\endgroup$ Oct 15, 2019 at 1:08
  • 4
    $\begingroup$ The answer to this is completely dependent on how you intend to "randomly generate a true statement about the natural numbers". $\endgroup$ Oct 15, 2019 at 1:42
  • 1
    $\begingroup$ @AlexKruckman Well, there might be some unexpected robustness, which would be quite interesting (incidentally, I can't resist using this as an opportunity to mention the singular importance of the number $0.625$). $\endgroup$ Oct 15, 2019 at 1:58
  • 1
    $\begingroup$ @NoahSchweber Ha! That's a very amusing result. I agree that there could be some interesting robustness, if the question is formulated correctly (though I expect that even so it would be extremely difficulty to analyze the situation). But we're talking about probability measures on a countable set. Since infinitely many truths are provable in PA and infinitely many are not, nothing more can be said without giving some sort of restriction on the class of measures under consideration. $\endgroup$ Oct 15, 2019 at 2:03
  • 3
    $\begingroup$ @AlexKruckman Oh sure, a lot of work is needed. My point was mostly meant to un-discourage the OP: there are genuine problems with their question but I don't want them to come away from this thinking that it's a bad one per se. $\endgroup$ Oct 15, 2019 at 2:05


You must log in to answer this question.

Browse other questions tagged .