Probably true, but provably unprovable
up vote
28
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 Nov 16 at 17:08
John Baez
8,4874593
|
show 9 more comments
up vote
28
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 Nov 16 at 17:08
John Baez
8,4874593
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
|
show 9 more comments
up vote
28
down vote
favorite
up vote
28
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 Nov 16 at 17:08
John Baez
8,4874593
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 Nov 16 at 17:08
John Baez
8,4874593
asked Nov 16 at 17:08
John Baez
8,4874593
edited Nov 16 at 22:52
asked Nov 16 at 17:08
John Baez
8,4874593
asked Nov 16 at 17:08
John Baez
8,4874593
asked Nov 16 at 17:08
John Baez
8,4874593
8,4874593
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
|
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
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
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
Nov 16 at 17:19
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
3
What's the difference between "true" and "provable"?
– YCor
Nov 16 at 18:13
What's the difference between "true" and "provable"?
– YCor
Nov 16 at 18:13
1
1
Do statements like the Paris-Hamilton theorem count?
– Ilya Bogdanov
Nov 16 at 19:37
Do statements like the Paris-Hamilton theorem count?
– Ilya Bogdanov
Nov 16 at 19:37
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
Nov 16 at 20:53
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
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
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
|
show 9 more comments
1 Answer
1
active
oldest
votes
up vote
11
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 Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
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
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
11
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 Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
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
add a comment |
up vote
11
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 Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
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
add a comment |
up vote
11
down vote
up vote
11
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 Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
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 Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
edited Nov 16 at 22:15
answered Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
answered Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
answered Nov 16 at 21:43
Bjørn Kjos-Hanssen
17.6k33786
17.6k33786
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
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
Nov 16 at 22:11
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
Nov 16 at 22:16
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
Nov 16 at 22:11
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
@EmilJeřábek right, I'll update...
– Bjørn Kjos-Hanssen
Nov 16 at 22:16
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
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