35
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – James Hanson Nov 16 '18 at 17:19
  • 3
    $\begingroup$ What's the difference between "true" and "provable"? $\endgroup$ – YCor Nov 16 '18 at 18:13
  • 1
    $\begingroup$ Do statements like the Paris-Hamilton theorem count? $\endgroup$ – Ilya Bogdanov Nov 16 '18 at 19:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Nik Weaver Nov 16 '18 at 20:53
  • 3
    $\begingroup$ 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. $\endgroup$ – John Baez Nov 16 '18 at 22:11
16
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Nov 16 '18 at 22:11
  • $\begingroup$ @EmilJeřábek right, I'll update... $\endgroup$ – Bjørn Kjos-Hanssen Nov 16 '18 at 22:16
4
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ In the first paragraph, you give two formulations of p(n), but these are not equivalent. To make them equivalent, you could change "Either T is consistent" in the second version to "Either n doesn't code a proof of a contradiction in T". You seem to use both versions in the subsequent argument, so I'm not convinced. $\endgroup$ – Andreas Blass Dec 9 '19 at 1:15
  • $\begingroup$ Good catch; hopefully, I have patched up the thinko now. $\endgroup$ – Sridhar Ramesh Dec 10 '19 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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