User z. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T07:58:13Z http://mathoverflow.net/feeds/user/14254 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/61883#61883 Answer by Z. for Knuth's intuition that Goldbach might be unprovable Z. 2011-04-16T00:05:53Z 2012-01-01T22:10:57Z <p>[Edit: In regards to some so called "open question" above, if the twin prime conjecture is independent from PA then it is false. This is very easy to see, just forget about the formulas: any non-standard model of PA is basically the initial segment N followed by some junk. Now if one can show that Goldbach holds for some non-standard model, it must also hold for the standard model N for obvious reason, since it is a "for all...". Similarly, if the twin prime conjecture is true, then it remains so for any non-standard model, since it suffices to establish the validity by exhibiting infinitely many twin primes in the standard model.]</p> <p>[Edit: If this is still not clear, what the twin prime conjecture says is essentially that "there are infinitely many" twin primes, so if it's true there are infinitely many "standard numbers" (or numerals if you like) that are twin primes. Now for specific n, checking whether n and n+2 are primes only amounts to bounded quantification (definable by a Delta_0 formula if you are such a big fan of fancy terminology...), which is never going to jump outside omega, therefore all the standard (or genuine) twin primes survive in any non-standard model, and in particular, sticking anything to the end of the standard model is not going to invalidate the fact that there are already infinitely many twin primes below omega.]</p> <p>Well, the seem to be some misunderstanding...</p> <ol> <li><p>By "unprovable" it's understood that one meant "unprovable from some formal theory" such as Peano Arithmetic or ZFC, it does not mean that Goldbach's conjecture (provided it's true) cannot have a "mathematical proof", what Knuth said (I think it might not even have a proof) in his bloody paper was utter nonsense! For example the fact that CH is independent from ZFC does not mean that it can't be proved or disproved.</p></li> <li><p>DELETED</p></li> <li><p>The existence of a non-standard model that is elementarily equivalent (have the same first order theory) to the standard model is irrelevant, since Goldbach's conjecture could be easily written as a first order sentence.</p></li> </ol> http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/61883#61883 Comment by Z. Z. 2011-04-17T16:28:37Z 2011-04-17T16:28:37Z Aha you are right, thanks! http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/61883#61883 Comment by Z. Z. 2011-04-17T15:10:12Z 2011-04-17T15:10:12Z @Andres Caicedo: Sorry for the language, I'm not saying that this works for all Pi_2 sentences, but for twin prime conjecture this is obvious! http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/61883#61883 Comment by Z. Z. 2011-04-17T08:10:51Z 2011-04-17T08:10:51Z @Andres Caicedo: Did you actually read what I said apart from quoting all the textbook result? I understand what you said about Sigma 1 completeness of Robinson arithmetic and all that. Goldbach is true if independent because if it is true for any non-standard model it must also be true for the initial segment, which is in fact a copy of the standard model. On the other hand, twin prime conjecture is false if shown independent, because again by showing that it fails for any non-standard model it also fails for the initial segment. http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/61883#61883 Comment by Z. Z. 2011-04-17T01:09:22Z 2011-04-17T01:09:22Z BTW thanks for pointing out the issue...