Probably true, but provably unprovable

Question

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 in some widely accepted axiom system $X$, preferably by making the heuristic arguments rigorous, that "$P(n)$ holds for infinitely $n$".

3. One can prove in some widely accepted axiom system $Y$ that "$X$ cannot prove $\forall n P(n)$".

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.

Answer 1

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).

Answer 2

I will take the question as reworded in the comments: 1) asks for a plausible probabilistic argument for $\forall nP(n)$ using any framework you like, 2) asks for a proof in some widely accepted axiom system $X$ of "$P(n)$ for infinitely many $n$", and 3) asks for a proof in some widely accepted axiom system that $X$ cannot prove $\forall nP(n)$.

Let us call a function $f$ from the positive integers to the positive integers Collatz-like if it is piecewise linear, the pieces being finite in number and depending only on the congruence class of the argument modulo some $m$. The ur-Collatz function is given by $C(n)=n/2$ if $n\equiv0\bmod2$, $C(n)=(3n+1)/2$ if $n\equiv1\bmod2$. Another example is given by $D(n)=n/2$ if $n\equiv0\bmod2$, $D(n)=(5n+1)/2$ if $n\equiv1\bmod2$.

We make ourselves interested in the question, given a Collatz-like function $f$, is there a positive integer $s$ such that the sequence $s,f(s),f(f(s)),f(f(f(s))),\dots$ goes to infinity.

Heuristically, $C(n)$ is, on average, much like $3n/4$, hence, decreasing, while $D(n)$ is much like $5n/2$, hence, increasing. Henceforward, we restrict our attention to those functions that are (heuristically, on average) decreasing. We enumerate them, and let $P(n)$ be the statement that there is no input to the $n$th such function such that the iterates of the function go to infinity. I find $\forall nP(n)$ plausible, on heuristic grounds.

Now, infinitely many of our functions $f$ satisfy the condition $\forall mf(m)\le m$. The heuristic argument becomes a trivial proof that for all these infinitely many functions, $P(n)$.

Finally, John Conway, Unpredictable Iterations, in Proc. 1972 Number Theory Conference, University of Colorado, Boulder, CO. 1972 , pp 49-52 (MR 52 #13717), proved that in the set of Collatz-like functions there are those for which $P(n)$ is algorithmically undecidable. So, we can't prove $\forall nP(n)$.

Answer 3

Let T be the theory of interest (PA, or ZFC, or whatever). Let P(n) be the statement "Either T is consistent, or there is a proof of a contradiction in T whose code is smaller than n".

Clearly (provably!), all but finitely many of the P(n) are true [for if any of the P(n) is false, then T is inconsistent, and thus there is some code of a contradiction in T, and P(n) will be true for all n larger than this code]. This gives us requirement 2.

Also, if T is consistent, it cannot prove ANY of the P(n) [for if T was consistent, then the finitely many values smaller than n would all provably not actually encode a proof of a contradiction; thus, P(n) would provably entail the consistency of T, and therefore T cannot consistently prove p(n) by Goedel's second incompleteness theorem]. This gives us requirement 3 as well as we can hope for; in any context where we can prove the consistency of T, we can prove that T doesn't prove any of the P(n), much less $\forall n P(n)$. We can't hope for T itself to prove that T does not prove everything, because of Goedel's second incompleteness theorem.

Finally, for ALL of the P(n) to be true (including P(0)) is equivalent to the consistency of T. So again we are assured of this in any context where we are assured of the consistency of T. But at any rate, one might feel this to be probabilistically established by the empirical evidence of many decades of mathematicians having failed to find a contradiction in T yet. This gives us requirement 1, sort of. :)