Probably true, but provably unprovable
up vote
22
down vote
favorite
I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n in mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are true.
One can prove, preferably by making the probabilistic arguments rigorous, that infinitely many of the statements $P(n)$ are true.
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.
nt.number-theory lo.logic
asked yesterday
John Baez
8,4524392
|
show 9 more comments
up vote
22
down vote
favorite
I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n in mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are true.
One can prove, preferably by making the probabilistic arguments rigorous, that infinitely many of the statements $P(n)$ are true.
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.
nt.number-theory lo.logic
asked yesterday
John Baez
8,4524392
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
yesterday
2
What's the difference between "true" and "provable"?
– YCor
yesterday
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
yesterday
1
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
1
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
yesterday
|
show 9 more comments
up vote
22
down vote
favorite
up vote
22
down vote
favorite
I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n in mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are true.
One can prove, preferably by making the probabilistic arguments rigorous, that infinitely many of the statements $P(n)$ are true.
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.
nt.number-theory lo.logic
asked yesterday
John Baez
8,4524392
I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n in mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are true.
One can prove, preferably by making the probabilistic arguments rigorous, that infinitely many of the statements $P(n)$ are true.
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.
nt.number-theory lo.logic
nt.number-theory lo.logic
asked yesterday
John Baez
8,4524392
asked yesterday
John Baez
8,4524392
edited yesterday
asked yesterday
John Baez
8,4524392
asked yesterday
John Baez
8,4524392
asked yesterday
John Baez
8,4524392
8,4524392
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
yesterday
2
What's the difference between "true" and "provable"?
– YCor
yesterday
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
yesterday
1
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
1
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
yesterday
|
show 9 more comments
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
yesterday
2
What's the difference between "true" and "provable"?
– YCor
yesterday
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
yesterday
1
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
1
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
yesterday
5
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
yesterday
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
yesterday
2
2
What's the difference between "true" and "provable"?
– YCor
yesterday
What's the difference between "true" and "provable"?
– YCor
yesterday
1
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
yesterday
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
yesterday
1
1
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
1
1
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
yesterday
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
yesterday
|
show 9 more comments
1 Answer
1
active
oldest
votes
up vote
9
down vote
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).
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
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).
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
add a comment |
up vote
9
down vote
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).
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
add a comment |
up vote
9
down vote
up vote
9
down vote
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).
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
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).
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
edited yesterday
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
answered yesterday
Bjørn Kjos-Hanssen
17.4k33683
17.4k33683
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
add a comment |
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
2
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
yesterday
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
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
yesterday
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f315473%2fprobably-true-but-provably-unprovable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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
yesterday
2
What's the difference between "true" and "provable"?
– YCor
yesterday
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
yesterday
1
@IlyaBogdanov Was Paris–Hamilton a typo for Paris–Harrington?
– bof
yesterday
1
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
yesterday