Sorry for the naive question. Is it theoretically possible that
a statement such as "there are infinitely many primes of the form n^2+1"
could be true, but not provable, in ZFC?

I'm well aware that there are going to be statements in mathematics which
are true but not provable, but on the other hand I also am half-aware that
it's too naive to expect that an *arbitrary* statement in mathematics, whose
truth value is unknown, might be true but not provable. As a concrete
example, I have a vague memory that, before Fermat's Last Theorem
was resolved, someone told me that the statement
"Fermat's Last Theorem is wrong" could not possibly be true but not
provable in ZFC. My knowledge of proof theory is sufficiently vague
for me not to be able to back this up rigorously, but the force
of the idea was that if FLT really were false then there would
exist a counterexample, and "writing down the counterexample" would be
a proof that FLT was false. But I am sufficiently confused about
these sorts of ideas to understand how far they can take you, and,
in particular, whether they go as far as to apply to the above question
about primes (I suspect they don't...).

Kevin Buzzard

On Jul 4, 5:00*pm, Kevin Buzzard
wrote:
Sorry for the naive question. Is it theoretically possible that
a statement such as "there are infinitely many primes of the form n^2+1"
could be true, but not provable, in ZFC?

I'm well aware that there are going to be statements in mathematics which
are true but not provable, but on the other hand I also am half-aware that
it's too naive to expect that an *arbitrary* statement in mathematics, whose
truth value is unknown, might be true but not provable. As a concrete
example, I have a vague memory that, before Fermat's Last Theorem
was resolved, someone told me that the statement
"Fermat's Last Theorem is wrong" could not possibly be true but not
provable in ZFC. My knowledge of proof theory is sufficiently vague
for me not to be able to back this up rigorously, but the force
of the idea was that if FLT really were false then there would
exist a counterexample, and "writing down the counterexample" would be
a proof that FLT was false. But I am sufficiently confused about
these sorts of ideas to understand how far they can take you, and,
in particular, whether they go as far as to apply to the above question
about primes (I suspect they don't...).

Kevin Buzzard

The issue here is the logical form of the statement. The Fermat
Conjecture (proven by Wiles) was of the "Pi_1" form "For all a in A,
B(a)" where A is an enumerable set of statements and B is a computable
predicate. Here the a are quadruples of the form (x,y,z,n) where x, y,
and z are positive integers and n is an integer =3, and B is the
condition "x^n + y^n is not equal to z^n". Clearly it is possible to
enumerate all the possible members a of A and calculate whether B is
true for each. A counterexample would be *any* member of A for which B
was false.

For a statement to be independent, it must be "Pi_2", the next level
of logical complexity up: "For all a in A, there exists b in B,
C(a,b)" where A and B are enumerable anc C is a computable predicate
of A and B.

The twin prime conjecture is of this form: "for all integers a, there
exists an integer b such that (ba and b is prime and b+2 is prime)".
It could conceivably be independent of ZFC. Similarly for "there are
infinitely many primes of the form n^2+1."

However, both these statements are poor candidates for independence
because there is strong numerical and heuristic evidence that the
distribution (of twin primes, or of primes of the form n^2+1) follows
a particular functional form -- so we know a lot about the answer even
though we can't prove it, and there are plausible Pi_1 strengthenings
of those Pi^2 statements (e.g. "for all n, there are at least n primes
of the form k^2+1 less than f(n)" where f is a computable function).

The P-NP question is also Pi_2 and is more plausibly independent
(though it would still be very surprising for it to be shown
independent). If the P-NP question were independent, though, the
"P=NP" side would be implausible because there would have to be a
polynomial-time algorithm which really did solve an NP-complete
problem but we couldn't prove that it solved it.

Harvey Friedman has found some Pi_1 arithmetical statements which are
independent of ZFC (assuming large cardinals). They are mathematical
rather than logical in form, but equivalent to consistency statements
about certain large cardinals.

It's hard to think of a statement involving computable predicates on
enumerable sets that might be independent that doesn't have a
"preferred direction". You can find one if you are willing to talk
about uncountable sets and sacrifice enumerability and computability.

-- Joe Shipman

On 4 Jul., 23:00, Kevin Buzzard
wrote:
Sorry for the naive question. Is it theoretically possible that
a statement such as "there are infinitely many primes of the form n^2+1"
could be true, but not provable, in ZFC?

I'm well aware that there are going to be statements in mathematics which
are true but not provable, but on the other hand I also am half-aware that
it's too naive to expect that an *arbitrary* statement in mathematics, whose
truth value is unknown, might be true but not provable. As a concrete
example, I have a vague memory that, before Fermat's Last Theorem
was resolved, someone told me that the statement
"Fermat's Last Theorem is wrong" could not possibly be true but not
provable in ZFC. My knowledge of proof theory is sufficiently vague
for me not to be able to back this up rigorously, but the force
of the idea was that if FLT really were false then there would
exist a counterexample, and "writing down the counterexample" would be
a proof that FLT was false. But I am sufficiently confused about
these sorts of ideas to understand how far they can take you, and,
in particular, whether they go as far as to apply to the above question
about primes (I suspect they don't...).

A proof is something that is performed and must exist within physical
reality. So it may not desecrate pure mathematics if physical
constraints are considered in this case.

Any proof is certainly impossible, if it requires more steps than the
maximum number of bits available. With no doubt, the maximum number of
bits available in the universe is bounded by a finite number F and
will forever remains so. So it is easy to give ample examples for
impossible proofs. Consider for instance an irrational number like pi
or e or ln2 with no discernible pattern of digits. It is impossible to
prove whether the sum of its first 10^F digits is less or larger than
5*10^F. This fact is independent of any results concerning the rapid
computation of polylogarithmic constants like those of Bailey, Borwein
and Plouffe (Math. Comput. 66, 1997). Of course a similar argument
holds for the sum of the first 10^F prime numbers: We will never know
or prove what their sum is.

Regards, WM

On 5 Jul, 14:30, WM wrote:

A proof is something that is performed and must exist within physical
reality.

Not in proof theory (a branch of mathematical logic)
where proofs of arbitrary finite length are considered.

With no doubt, the maximum number of
bits available in the universe is bounded by a finite number F and
will forever remains so.

Are you going to tell us what F is? Has it a *mathematical*
definition?

Consider for instance an irrational number like pi
or e or ln2 with no discernible pattern of digits.

Now what does "no discernible pattern" mean?

It is impossible to
prove whether the sum of its first 10^F digits is less or larger than
5*10^F.

Can you prove this impossibility? Can you prove that, for instance,
there
is no constructive proof of the non-normality of pi in base 10?

Of course a similar argument
holds for the sum of the first 10^F prime numbers: We will never know
or prove what their sum is.

We certainly won't know what their sum is until we know what F is.

Victor Meldrew
"I don't believe it!"

Joe Shipman has posted a thorough reply already, but perhaps the following
less formal comments will also be helpful.

In article ,
Kevin Buzzard wrote:
Sorry for the naive question. Is it theoretically possible that
a statement such as "there are infinitely many primes of the form n^2+1"
could be true, but not provable, in ZFC?

Yes.

the idea was that if FLT really were false then there would
exist a counterexample, and "writing down the counterexample" would be
a proof that FLT was false.

Yes. You will not go far astray with the following rule of thumb: Any
"finite computation," if correct, is provable in ZFC, and in fact in far
weaker systems. Other than that, just from the *form* of a statement, we
can't tell a priori whether it could be true but not provable in ZFC.

So for example, "There is no proof of a contradiction from ZFC with
length 10^10^10," if true, is certainly provable in ZFC. We can say
this even though we don't know whether the statement is in fact true.
Ditto for "There is no odd perfect number less than 10^10^10."

On the other hand, it's entirely possible that the Riemann hypothesis
or the Goldbach conjecture or P = NP or almost any "interesting" conjecture
is true but not provable in ZFC.

One thing that sometimes confuses the issue is that we currently know only
a small number of ways to prove unprovability. Hence you will sometimes
encounter assertions such as, "large cardinals cannot settle the continuum
hypothesis" or "forcing cannot prove the independence of absolute
statements." Such assertions, if interpreted narrowly, are theorems, but
can still sometimes cause arguments because they can also be stated more
broadly and imprecisely so that they are not quite theorems any more. For
your present purposes, you should not be distracted by such debates,
because they are concerned only with the limits of current technology and
say nothing about whether future new techniques will be able to establish
the unprovability of your favorite conjecture.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

In article ,
A N Niel wrote:
In article ,
wrote:
Yes. You will not go far astray with the following rule of thumb: Any
"finite computation," if correct, is provable in ZFC, and in fact in far
weaker systems. Other than that, just from the *form* of a statement, we
can't tell a priori whether it could be true but not provable in ZFC.

The *form* can tell us something about this...
Logicians call it Pi-1 I think. (Or is it Sigma-1)

If "There is an odd perfect number" is true, then it is provable.
If "There is an even number 6 not the sum of two primes" is true,
then it is provable.

Your examples fall into the category of what I call "finite computations."
(They are Pi-0, not Pi-1.) If there is an odd perfect number, then it can
be written down explicitly and checked to be an odd perfect number with a
finite computation.

But as I said, *other than that*, there aren't any categories of statements
where the mere form tells us anything useful.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

On Jul 5, 7:30 am, " wrote:
|For a statement to be independent, it must be "Pi_2", the next level
|of logical complexity up: "For all a in A, there exists b in B,
|C(a,b)" where A and B are enumerable anc C is a computable predicate
|of A and B.

It doesn't have to be Pi_2; it just can't be Pi_1 (or Sigma_1 for that
matter). These classes of statements put upper bounds on the "logical
complexity" of statements, not lower bounds. Note also that statements
that aren't Pi_1 or Pi_2 don't have to be "worse than Pi_2"; an
independent statement could also be Sigma_2 (there exists an n, such
that for every m, P(n,m) where P is primitive recursive).

All we're really saying when we answer questions like the original
poster's is that there are certain cases where it's relatively easy to
see that a statement can't be independent, and that the example of the
infinitude of the primes of the form n^2+1 isn't one of them. This may
seem a little weak, but typically the obvious ways to see this are the
only ones you get until you either prove or disprove the claim.

There are some cases where a conjecture is reduced to a finite number
of cases before it's finally proven. If I remember correctly it was
shown that all odd numbers above some bound are sums of three primes
without it being shown that all the odd numbers below the bound but
greater than 5 are. It would be a bit weird if that happened in this
case.

Keith Ramsay

In article ,
Keith Ramsay wrote:
All we're really saying when we answer questions like the original
poster's is that there are certain cases where it's relatively easy to
see that a statement can't be independent, and that the example of the
infinitude of the primes of the form n^2+1 isn't one of them. This may
seem a little weak, but typically the obvious ways to see this are the
only ones you get until you either prove or disprove the claim.

Right. Having elsewhere said that the only examples are "finite
computations," though, I feel I should at least mention some less
obvious theorems in this direction. For example, Harvey Friedman
has shown that sentences with at most three quantifiers (in the
language of set theory, with equality and membership relation
symbols only) are either provable or disprovable in ZFC. See

http://www.cs.nyu.edu/pipermail/fom/...ne/006692.html

for some other results like this. These results are less "useful"
than they might seem at first glance when it comes to "natural"
conjectures, because usually the most straightforward formalizations
of natural mathematical statements introduce tons of quantifiers.
But in principle, one could imagine showing that (say) the Riemann
hypothesis is ZFC-equivalent to a three-quantifier sentence and
thereby reducing it to a finite computation.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

I have a silly request. Can someone explain what is exectly "Pi-1
form" ? Preesumably there are
Pi_n forms,etc. A pointer to an article, understandable by a non-
logician, would be perfectly acceptable.

Thanks in advance


Vladimir Drobot


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
* Vladimir Drobot
* Retired and gainfully unemployed
* http://www.vdrobot.com
*
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-




The issue here is the logical form of the statement. The Fermat
Conjecture (proven by Wiles) was of the "Pi_1" form "For all a in A,
B(a)" where A is an enumerable set of statements and B is a computable
predicate. Here the a are quadruples of the form (x,y,z,n) where x, y,
and z are positive integers and n is an integer =3, and B is the
condition "x^n + y^n is not equal to z^n". Clearly it is possible to
enumerate all the possible members a of A and calculate whether B is
true for each. A counterexample would be *any* member of A for which B
was false.

[
Moderator's Note:
http://planetmath.org/encyclopedia/A...Hierarchy.html
]

[
Moderator's Note:
http://planetmath.org/encyclopedia/A...Hierarchy.html
]

The line

A formula $\phi$ is $\Sigma^0_n$Êif there is some $\Delta^0_1$Êformula
....

should read

A formula $\phi$ is $\Sigma^0_n$Êif there is some $\Delta^0_0$Êformula
....

and similarly for the definition of $\Pi^0_n$ .

--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/