I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n \in \mathbb{N}$) such that:

  1. Heuristic arguments using probability theory suggest that all the statements $P(n)$ are true.

  2. One can prove, preferably by making the probabilistic arguments rigorous, that infinitely many of the statements $P(n)$ are true.

  3. One can prove that only finitely many of the statements $P(n)$ are provable (say in Peano arithmetic or ZFC).

The goal here would be to find statements that are true 'just because they are probably true', not because we can put our finger on a reason why any individual one must be true.

An example of such a sequence of statements might be 'if $p_n$ is the $n$th prime, there are infinitely many repunit primes in base $p_n$'. However while this example meets condition 1 we seem far from having enough understanding of mathematics to prove 2, and 3 seems hopeless. I think we need a less charismatic sequence of statements that are more carefully crafted to the task at hand.

  • 5
    It's not a fixed sequence but you can generate arbitrarily many probably true, ZFC independent statements by stating lower bounds on the Kolmogorov complexity of randomly generated binary strings. You can tune the probability that they're true by choosing the length of the string and the lower bound carefully. – James Hanson Nov 16 at 17:19
  • 3
    What's the difference between "true" and "provable"? – YCor Nov 16 at 18:13
  • 1
    Do statements like the Paris-Hamilton theorem count? – Ilya Bogdanov Nov 16 at 19:37
  • 1
    How could you "prove that only finitely many of the statements $P(n)$ are provable" (condition 3) and also "prove that infinitely many of the statements $P(n)$ are true" (condition 2)? Is the latter proof supposed to depend on large cardinals or something? – Nik Weaver Nov 16 at 20:53
  • 3
    The Parris-Harrington theorem gives an infinite sequence of statements $P(n)$ that are individually provable in Peano arithmetic, for which $\forall n P(n)$ is not provable in PA. It also has nothing to do with probabilistic heuristics. So this fails to meet all three criteria I listed. – John Baez Nov 16 at 22:11

Let $c$ be a constant such that $$\mathrm{PA}\not\vdash K(x)\ge c$$ for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked Q&A discusses how to find it in $\mathrm{PA}+\mathrm{Con}(\mathrm{PA})$.

For any $d$, let $x_d$ be the indicator string for the primes among nonnegative integers $\le d$. So for instance, $x_5=001101$ and $x_{9}=0011010100$.

Let $P_{d}(n)$ be the statement $$K(x_{n+d})\ge c.$$

Let $d$ be large and then let $P(n)=P_d(n)$ for all $n$.

  • If $d$ is large enough then heuristically all the $P(n)$ are true.*

  • By the Pigeonhole Principle in $\mathrm{PA}+\mathrm{Con}(\mathrm{PA})$ we prove that all but finitely many $P(n)$ are true.

  • We cannot prove any particular $P(n)$ in $\mathrm{PA}$.

(*) Heuristics may suggest something like $d\ge c\cdot \mathcal H(1/\log c)$ where $\mathcal H$ is the entropy function, and we heuristically assume the primes are "random modulo the Prime Number Theorem", but the primes are computable so that heuristic is not quite right (thanks @EmilJerabek).

  • 2
    But primes are not random at all, they are computable. Thus the Kolmogorov complexity of $x_d$ is a constant plus the Kolmogorov complexity of $d$. If you defined $x_d$ as a string of $d$ zeros, it would behave in an essentially identical way. – Emil Jeřábek Nov 16 at 22:11
  • @EmilJeřábek right, I'll update... – Bjørn Kjos-Hanssen Nov 16 at 22:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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