Cfrgtkky

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.

Let $c$ be a constant such that
$$mathrm{PA}notvdash 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 $dge ccdot 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).