13
$\begingroup$

Gödel's incompleteness theorem shows that there are undecidable statements, i.e., formal logical claims which neither have proofs nor disproofs.

In doing so, Gödel famously enumerated all well-formed formulas with his so-called "Gödel numbering". Thus, the following question is well posed:

What proportion of well-formed formulas in ZFC are undecidable?

I seems clear to me that this proportion should converge. Moreover, there are really only two reasonable options - 0% or 100%. My money is on 100%, since that feels in line with the sort of logical weirdness inherent in this area, though I do not have any rigorous heuristic.

Improve this question
$\endgroup$
7
  • 7
    $\begingroup$ I believe you can show that it is neither 0% nor 100% pretty easily, although technically this is going to depend on how you number formulas precisely. Given a tautology $\varphi$, any sentence of the form $\varphi \vee \psi$ will also be a tautology. In any reasonable numbering, this is going to be a positive fractional of all sentences. $\endgroup$
    – James E Hanson
    Commented Mar 8, 2023 at 23:16
  • 2
    $\begingroup$ On the other hand, if $\varphi$ is undecidable, then any sentence of the form $\varphi \wedge (\varphi \vee \psi)$ will also be undecidable. These should also be a positive fraction of all sentences. $\endgroup$
    – James E Hanson
    Commented Mar 8, 2023 at 23:18
  • 2
    $\begingroup$ Related question: mathoverflow.net/questions/4454/… $\endgroup$
    – Sam Hopkins
    Commented Mar 8, 2023 at 23:32
  • 2
    $\begingroup$ How do you define proportion on a countably infinite set? $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 9, 2023 at 9:32
  • 2
    $\begingroup$ @JoshuaZ: I know how it could be done. I'm asking how the OP means to measure it. Even more so, since % normally implies thinking in terms of measure/probability theoretic approaches, which require a different flavour when talking about a countably infinite set, since the measure cannot be countably additive. $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 9, 2023 at 13:38

1 Answer 1

Reset to default
16
$\begingroup$

This is going to depend sensitively on your exact choice of Gödel number, and the limit will often not be defined. Pick your favorite very short undecidable statement S. Then for any statement A, you have the nearly the same length statements like "A or S", "A and S", "A and True", "A or False". However, one can construct Gödel numberings where any use of an "or" is much longer than any use of an "and" or the reverse, which will change how common these statements are.

So, the answer can be, with a little work, $100\%$, $0\%$, or undefined (which will probably be the case for most natural numbering choices). It is likely that for any computable $x$ where $0 \leq x \leq 1$, there is a numbering which gives an answer of $x$ to your question.

Improve this answer
$\endgroup$
4
  • 9
    $\begingroup$ I'll point to my answer mathoverflow.net/a/7902/297 , arguing that, for "reasonable" numberings, the probability will be strictly between 0 and 1. $\endgroup$
    – David E Speyer
    Commented Mar 9, 2023 at 13:50
  • $\begingroup$ @DavidESpeyer Hmm, yes that reasoning does look more convincing. $\endgroup$
    – JoshuaZ
    Commented Mar 9, 2023 at 15:41
  • 5
    $\begingroup$ Since this is on the front page again, though, I edited my answer to point out something that I noticed the last time I thought about this: It matters a lot whether writing down the variable "$x_i$" counts as adding $O(1)$ to the length of your formula, regardless of $i$, or as adding $O(\log i)$ (as would be the case in any actual data storage format). $\endgroup$
    – David E Speyer
    Commented Mar 9, 2023 at 17:55
  • $\begingroup$ @DavidESpeyer As a layabout respectfully nitpicking, when you say 'any' actual data storage format do you include the human brain? (just curious to hear your opinion, as an expert) $\endgroup$
    – Alec Rhea
    Commented Jul 31, 2023 at 9:13

Not the answer you're looking for? Browse other questions tagged .